CIS3355:
Business Data Structures
Fall, 2008
|
|
|
How Do We Set Up A Binary Tree??
By the end of this tutorial, you will learn how to set up a binary tree.
The trick is to place the correct leaf (node) on its corresponding branch. 2. Lets suppose we have a list of numbers to be sorted:
3. We begin with the first element on the list (6). We call this the root node.
4. Now we look at the second value on the list (2). Values that are less than the root node are placed on the left and values greater than the root node are placed on the right. Since 2 < 6 we have:
From there we add 5: 5 < 6 and 5 > 2 so:
From there we will add the rest according to the list:
Just like a tree, the stems are the branches that connect the leaves (nodes). How will this apply to RAM: The branches act as pointers to the location (address) of the elements (nodes) in RAM. Each node can have a maximum of 2 "child" nodes. Lets go back and look at node 4 and node 9:
Since they have descending nodes, they are placed by 2 null characters in RAM. Nodes 5 and 10 will only have 1 null character each. So how do we determine how the new list will be sorted? 5. We start by looking at the child nodes at the bottom of the tree. We take our lowest value (4) and work our way up. Starting at node 4 then searching for its parent node (5) then back to node 2 and finally up to the root (6). From the root node we search for the lowest value on the right side which will be (7) and then finding its parent node (8). We work our way back down to node (10) and finally to node (9). The result will appear as:
Some helpful sites I found are: By now you should be able to answer the following: 1. Which is a component of a binary tree? a. block b. node c. root d. both b and c Answer: d 2. Which element do we store our original key value: a. root b. child c. leaf d. branch Answer: a 3. How are values of a binary tree determined where they will be placed? Answer: It depends on the value of the root node. If the next value o the list is less than the root value, it is placed on the left. If it's greater than the root value its placed on the right. Each element must be compared first with the root node then work its way down the tree. 4. What is the result of a node that has no "children"? Answer: A null character will be placed at the address in place of 2 child nodes if it has no children. Only 1 null character will be placed if the node only has one child (remember a node can have a max. of 2 children).
|
