Chapter 9, Exercise 4 - Ordered Binary Tree - Beginning Visual C++ 2008
I know, another binary tree thread. I found many of them when I searched prior to creating this thread, so my apologies if you're a regular and are tired of seeing them.
Hopefully the mental block I'm having is simple enough that this thread will be buried soon. ;)
I completed the C++ portion of Chapter 9 (Beginning Visual C++ 2008) and finished the first three exercises without a lot of trouble (very good for morale), and was thrown for a loop by exercise 4:
Quote:
A binary tree is a structure made up of nodes, where each node contains a pointer to a “left” node and a pointer to a “right” node plus a data item, as shown in Figure 9-6.
The tree starts with a root node, and this is the starting point for accessing the nodes in the tree. Either or both pointers in a node can be null. Figure 9-6 shows an ordered binary tree, which is a tree organized so that the value of each node is always greater than or equal to the value of the left node and less than or equal to the value of the right node.
Define a native C++ class to define an ordered binary tree that stores integer values. You also need to define a Node class, but that can be an inner class to the BinaryTree class.
Write a program to test the operation of your BinaryTree class by storing an arbitrary sequence of integers in it and retrieving and outputting them in ascending sequence.
Hint: Don’t be afraid to use recursion.
To my knowledge, this is the first time tree structures have been mentioned in the book and I don't have experience with them in other programming languages, so I didn't find that explanation to be enough to get me started.
I haven't yet looked at the author's solution, but I did look at another of his books (Beginning C - From Novice to Professional 4E), Wikipedia and various other articles for direction.
For the sake of simplicity, assume there are no duplicate values. You also have say, 10 integers that you're going to use for the binary tree. My understanding is that you start with a root node and compare a second value against the root node's data value. If the second value is greater, you update the root node's right_node pointer to point to the second Node you created.
This repeats until all values have been used and all nodes are pointed to by another node (with the root node being pointed to by the BinaryTree's Node pointer). I know I'm over simplifying the process, but here is the part I'm getting hung up on:
Everything I read (with one exception I'm about to mention) referred to all new nodes being pointed to by an existing node, causing everything to be linked together.
However, as shown in Figure 11-6 (Beginning C - From Novice to Professional 4E), the Node with a data value of 480 isn't pointed to by anything else.
Is that allowed, or is that a mistake with the diagram?
Thank you for your time.
Edit:
I tried to attach the images directly to my post, but the attachment window is giving a blank window on Mozilla Firefox 11 and Google Chrome 18, so here are off-site links:
