Binary tree addition

This is a discussion on Binary tree addition within the C Programming forums, part of the General Programming Boards category; Hi, I'm having a little bit of trouble getting my head round the addition of a new node to a ...

  1. #1
    Registered User
    Join Date
    Sep 2002
    Posts
    137

    Binary tree addition

    Hi, I'm having a little bit of trouble getting my head round the addition of a new node to a binary tree. Do you add a new node to the top or bottom of an existing node.
    If I had this for example:
    Code:
                   |
                   a
                 /   \
    do I add the next node to the top of a or one of the bottom bits ( better word? ).
    Thanks
    http://uk.geocities.com/ca_chorltonkids

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    There is no top and bottom in a basic binary tree, only left and right. Let's say you have a tree with three values, 5, 9, and 3:
    Code:
       5
     /   \
    3     9
    Now, you want to add the value 4 to the three, but 5 already has a left node. In this case you place 4 to the right of 3 because it has a greater value than 3, but a lower value than 5:
    Code:
       5
     /   \
    3     9
     \
      4
    You can think of this insertion as placing 4 between 3 and 5. When adding to a basic binary tree, you test the value being inserted with every node until you can place it. If the value is greater than the node, move to the node's right, if the value is less than the node, move to the node's left. When you reach an empty node (usually NULL) this is where you insert the value. The recursive algorithm to do this is as follows:
    Code:
    add_node ( node, new_node )
    begin
      if node == NULL
        node = new_node
      else if new_node.value < node.value
        add_node ( node.left, new_node )
      else
        add_node ( node.right, new_node )
    end
    -Prelude
    My best code is written with the delete key.

  3. #3
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 04:00 PM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 11:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21