Basic Programming, BinaryTree

This is a discussion on Basic Programming, BinaryTree within the C++ Programming forums, part of the General Programming Boards category; So I'm quite familiar with java, but need to bring myself up to speed on c++. I've got this code ...

  1. #1
    Registered User
    Join Date
    Mar 2009
    Posts
    2

    Basic Programming, BinaryTree

    So I'm quite familiar with java, but need to bring myself up to speed on c++. I've got this code going, very basic, just starting some basic functions. My question is as to why the two argument insert doesn't update the pointer in the one argument insert. (to the root, specifically)

    Code:
    Code:
    #include <iostream>
    using namespace std;
    
    struct node {
    	int keyVal;
    	node  * left;
    	node  * right;
    };
    
    class BinarySearchTree {
    public:
    	BinarySearchTree();
    	~BinarySearchTree();
    
    	void insert(int key);
    
    private:
    	node * root;
    
    	void insert(int key, node * node);
    
    };
    
    BinarySearchTree::BinarySearchTree() {
    	root = NULL;
    }
    
    BinarySearchTree::~BinarySearchTree() {
    
    }
    
    void BinarySearchTree::insert(int key) {
    	insert(key, root);
    	if (root == NULL) {
    		cout << "Didn't work.";
    	}
    }
    
    void BinarySearchTree::insert(int key, node * leaf) {
    	if (leaf == NULL) {
    		leaf = new node;
    		leaf->keyVal = key;
    		leaf->left = NULL;
    		leaf->right = NULL;
    	}
    }
    
    int main() {
    	BinarySearchTree foo;
    	foo.insert(14);
    }
    Any input is appreciated,
    thanks.

  2. #2
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Because the pointer is passed by value and will act as a local variable.
    Consider using node*& (reference to pointer) or node** (pointer to pointer) instead.
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  3. #3
    Registered User
    Join Date
    Mar 2009
    Posts
    2
    I think I get it, the question is, what's the difference with the binary code on this site:

    Code:
    void btree::insert(int key, node *leaf)
    {
      if(key< leaf->key_value)
      {
        if(leaf->left!=NULL)
         insert(key, leaf->left);
        else
        {
          leaf->left=new node;
          leaf->left->key_value=key;
          leaf->left->left=NULL;    //Sets the left child of the child node to null
          leaf->left->right=NULL;   //Sets the right child of the child node to null
        }  
      }
      else if(key>=leaf->key_value)
      {
        if(leaf->right!=NULL)
          insert(key, leaf->right);
        else
        {
          leaf->right=new node;
          leaf->right->key_value=key;
          leaf->right->left=NULL;  //Sets the left child of the child node to null
          leaf->right->right=NULL; //Sets the right child of the child node to null
        }
      }
    }
    
    void btree::insert(int key)
    {
      if(root!=NULL)
        insert(key, root);
      else
      {
        root=new node;
        root->key_value=key;
        root->left=NULL;
        root->right=NULL;
      }
    }
    isn't it doing the same thing there?

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Not at all. Things passed into a function cannot be changed, so leaf (in either yours or theirs) can never be changed. You try to change leaf, and fail; they don't try to change leaf. (You can change what is pointed to by leaf, but you cannot change leaf itself.)

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    I'm not particularly impressed with that piece of code on this site. The else-if could just be an else, and it could be a lot simpler if the creation of the new node was separated from the linking in of it into the tree.

    I suggest passing the in parameter as a node**, or simply returning the new node* to be reassigned to the next node up, or the root.
    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"

  6. #6
    Registered User MacNilly's Avatar
    Join Date
    Oct 2005
    Posts
    311
    Alternatively, if you need to change the pointer value itself, you could do something like this:

    Code:
    void foo(tree *&root);
    Just my personal preference instead of using pointer-to-pointer syntax...
    GCC on Fedora Core 10

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    Quote Originally Posted by MacNilly View Post
    Alternatively, if you need to change the pointer value itself, you could do something like this:

    Code:
    void foo(tree *&root);
    Just my personal preference instead of using pointer-to-pointer syntax...
    Doh, for some reason I thought this was in the C forum.
    Yes of course, use a reference to a pointer in this case.
    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. please help with binary tree, urgent.
    By slickestting in forum C Programming
    Replies: 2
    Last Post: 07-22-2007, 07:55 PM
  2. [ANN] New script engine (Basic sintax)
    By MKTMK in forum C++ Programming
    Replies: 1
    Last Post: 11-01-2005, 09:28 AM
  3. what are your thoughts on visual basic?
    By orion- in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 09-22-2005, 04:28 AM
  4. visual basic vs C or C++
    By FOOTOO in forum Windows Programming
    Replies: 5
    Last Post: 02-06-2005, 07:41 PM

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