problem in binary search

This is a discussion on problem in binary search within the C++ Programming forums, part of the General Programming Boards category; hello every body I have problem when I try to looking for in number to check if the number inside ...

  1. #1
    Registered User
    Join Date
    Mar 2007
    Posts
    10

    problem in binary search

    hello every body

    I have problem when I try to looking for in number to check if the number

    inside the tree or not

    the problem in my program is

    if I search for number not inside the tree the program crash

    the code below work

    but it crash when I search for number not inside the tree

    Code:
    #include"stdafx.h"
    #include<iostream>
    using namespace std;
    
    class Node{
    
    public:
    	Node * getParent()
    	{
    		return parent;
    	}
    
    Node * getLeft(){
    
    return left;
    
    }
    
    Node * getRight(){
    
    return right;
    
    }
    
    void setParent(Node * p)
    {
    	parent = p;
    }
    
    void setLeft(Node * l)
    {
    	left = l;
    }
    
    void setRight(Node * r)
    {
    	right = r;
    }
    void setVal(int value)
    {
    	val = value;
    }
    
    int getVal()
    {
    	return val;
    }
    private:
    	Node * parent;
    	Node * left, * right;
    	int val;
    };
    
     
    
    class Tree{
    
    private:
    
    Node * root;
    
    public:
    	void setRoot(int val)
    	{
    		root =new Node();
    		root->setVal(val);
    	}
    void depthFirstTraversal(Node* root)
    {
    	if(root == NULL)
    		return;
    	else
    	{
    		if(root->getLeft()!= NULL)
    			depthFirstTraversal(root->getLeft());
    		cout << root->getVal()<<"\t"<<endl;
    		if(root->getRight()!= NULL)
    			depthFirstTraversal(root->getRight());
    	}
    }
    Tree()
    {
    	root = NULL;
    }
    Node * getRoot()
    {
    	return root;
    }
    
    Node * search(Node *root,int val)
    {
    	Node *newNode;
    	if (val < root->getVal())
    	{
    		return search(root->getLeft(),val);
    	}
    	else 
    		if (val > root->getVal())
    		{
    			return search(root->getRight(),val);
    }
    else 
    {
    	newNode = root;
    	return newNode;
    }
    
    }
    
    Node * rightMostNode(Node *n)
    {
    	while(n->getRight() != NULL)
    		n = n->getRight();
    	return n;
    }
    Node * getLeftMost(Node *n)
    {
    	while(n->getLeft() != NULL)
    		n = n->getLeft();
    	return n;
    }
    
    void insert(Node *root, int val)
    {
    	Node *temp;
    	if(root == NULL)
    {
    	root =new Node();
    	root->setVal(val);
    	this->root = root;
    //setRoot(root);
    }
    	else if(val>root->getVal())
    	{
    		if(root->getRight()!=NULL)
    			insert(root->getRight(),val);
    		else
    {
    	temp =new Node();
    	temp->setVal(val);
    	root->setRight(temp);
    }
    
    }
    
    else
    {
    	if(root->getLeft()!=NULL)
    		insert(root->getLeft(),val);
    	else
    {
    	Node *temp =new Node();
    	temp->setVal(val);
    	root->setLeft(temp);
    }
    
    }
    
    }
    
    };
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	Tree T;
    	int x;
    	cout <<"Enter element #1\n";
    	cin >> x;
    	T.setRoot(x);
    	for (int i = 0; i < 4; i++)
    	{
    		cout <<"Enter element #" << i + 2 << ": \n";
    		cin >> x;
    		T.insert(T.getRoot(),x);
    }
    	T.depthFirstTraversal(T.getRoot());
    	cout <<"Enter element to search for\n";
    	cin >> x;
    	if(x==T.search(T.getRoot(), x)->getVal())
    		cout<<"Found element "<< endl << T.search(T.getRoot(), x)->getVal();
    	else
    		cout <<"Not found\n";
    	cout << endl;
    	return 0;
    }

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    In your search function you do not check if you've reached the end of the tree, so you try to access a node that points at NULL.

    Your indentation is all over the place.

    Inside search, you do:
    Code:
    else 
    {
    	newNode = root;
    	return newNode;
    }
    That doesn't seem at all right.

    Code:
    	if(root == NULL)
    		return;
    	else
    	{
    		if(root->getLeft()!= NULL)
    			depthFirstTraversal(root->getLeft());
    		cout << root->getVal()<<"\t"<<endl;
    		if(root->getRight()!= NULL)
    			depthFirstTraversal(root->getRight());
    	}
    }
    Here you do TOO MANY checks for the bottom of the tree - you may as well just call depthFirstTraversal with root->getLeft() and root->getRight(), as you will check immediately at the start of the function if it is NULL.

    --
    Mats

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help with binary search.
    By StateofMind in forum C Programming
    Replies: 6
    Last Post: 05-06-2009, 02:14 PM
  2. Performance issue!
    By maven in forum C Programming
    Replies: 42
    Last Post: 03-23-2009, 11:57 AM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 08:40 PM
  4. Problem with binary search tree :(
    By Unregistered in forum C Programming
    Replies: 10
    Last Post: 05-01-2002, 10:31 PM
  5. binary search trees in C
    By seeks in forum C Programming
    Replies: 1
    Last Post: 02-18-2002, 03:22 AM

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