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.

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

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); ?

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

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

>> (int &*p)
Should be (int *&p).

Quote:

---

Originally Posted by Daved

>> (int &*p)
Should be (int *&p).

---

Thanks - I don't usually do C++, so I get it wrong a bit now and again.

--
Mats

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!

Quote:

---

Originally Posted by sybariticak47

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