Tree Search using C/C++.

In the binary tree used to store a file, all the left descendants of a node with key 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 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
 
#include
 
#includestring>
 
 
 
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 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){
 
        coutNothing to display";
 
    }else
 
    if(t != NULL){
 
        coutinfo ";
 
        pretrav(t->Left);
 
        pretrav(t->Right);
 
    }
 
}
 
 
 
void Binary_tree::intrav(tree *t = root){
 
    if(root==NULL){
 
        coutNothing to display";
 
    }else
 
    if(t!=NULL){
 
        intrav(t->Left);
 
        coutinfo ";
 
        intrav(t->Right);
 
    }
 
}
 
 
 
void Binary_tree::posttrav(tree *t = root){
 
    if(root==NULL){
 
        coutNothing to display";
 
    }else
 
        if(t!=NULL){
 
        posttrav(t->Left);
 
        posttrav(t->Right);
 
        coutinfo ";
 
    }
 
}
 
 
 
void Binary_tree::search(int key){
 
    tree *temp=root,*parent=root;
 
    path = "";
 
    if(temp==NULL){
 
        coutThe tree is empty"
 
    }else{
 
        path = "root";
 
        while(temp!=NULL && temp->info!=key){
 
            parent=temp;
 
            if(temp->info
 
                temp=temp->Right;
 
                path += "->Right";
 
            }else{
 
                temp=temp->Left;
 
                path += "->Left";
 
            }
 
        }
 
    }
 
    if(temp==NULL){
 
        coutKey not found!";
 
    }else{
 
        coutKey is found\n";
 
        coutPaht is: ";
 
        cout
 
    }
 
}
 
 
 
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"
 
        coutEnter your choice: ";
 
        cin>>choice;
 
 
 
        switch(choice){
 
            case 1:
 
                coutEnter item: ";
 
                cin>>n;
 
                bt.insert1(n);
 
                break;
 
            case 2:
 
                coutEnter element to search: ";
 
                cin>>key;
 
                bt.search(key);
 
                break;
 
            case 3:
 
                cout
 
                bt.pretrav();
 
                break;
 
            case 4:
 
                cout
 
                bt.intrav();
 
                break;
 
            case 5:
 
                cout
 
                bt.posttrav();
 
                break;
 
            case 6:
 
                exit(0);
 
        }
 
    }
 
    return 0;
 
}