Thread: Binary Tree Insert & Find

  1. #1
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    715

    Binary Tree Insert & Find

    I'm writing a simple program which make Binary Search Tree from some int array and then search for specified value.
    Code is:
    Code:
    #include <iostream>
    using namespace std;
    
    class BinaryTree
    {
    	typedef struct NODE
    	{
    		int data;
    		struct NODE* left;
    		struct NODE* right;
    	}node;
    
    	node *head;
    	node* InsertPrivate(node*,int);
    	node* FindPrivate(node*,int);
    	void Delete(node*);
    public:
    	BinaryTree();
    	~BinaryTree();
    	void Insert(int);
    	node* Find(int);
    };
    
    BinaryTree::BinaryTree():head(0){}
    BinaryTree::~BinaryTree(){Delete(head);}
    void BinaryTree::Insert(int data)
    {
    	head=InsertPrivate(head,data);
    }
    
    BinaryTree::node* BinaryTree::InsertPrivate(node* root,int data)
    {
    	if(!root)
    	{
    		root=new node;
    		root->data=data;
    		root->left=0;
    		root->right=0;
    		return root;
    	}
    
    	if(data<=root->data)
    		root->left=InsertPrivate(root->left,data);
    	else
    		root->right=InsertPrivate(root->right,data);
    	return root;
    }
    
    BinaryTree::node* BinaryTree::FindPrivate(node*root,int data)
    {
    	if(!root)
    	{
    		return root;
    	}
    	if(root->data==data)
    		return root;
    	else
    	{
    		if(data<root->data)
    			root=FindPrivate(root->left,data);
    		else
    			root=FindPrivate(root->right,data);
    	}
    	return root;
    }
    
    BinaryTree::node* BinaryTree::Find(int data)
    {
    	node *cur=FindPrivate(head,data);
    	if(!cur)
    		cout<<"No element"<<endl;
    	else
    		cout<<"Success!"<<endl;
    	return cur;
    }
    
    void BinaryTree::Delete(node *current)
    {
    	if(current !=0)
    	{
    		Delete(current->left);
    		Delete(current->right);
    		delete current;
    	}
    
    }
    int main()
    {
    	int array[]={5,1,8,2,0,4,7,1,9,2};
    	BinaryTree b;
    	for(int i=0;i<10;i++)
    		b.Insert(array[i]);
    	b.Find(19);
    }
    and it seems to work fine. However, I had difficulties to make it work properly. I was getting strange errors when trying to write
    node* BinaryTree::FindPrivate(node*root,int data)
    and not
    BinaryTree::node* BinaryTree::FindPrivate(node*root,int data)
    I assume that is because of node is declared within class.
    If you can examine this code and give some advices how to make it simpler?

    Because of recursion in class I had to write two versions of functions Find and Insert
    maybe there is a better way.
    Thanks for your help

  2. #2
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    First a note. You don't have to use typedef on a struct in C++. In C you had, but not C++.
    Code:
    struct node
    {
       ...
    };
    Second, your deletion method seems suspicious. You never nullify any of the node pointers. After deletion the parent still points to the deleted node, which may (and will) cause errors.
    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
    Its not rocket science vasanth's Avatar
    Join Date
    Jan 2002
    Posts
    1,683
    Quote Originally Posted by Magos
    Second, your deletion method seems suspicious. You never nullify any of the node pointers. After deletion the parent still points to the deleted node, which may (and will) cause errors.
    any wont be wont be using the head pointer any way since the destructor will be called when the object is destroyed...

  4. #4
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    715
    I don't know what you mean exactly.
    Maybe after delete I should put current=NULL???

  5. #5
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >I assume that is because of node is declared within class
    Yes.

    >If you can examine this code and give some advices how to make it simpler?
    What you have is about as simple as it gets.

    >maybe there is a better way
    It depends on your philosophical beliefs concerning binary search trees. This is a good use of recursion, but to have a simple interface you need to have helper functions that prepare for, call, and finalize the recursive functions. You could write a non-recursive insertion and search fairly easily, but some would say such a beast is not as elegant. I personally use recursion if it makes the code or problem signifigantly simpler, but that often requires writing a non-recursive implementation for comparison. As this article shows, the recursive and non-recursive algorithms are very close in simplicity and size, but the recursive algorithm requires workarounds if you need certain features like error reporting for duplicates. A more direct approach results in more direct solutions as it were.

    >Maybe after delete I should put current=NULL???
    There's no need. Delete is private, so you have no worries about the client calling it and then using the object. Your implementation only calls Delete from the destructor, so there's no worry about an invalid root being accessed as the object will be completely destroyed. If you plan on making Delete into a more generic function that clears a tree for further use, it would be a good idea to set the root to null.
    Last edited by Prelude; 04-11-2004 at 01:20 PM.
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. problem in creating a tree
    By Lorin_sz in forum C Programming
    Replies: 1
    Last Post: 09-26-2005, 01:24 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, 09:40 PM
  4. binary search and search using binary tree
    By Micko in forum C++ Programming
    Replies: 9
    Last Post: 03-18-2004, 10:18 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM