Thread: Chapter 9, Exercise 4 - Ordered Binary Tree - Beginning Visual C++ 2008

  1. #1
    Registered User deoren's Avatar
    Join Date
    Mar 2003
    Posts
    63

    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:

    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:

    It is better to fail with honor than win by deceit
    - unknown

    My erratic tinkerings:
    http://projects.whyaskwhy.org/

  2. #2
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by deoren View Post
    Is that allowed, or is that a mistake with the diagram?
    It's a mistake with the diagram (an arrow is missing). Or else an illustration of a memory leak .

    Binary trees are exactly what you think they are.

    CS diagram protocols can get esoteric, tho. I could be wrong...
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  3. #3
    Registered User deoren's Avatar
    Join Date
    Mar 2003
    Posts
    63
    Quote Originally Posted by MK27 View Post
    It's a mistake with the diagram (an arrow is missing). Or else an illustration of a memory leak .

    Binary trees are exactly what you think they are.
    *Whew*

    Thanks for the confirmation.
    It is better to fail with honor than win by deceit
    - unknown

    My erratic tinkerings:
    http://projects.whyaskwhy.org/

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Class Members as Friends - Beginning Visual C++ 2008
    By deoren in forum C++ Programming
    Replies: 11
    Last Post: 02-25-2012, 12:55 PM
  2. Replies: 23
    Last Post: 01-14-2012, 11:11 AM
  3. Replies: 10
    Last Post: 11-27-2011, 11:44 AM
  4. Replies: 3
    Last Post: 12-10-2010, 12:07 AM
  5. ordered binary tree
    By Ami_01 in forum C Programming
    Replies: 3
    Last Post: 07-05-2005, 06:44 PM

Tags for this Thread