For ths lab you are to write a C program that will perform the following operations on a binary tree.

- add
- empty
- list items in "in-order"
- list items in "pre-order"
- list items in "post-order"

typedef struct bnodestructWe will be using a binary tree form called a "binary search tree". The items in the tree are to be stored in increasing order from "left" to "right" in the tree. What this means is that all values in the left subtree of a node will be less than the element of the node, while all values in the right subtree of a node will be greater than or equal to the element of the node. Consider the following tree:

{

int elem;

struct bnodestruct* left;

struct bnodestruct* right;

} bnode;

typedef bnode* bnodePtr;

Note that the node at the top (or "root") of the tree has the value of 8. The left subtree of this node contains only values less than 8. The right subtree contains only values greater than (or equal) to 8.

To determine if a value is in the tree, we start seaching at the root. If the root pointer is empty (i.e. is a NULL pointer), we return a FALSE value and stop. If the root node contains the value we are looking for, we return a TRUE value and stop. If we are looking for a value that is less than the value in this node, we search the left subtree. Otherwise we search the right subtree. We treat the subtree as its own tree with the top node of he subtree as the new root.

If we wanted to determine if 4 was in the above tree, we would

- first check the node with element of 8. Since 4 is less than 8, we search the left subtree and
- then check the node with element of 3. Since 4 is greater than 3, we search the right subtree and
- then check the node with element of 6. Since 4 is less than 6, we search the left subtree and
- then check the node with element of 4. Since 4 equals 4, we return TRUE and stop.

- first check the node with element of 8. Since 5 is less than 8, we search the left subtree and
- then check the node with element of 3. Since 5 is greater than 3, we search the right subtree and
- then check the node with element of 6. Since 5 is less than 6, we search the left subtree and
- then check the node with element of 4. Since 5 is greater than 4, we seach the right subtree and
- then we find this subtree is empty. We return FALSE and stop.

To determine which NULL pointer to have point to the newly inserted node, we must properly search through the tree until we find a NULL pointer. The then replace this NULL pointer with a pointer to the newly inserted node. The following is psuedocode describing this action:

set curr to root of treeThus inserting the value of 5 into the above tree, we would following the same search routine as described above. Once we found that the right subtree of the node with 4 is empty, we would replace that NULL pointer with a pointer to the newly create node contain the value of 5.

while ( curr is not NULL){Insert new node at curr

if (value to insert is less than element at curr)set curr to left subtree of currelseset curr to right subtree of curr}

The input for the operations will be as follows:

q - quit the program

a <int> - add the integer value into the binary tree. The items in the tree are to be stored in increasing order from "left" to "right" in the tree. What this means is that all values in the left subtree of a node will be less than the element of the node, while all values in the right subtree of a node will be greater than or equal to the element of the node.

e - empty all values from the binary tree. Be sure to properly deallocate the nodes.

i - list the items contained in the binary tree in "in-order". This means that for every node in the tree, you list the values in the left subtree first, then list the element in the node next, and finally list the values in the right subtree. You want this to be a recursive function (the code for a non-recursive version of this function is a complete headache to write).

r - list the items contained in the binary tree in "pre-order". This means that for every node in the tree, you list the element in the node first, then list the values in the left subtree next, and finally list the values in the right subtree. You want this to be a recursive function (the code for a non-recursive version of this function is a complete headache to write).

p - list the items contained in the binary tree in "post-order". This means that for every node in the tree, you list the values in the left subtree first, then list values in the right subtree next, and finally list the element in the node. You want this to be a recursive function (the code for a non-recursive version of this function is a complete headache to write).

The "in-order" listing of the above tree would be: 1 3 4 6 7 8 10 13 14

The "pre-order" listing of the above tree would be: 8 3 1 6 4 7 10 14 13

The "post-order" listing of the above tree would be: 1 4 7 6 3 13 14 10 8

To help the TA, name your file with your net-id and the assignment name, like:

- ptroy1LabX.c

- In the CS 211 Web Pages in Blackboard, go to the Assignments Page
- Click on the link for the correct lab. This will open a web page with the title: "Upload Assignment: Lab X", where X is the number of the lab
- Scroll down and click on the button "Browse for Local File"
- Select the file that you created that contains the program. Then click OK.
- Repeat steps 3 and 4 for your second program.
- Click the submit button on the "Upload Assignment: Lab X" page.
- You should see the Submission History page that shows what you submitted. Verify you actually submitted the correct information.

I | Attachment | Action | Size | Date | Who | Comment |
---|---|---|---|---|---|---|

png | Binary_search_tree.png | manage | 6.3 K | 2012-11-20 - 18:51 | UnknownUser |

Edit | Attach | Print version | History: r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions

Topic revision: r2 - 2012-11-21 - 17:33:34 - Main.iswift2

Copyright 2016 The Board of Trustees of the University of Illinois.webmaster@cs.uic.edu |
WISEST Helping Women Faculty Advance Funded by NSF |