Tree Search using C/C++.

In the binary tree used to store a file, all the left descendants of a node with key have keys that are less than key, and all the right descendants have keys that are greater than or equal to key. The inorder traversal of such a binary tree yields the file in ascending key order.

Such a tree may also be used as a binary search tree. Using binary tree notation, the algorithm for searching for the key key in such a tree is as follows ( here we assume that each node contains four fields: k, which holds the record’s key value, r, which holds the record itself, and left and right, which are pointers to the subtrees).

p = tree;
while(p != null && key != k(p))
    p = (key < k(p))?left(p):right(p);
return (p);

The efficiency of the search process can be improved by using a sentinel, as in sequential searching. A sentinel node, with a separate external pointer pointing to it, remains allocated with the tree. All left or right tree pointers that do not point to another tree node now point to this sentinel node instead of equaling null. When a search is performed, the argument key is first inserted into the sentinel node, thus guaranteeing that it will be located in the tree. This enables the header of the search loop to be written while(key != key(p)) without the risk of an infinite loop. After leaving the loop, if p equals the external sentinel pointer, the search is unsuccessful; otherwise, p points to the desired node.

Source Code

#include<iostream>
#include<cstdlib>
#include<string>
using namespace std;
struct tree{
    int info;
    tree *Left, *Right;
};
tree *root;
class Binary_tree{
    string path;
    public:
        Binary_tree();
        void insert1(int);
        tree *insert2(tree *, tree *);
        void search(int);
        void pretrav(tree *);
        void intrav(tree *);
        void posttrav(tree *);
};
Binary_tree::Binary_tree(){
    root = NULL;
}
tree* Binary_tree::insert2(tree *temp,tree *newnode){
    if(temp==NULL){
        temp=newnode;
    }
    else if(temp->info < newnode->info){
        insert2(temp->Right,newnode);
        if(temp->Right==NULL)
            temp->Right=newnode;
    }
    else{
        insert2(temp->Left,newnode);
        if(temp->Left==NULL) temp->Left=newnode;
    }
    return temp;
}
void Binary_tree::insert1(int n){
    tree *temp=root,*newnode;
    newnode=new tree;
    newnode->Left=NULL;
    newnode->Right=NULL;
    newnode->info=n;
    root=insert2(temp,newnode);
}
void Binary_tree::pretrav(tree *t = root){
    if(root == NULL){
        cout<<"Nothing to display";
    }else
    if(t != NULL){
        cout<<t->info<<" ";
        pretrav(t->Left);
        pretrav(t->Right);
    }
}
void Binary_tree::intrav(tree *t = root){
    if(root==NULL){
        cout<<"Nothing to display";
    }else
    if(t!=NULL){
        intrav(t->Left);
        cout<<t->info<<" ";
        intrav(t->Right);
    }
}
void Binary_tree::posttrav(tree *t = root){
    if(root==NULL){
        cout<<"Nothing to display";
    }else
        if(t!=NULL){
        posttrav(t->Left);
        posttrav(t->Right);
        cout<<t->info<<" ";
    }
}
void Binary_tree::search(int key){
    tree *temp=root,*parent=root;
    path = "";
    if(temp==NULL){
        cout<<"The tree is empty"<<endl;
    }else{
        path = "root";
        while(temp!=NULL && temp->info!=key){
            parent=temp;
            if(temp->info<key){
                temp=temp->Right;
                path += "->Right";
            }else{
                temp=temp->Left;
                path += "->Left";
            }
        }
    }
    if(temp==NULL){
        cout<<"Key not found!";
    }else{
        cout<<"Key is found\n";
        cout<<"Paht is: ";
        cout<<path;
    }
}
int main(){
    Binary_tree bt;
    int choice, n, key;
    while(1){
        cout<<"\n\t1. Insert\n\t2. Search\n\t3. Preorder Traversal\n\t4. Inorder Treversal\n\t5. Postorder Traversal\n\t6. Exit"<<endl;
        cout<<"Enter your choice: ";
        cin>>choice;
        switch(choice){
            case 1:
                cout<<"Enter item: ";
                cin>>n;
                bt.insert1(n);
                break;
            case 2:
                cout<<"Enter element to search: ";
                cin>>key;
                bt.search(key);
                break;
            case 3:
                cout<<endl;
                bt.pretrav();
                break;
            case 4:
                cout<<endl;
                bt.intrav();
                break;
            case 5:
                cout<<endl;
                bt.posttrav();
                break;
            case 6:
                exit(0);
        }
    }
    return 0;
}