# CSCI203/803 Exercise 4 – BST Sort Solved

20.00 \$

Category:
Click Category Button to View Your Next Assignment | Homework

You'll get a download link with a: . ` zip` solution files instantly, after Payment

## Description

For this exercise, you are to implement BST sort and test it for correctness. Your program should prompt for the name of an input file and then read and process the data contained in this file.

The file contains a sequence of integer values. Read them and construct a binary search tree from the values in the order they are read. Thus, the first number read will be the root of the tree. For this exercise, you may use dynamic data, as shown with the pseudo code on page 2.

You do not need to balance the tree as you construct it.

When you have read the last value into the BST, conduct an in‐order traversal to output the values in ascending order.

Print the values 10 to a line in a 5‐character wide field.

Do not use STL or other libraries to implement the BST.

When you are finished, test your program using the provided text file named “ex4.txt” and show your code and the output to your lab tutor to receive your mark. Also, submit your file via unix (banshee) using the submit command below.

\$ submit -u login -c CSCI203 –a ex4 filename

If you are unable to attend your lab class and demonstrate your work on time due to circumstances beyond your control (e.g. sickness), contact your lecturer  to request an extension.

BST Pseudo Code (from the week 4 lecture notes)

type tree_node = record

contents: stuff  left: ^tree_node

right: ^tree_node

root: tree_node

procedure find(value: stuff, node: ^tree_node): ^tree_node  if value == nil then

fi

if value == node.contents then

return node

else if value < node.contents then       find(value, node.left)

else

find(value, node.right)  fi end

 procedure insert(value: stuff, node: ^tree_node) next: ^tree_node, left: boolean if value == node.contents then return // already in the tree else if value < node.contents then next = node.left; left= true // we need to go left else next = node.right; left = false // we need to go right fi if next != nil then insert (value, next) // keep trying else next = new_tree_node // make a new node next.contents = value // store the value if left then // update the parent node.left = next else node.right = next fi end fi

procedure insert_first(value): ^tree_node

node: ^tree_node  start = new_tree_node  start.contents = value

return start

end

procedure visit(node: ^tree_node)

if node.left != nil then      visit(node.left)  fi

print(node.contents)

if node.right != nil then         visit(node.right)

fi

return end

procedure main()

root: ^tree_node