Thread: traversing binary trees or partial trees

  1. #1
    Registered User sballew's Avatar
    Join Date
    Sep 2001
    Posts
    157

    traversing binary trees or partial trees

    Please check out the file attached as it has a binary tree on it that I don't understand.

    (1) it has interior leafs and I need to follow the logic about traversing such kind of binary tree

    (2) where do you start to traverse with
    preorder
    inorder
    postorder
    types of traversals???
    (3) can you list the node more than once??? What is the rule here?

    I came up with the following paths:
    preorder : U T X U V Y W Z X Y
    inorder : U T U X V W Y X Z Y
    postorder : T U U V X W Y X Y Z

    Are they right? Are they wrong ? Why?
    Sue B.

    dazed and confused


  2. #2
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    This is surprisingly difficult to explain, so I'll try by example...
    Code:
             5
            / \
           /   \
          /     \
         /       \
        2         9
       / \       /
      /   \     /
     0     4   7
      \   /   / \
       1 3   6   8
    For this tree,
    preorder: 5 2 0 1 4 3 9 7 6 8
    inorder: 0 1 2 3 4 5 6 7 8 9
    postorder: 1 0 3 4 2 6 8 7 9 5

    Here are the rules of the game...
    First off, you have to print -all- of a node's left subtree before you can print any of the node's right subtree. No matter what kind of traversal you use.

    Second off is the order in which you do it.
    preorder is... (print parent) (print left subtree) (print right subtree)
    inorder is... (print left subtree) (print parent) (print right subtree)
    postorder is... (print left subtree) (print right subtree) (print parent)

    Let's look at the preorder I have. We always start at root.
    First thing I have to do it print the parent, so I print 5.
    Next I print the left subtree... (2 0 1 4 3)
    Then I print the right subtree... (9 7 6 8)
    5 (2 0 1 4 3) (9 7 6 8)

    But the catch is that the left and right subtrees have to be printed preorder as well. For example... (2 4 3 0 1) would not work because it prints the elements of the right subtree before the elements of the left subtree.

    ( 0 1 2 4 3) wouldn't work either because it prints the parent after printing the left subtree. It will turn out that (2 0 1 4 3) is the only preorder of the tree. All trees only have one preorder traversal, one inorder traversal, and one postorder traversal.

    One important feature is that every node in the tree will be printed once, and only once.

    And incidentally, your postorder answer is almost correct... that is...
    (left) (right) parent
    (T U U V X) (W Y X Y) Z
    So that part makes sense...
    (T U U) (V) X
    And that part works
    (no left child) (T) U U
    (T) U <- This is correct version.
    Okay, gotta get rid of one of those Us. Each node only needs printed once. Obviously (V) and (T) are right, since there's only 1 way to print 1 node. Now the left child...
    (W) (no right node) Y X Y
    (W) Y <- This is correct version.
    Y is the node, so it has to come last. Before it comes the left children (W), and the right children (none) The X and Y there are clearly axtre, so take them out.

    So now let's try to get back to the top and put this back together...
    (T U V) X)
    (W) Y
    Z
    (T U V X) (W Y) Z
    T U V X W Y Z <- this is it
    Callou collei we'll code the way
    Of prime numbers and pings!

  3. #3
    Registered User sballew's Avatar
    Join Date
    Sep 2001
    Posts
    157
    ok, so preorder is the only one that starts with parent and the root right off is a parent. Then goes down the left side of tree??


    silly question here: How did you get the the binary tree to print in this forum without left justifying everything, elminating spaces until first character/letter or / \ was encountered??? Just drove me crazy to use this thread so I attached my txt file to show you.
    Sue B.

    dazed and confused


  4. #4
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    I just wrote it up in notepad and copy and pasted it to the forum with code tags.
    Callou collei we'll code the way
    Of prime numbers and pings!

  5. #5
    Registered User sballew's Avatar
    Join Date
    Sep 2001
    Posts
    157
    I'll try that here, inserting code with tags.

    Anyways, here's another ditty about binary search trees. I missed lecture on this and I don't follow my data structure's book on searches. Can you explain this in laymen's terms?

    Question: Show the search tree that would result if the following characters are inserted in the tree from left to right :

    k e y b o a r d i n g

    Then show the results of different types of traversals of this tree
    (preorder, inorder, postorder)..


    I have no idea what this tree would look like. Is there rules to how these are put in tree?

    First guess is the following:


    Code:
                       k
                     /    \
                   e       y
                  /  \    /  \
                b    o  a     r
              /  \   /  \
             d    i  n    g
    Whether or not this tree is created right from the characters given in the order given, I want to also understand the rules for dealing with a heap with characters.

    Given this tree I have here, do I leave the letters where they are before giving the traversals OR do I sort first into heap (assuming there is a logic to the "largest" letter) and then show traversal??

    Any help here would be greatly appreciated!!!
    Sue B.

    dazed and confused


Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Converting From Binary Tree to Threaded Binary Trees
    By elton_fan in forum C Programming
    Replies: 15
    Last Post: 11-08-2007, 11:41 PM
  2. A Binary Search Tree of... Binary Search Trees...
    By SlyMaelstrom in forum C++ Programming
    Replies: 5
    Last Post: 12-10-2005, 02:12 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  5. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM