Thread: Simple binary search tree?

  1. #1
    Registered User
    Join Date
    Dec 2005
    Posts
    24

    Simple binary search tree?

    Hi! I've been trying to code a binary search tree. I had a implementation in a book and it worked, but it used a double pointer (**ptr). Although I think I understand how it works, I tried to make it so that I only had to use a single pointer (*ptr). When I changed the code it didn't work. For some reason the root pointer is never initialized. Could someone tell me the difference between my code and the book's code?

    Here's the book's code:

    Code:
    template<typename NODETYPE>class Tree;
    
    
    template<typename NODETYPE>
    class TreeNode
    {
        friend class Tree<NODETYPE>;
    public:
        TreeNode(const NODETYPE &d)
        :leftPtr(0),
         data(d),
         rightPtr(0)
         {
                     
         }
         NODETYPE getData()const
         {
             return data;
         }
    private:
        TreeNode<NODETYPE> *leftPtr;
        NODETYPE data;
        TreeNode<NODETYPE> *rightPtr;
    };
    
    #endif
    #ifndef TREE_H
    #define TREE_H
    
    #include<iostream>
    #include "Treenode.h"
    
    template<typename NODETYPE>
    class Tree
    {
    public:
        Tree();
        void insertNode(const NODETYPE & );
        void preOrderTraversal() const;
        void inOrderTraversal() const;
        void postOrderTraversal() const;
    private:
        TreeNode<NODETYPE>*rootPtr;
        void insertNodeHelper(TreeNode<NODETYPE> **, const NODETYPE & );
        void preOrderHelper(TreeNode<NODETYPE> * ) const;
        void inOrderHelper(TreeNode<NODETYPE> * ) const;
        void postOrderHelper(TreeNode<NODETYPE> * ) const;        
    };
    
    template<typename NODETYPE>
    Tree<NODETYPE>::Tree()
    {
        rootPtr=0;
    }
    
    template<typename NODETYPE>
    void Tree<NODETYPE>:: insertNode(const NODETYPE &value)
    {
        insertNodeHelper(&rootPtr,value);
    }
    
    template<typename NODETYPE>
    void Tree<NODETYPE>::insertNodeHelper(TreeNode<NODETYPE> **ptr,const NODETYPE &value)
    {
        if(*ptr==0)
            *ptr=new TreeNode<NODETYPE>(value);
        else
        {
            if(value<(*ptr)->data)
                insertNodeHelper(&( ( *ptr)->leftPtr),value);
            else
            {
                if(value>( *ptr)->data)
                    insertNodeHelper( &( (*ptr)->rightPtr),value);
                else
                    cout<<value<<" dup"<<endl;
            }
        }
    }
    Here's my code (I've only include the changed code and I have changed the prototypes):

    Code:
    template<typename NODETYPE>
    void Tree<NODETYPE>:: insertNode(const NODETYPE &value)
    {
        insertNodeHelper(rootPtr,value);//changed to giving pointer
    }
    
    template<typename NODETYPE>
    void Tree<NODETYPE>::insertNodeHelper(TreeNode<NODETYPE> *ptr,const NODETYPE &value)
    {
        if(ptr==0)//if pointer is null
        {
            ptr=new TreeNode<NODETYPE>(value);//pointer refers to new node
        }
        else
        {
            if(value<(ptr)->data)
                insertNodeHelper((ptr)->leftPtr,value);//go left if less
            else
            {
                if(value>(ptr)->data)
                    insertNodeHelper((ptr)->rightPtr,value);//go right if more
                else
                    cout<<value<<" dup"<<endl;
            }
        }
    }
    Any help would be greatly appreciated.

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    If you pass "**ptr", you are passing the address of the pointer, so when you do "*ptr = something", it changes what the pointer value is. Using a single pointer indirection, you can only change the actual data that the pointer itself points at, but you can't (permanently) change the value that the pointer holds.

    --
    Mats

  3. #3
    Registered User
    Join Date
    Dec 2005
    Posts
    24
    Thanks for responding, but I'm still a little confused. Are you saying that with single inderection that the address the pointer holds is not changed when I do something like: ptr=new TreeNode<NODETYPE>(value); ?

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    If we have the following piece of code:
    Code:
    void func1(int *p) {
       *p = 12;
       p = new int;
       *p = 24;
    }
    
    void func2(int **p) {
       **p = 16;
       *p = new int;
       **p = 32;
    }
    
    int main(void) 
    {
       int a = 0;
       int *b = &a;
       func1(b);
       printf("a=%d, *b = %d\n", a, *b);
       func2(&b);
       printf("a=%d, *b = %d\n", a, *b);
       return 0;
    }
    After func1() is called, b will still point to "a", which has the value 12, and some "random" piece of memory contains the value 24 - you won't know where that is (unless you set a breakpoint in the debugger on the line after new in func1 and print out p).

    After func2(), b points to the location given by "new int", and a contains 16. *b contains 32.

    To modify ANYTHING of what's passed into a function, it must be pointed to. To modify a the pointer, you must have a pointer to a pointer, so **.

    I have seen code with "***ptr", but that is rather unusual.

    --
    Mats

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    A side note: C++ supports "pass by reference", which is "a different way to add another *" on the argument.

    We could rewrite the func2 as:
    Code:
    void func2(int &*p) {
       *p = 16;
       p = new int;
       *p = 32;
    }
    ....
    // in main
    ...
      func2(p);
    ....
    This would work ONLY in C++, not in standard C. It basicly moves the &-sign from the calling place to the function declaration, and hides the extra "*".

    --
    Mats


    --
    Mats

  6. #6
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    >> (int &*p)
    Should be (int *&p).

  7. #7
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by Daved View Post
    >> (int &*p)
    Should be (int *&p).
    Thanks - I don't usually do C++, so I get it wrong a bit now and again.

    --
    Mats

  8. #8
    Registered User
    Join Date
    Dec 2005
    Posts
    24
    I'm still a little fuzzy, but your point that if you want to change a value, then it must be pointed to makes it much clearer. Thanks a lot!

  9. #9
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by sybariticak47 View Post
    I'm still a little fuzzy, but your point that if you want to change a value, then it must be pointed to makes it much clearer. Thanks a lot!
    It took me quite a while to "get" pointers too. It's not the easiest part of the C/C++ programming language... ;-) [The first time I wrote something in C was on a PDP-11 in 1984-85 or so, so a bit more than 20 years back].

    --
    Mats

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  2. BST (Binary search tree)
    By praethorian in forum C++ Programming
    Replies: 3
    Last Post: 11-13-2005, 09:11 AM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  4. Binary Search Tree, Inserting node
    By cheryl_li in forum C Programming
    Replies: 1
    Last Post: 09-13-2003, 03:53 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM