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;
}

---

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