CIS3355:
Business Data Structures
Fall, 2008
|
|
|
Before we begin, we already know the following: v A Binary search tree is a linked structured data typeit allows for a binary search strategy. v A binary tree is made up of roots, parent and child nodes (leaves). v The 1st element on a list to be sorted is called the root node,
v
v All nodes, except the root node has a parent and each parent can have a maximum of 2 child nodes.
v A node that points to no children has a null pointer.
1. Lets look at the list:
2. Look at the first element on the list, M, this would be our root node.
2.Now look at the second element D. Alphabetically, D goes before M so we will place it to the left of M
   *Elements
that are < parent
Node go to the left and Elements > parent Node go to the right.
3.The next element is A and following the rules, we have:
4. The next element on the list is going to be larger than the root node so it will be placed to the right of it.
4. Now look at element F, it is less than M but D is already there, F can still be placed on the tree F comes after D alphabetically.
5. Now by adding P the tree is now complete:
**This is how the last step was done: P is greater than M therefore, it goes right. T is already to the right of M so P will go to the left of T, since alphabetically, it goes before it.
6. The last step is to traverse (or backtrack) and determine the sorted list according to the binary tree:
7. This is how we did the last step: 1. Start from the leftmost child node (in this case A) and go to its parent D, then go back down right to F.
2. Going back up the tree we go to the root D and back down the RIGHT side since we already did the left.
3. Now we will go to node T (next on list) and finally its child P. (this is because we always look at children first, we are looking at the children of the root M and so we must consider T first before P).
By now you should know the answers to the following questions: 1. A child node is known as___________. a. kids b. descendant c. leaf ANSWER: C
2. A binary search tree is a ______________. a. made of wood b. Structured data object c. Float d. None of the above ANSWER: B
Describe the characteristics of a parent and child node. ANSWER: A node can either be a parent node or a child node, a parent node may have between 0 and at most 2 child nodes, a node that has no children points to a null value.
What is traversal? ANSWER: Traversal is when you have a completed binary tree and go back and sort out the elements according to their location on the tree.
Here are some other useful references I found, hope they help!
http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic9/ http://en.wikipedia.org/wiki/Binary_tree
http://www.cs.oberlin.edu/classes/dragn/labs/avl/avl3.html
|
