Thread: inserting characters into a binary tree

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

    inserting characters into a binary tree

    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!!!
    Last edited by sballew; 12-06-2001 at 09:08 AM.
    Sue B.

    dazed and confused


  2. #2
    of Zen Hall zen's Avatar
    Join Date
    Aug 2001
    Posts
    1,007
    I get -
    Code:
    	      k
    	     /   \
    	    e      y
               /  \   / \
    	  b    i  o
    	 / \   / / \
    	a   d  g n  r
    For each entry you start at the root. If it's less than the node insert to the left, if it's greater insert to the right and continue until you find a empty child. Everything to the left of 'k' should be less than it and to the right greater, and so on throughout the tree.

    If you're implementing a binary search tree then you don't need a 'heap' and can traverse the tree as it is.
    zen

  3. #3
    Registered User sballew's Avatar
    Join Date
    Sep 2001
    Posts
    157
    Zen,

    I am not following your logic of
    < goes on left
    > goes on right



    Code:
                          k
                        /   \
                      e      y
                     /  \   /  \
                    b                                  <------ I get this to this point
    why would the "o" then go to the right of 'parent y' instead of
    'parent e' if e is the same node we are on after placement of
    'b'???

    Why wouldn't each letter be moved to the next child of same node if it fits the rule, else go to node on same level and fit in child of that node that it fits, then if that level is full and letter coming in doesn't fit rule for any node on that level go to the next level of nodes until all are placed?? Is there a rule I am missing/forgeting about filling in children and leaving too many "leaves" open??
    Code:
                             k 
                           /    \
                          /       \
                        e           y
                      /    \        /  \
                     /      \      /     \
                    b       o     a    
                   /   \    / \    / \
                  /     \  /   \  /   \
                        r  d      i
                      / \  /\
                     /   \/  \
                    n        g
    Sue B.

    dazed and confused


  4. #4
    of Zen Hall zen's Avatar
    Join Date
    Aug 2001
    Posts
    1,007
    why would the "o" then go to the right of 'parent y' instead of
    'parent e' if e is the same node we are on after placement of
    'b'???
    It'd go on the left of 'y' as it's less than it.

    Starting from the root 'o' is greater than 'k' so it'd go to the right. 'y' exists to the right of 'k' so repeat the comparison. 'o' is less than 'y' so it goes to the left. There's no existing node there so that's where it's inserted. For a plain binary search tree, after each placement you return to the root to find the insertion point for the next node and don't continue from the last place where a node was inserted.
    Last edited by zen; 12-06-2001 at 03:58 PM.
    zen

  5. #5
    Registered User sballew's Avatar
    Join Date
    Sep 2001
    Posts
    157
    I understand now. Thanks.
    Sue B.

    dazed and confused


Popular pages Recent additions subscribe to a feed

Similar Threads

  1. please help with binary tree, urgent.
    By slickestting in forum C Programming
    Replies: 2
    Last Post: 07-22-2007, 07:55 PM
  2. Binary Search Tree - one last question
    By tms43 in forum C++ Programming
    Replies: 2
    Last Post: 11-14-2006, 03:58 AM
  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. Inserting infix into a binary tree
    By Nakeerb in forum C++ Programming
    Replies: 20
    Last Post: 01-20-2003, 05:03 PM
  5. Templated Binary Tree... dear god...
    By Nakeerb in forum C++ Programming
    Replies: 15
    Last Post: 01-17-2003, 02:24 AM