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.