clumpsy tree insertion

This is a discussion on clumpsy tree insertion within the C++ Programming forums, part of the General Programming Boards category; This is my clumsy implementation of insertion into a binary tree class. It just uses nested "if" statement to walk ...

  1. #1
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    454

    clumpsy tree insertion

    This is my clumsy implementation of insertion into a binary tree class. It just uses nested "if" statement to walk through the node recursively.
    Code:
    class Tree
    {
    private:
       struct Node
      {
        int item;
        //  relate[0] = parent;
        //  relate[1] = left child;
        //  relate[2] = right child;
        Node * relate[3];
        Node(int n = 0):item(n)
        {
          relate[0]=relate[1] = relate[2] = 0;
        }
      };
      
      Node* root, *temp_insert;
    public:
       void insert_tree(int x);
    };
    
    // insertion
    void Tree::insert_tree(int x)
    {
      if ( x < temp_insert->item)
        {
          if( temp_insert->relate[1] != NULL)
    	{
    	  temp_insert = temp_insert->relate[1];
    	  insert_tree(x);
    	}
          else
    	{
    	  Node * temp = new Node(x);
    	  temp_insert->relate[1] = temp;
    	  temp->relate[0] = temp_insert;
    	  temp_insert = root; 
    	}
    	
        }
      else if( x > temp_insert->item )
        {
          if( temp_insert->relate[1] != NULL)
    	{
    	  temp_insert = temp_insert->relate[2];
    	  insert_tree(x);
    	}
          else
    	{
    	  Node * temp = new Node(x);
    	  temp_insert->relate[2] = temp;
    	  temp->relate[0] = temp_insert;
    	  temp_insert = root;
    	}
        }
      
    }
    Tree insertion seems to work better if it takes in as the argument the pointer to a node. But since the node is private, it makes recursion call a lot more awkward through the use of a member variable "temp_insert" to walk around the nodes. is there a way to avoid this problem?
    "All that we see or seem
    Is but a dream within a dream." - Poe

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Is this the sort of thing you're looking for?
    Code:
    void Tree::insert_tree(int x) {
        insert_tree_for_real(root, x);
    }
    
    void Tree::insert_tree_for_real(Node *root_o_tree, int value) {
        //usual recursive function goes here
    }

  3. #3
    -bleh-
    Join Date
    Aug 2010
    Location
    somewhere in this universe
    Posts
    454
    Quote Originally Posted by tabstop View Post
    Is this the sort of thing you're looking for?
    Code:
    void Tree::insert_tree(int x) {
        insert_tree_for_real(root, x);
    }
    
    void Tree::insert_tree_for_real(Node *root_o_tree, int value) {
        //usual recursive function goes here
    }
    hi tabstop. a function wrapper? DUH, that's genius, why didn't i think of that.. *sigh*. thank you, I really appreciate your help.
    "All that we see or seem
    Is but a dream within a dream." - Poe

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    Most of us don't think of everything the first time.
    It's been almost 20 years since I started programming and just today I saw something that made me wonder why I didn't think of a certain way of doing something yesterday.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  2. 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
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 08:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

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