document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. // program to implement simple binary search tree in python
  2. #include<iostream>
  3.  
  4. using namespace std;
  5.  
  6. class node{
  7.     protected:
  8.         int element;
  9.         node* left;
  10.         node* right;
  11.        
  12.     public:
  13.        
  14.         //constructor that accepts only element
  15.         node(int element){
  16.             this->element = element;
  17.             this->left = NULL;
  18.             this->right = NULL;
  19.         }
  20.        
  21.         //constructor that accepts element, left Link, Right Link
  22.         node(int element, node* leftLink, node* rightLink){
  23.             this->element = element;
  24.             this->left = leftLink;
  25.             this->right = rightLink;
  26.         }
  27.  
  28.         //method to update data of the node
  29.         void updateData(int element){
  30.             this->element = element;
  31.         }
  32.  
  33.         //method to update the left Link of the node
  34.         void updateLeftLink(node* temp){
  35.             this->left = temp;
  36.         }
  37.  
  38.         //method to update the right link of the node
  39.         void updateRightLink(node* temp){
  40.             this->right = temp;
  41.         }
  42.    
  43.         //method that returns the element of the node
  44.         int getElement(){
  45.             return this->element;
  46.         }
  47.  
  48.         //method that returns left Link
  49.         node* getLeftNode(){
  50.             return this->left;
  51.         }
  52.  
  53.         //method that returns the right Link
  54.         node* getRightNode(){
  55.             return this->right;
  56.         }
  57. };
  58.  
  59. //binary search tree class
  60. class BST{
  61.     protected:
  62.         node* root;
  63.        
  64.     public:
  65.        
  66.         //constructor for bst
  67.         BST(){
  68.             root = NULL;
  69.         }
  70.  
  71.         //returns true if the root node is null
  72.         bool isEmpty(){
  73.             return(root == NULL);
  74.         }
  75.        
  76.         //returns root node
  77.         node* getRoot(){
  78.             return root;
  79.         }
  80.        
  81.         void insert(int element){          
  82.             node* temp = new node(element);
  83.             //if tree is empty put it at root node
  84.             if(root == NULL){
  85.                 root = temp;
  86.             }
  87.             else{
  88.                 bool inserted = false;
  89.                 //creating a node pointer to traverse the tree
  90.                 node* p = root;
  91.  
  92.                 //keep looping while the node is not inserted
  93.                 while(not inserted){
  94.                     //if element of the new node is less than the current node than insert it to the left
  95.                     if(p->getElement() > temp->getElement()){
  96.                         if(p->getLeftNode() == NULL){
  97.                             p->updateLeftLink(temp);
  98.                             inserted = true;
  99.                         }
  100.                         else{
  101.                             p = p->getLeftNode();
  102.                         }
  103.                     }
  104.                     //if element of the new node is greater than the current node than insert it to the right
  105.                     else if(p->getElement() < temp->getElement()){
  106.                         if(p->getRightNode() == NULL){
  107.                             p->updateRightLink(temp);
  108.                             inserted = true;
  109.                         }
  110.                         else{
  111.                             p = p->getRightNode();
  112.                         }
  113.                     }
  114.                 }
  115.             }
  116.         }
  117.        
  118.  
  119.         // method that returns true if the data is present in the bst
  120.         bool search(int data){
  121.             bool found = false;
  122.            
  123.             // creating a temp node to traverse the binary tree
  124.             node* tempNode = root;
  125.             while(tempNode != NULL){
  126.            
  127.                 // if data is less than the node element then search on the left hand side
  128.                 if(data < tempNode->getElement()){
  129.                     tempNode = tempNode->getLeftNode();
  130.                 }
  131.                 // if data is greater than the node element search on the right hand side
  132.                 else if(data > tempNode->getElement()){
  133.                     tempNode = tempNode->getRightNode();
  134.                 }
  135.                 // if data is equal to the node element then return true
  136.                 else if(data == tempNode->getElement()) {
  137.                     found = true;
  138.                     cout<<"\\n\\nThe Data "<<data<<" is found in the BST.";
  139.                     return true;
  140.                 }
  141.             }
  142.             // if data is not found then return false
  143.             if(not found){
  144.                 cout<<"\\n\\nThe Data "<<data<<" is not found in the BST.";
  145.                 return false;
  146.             }
  147.         }
  148.        
  149.         // recursive program to display tree using Preorder traversal
  150.         void displayPreorder(node* n){
  151.            
  152.             if(n == NULL){
  153.                 return;
  154.             }
  155.            
  156.             cout<<n->getElement()<<"  ";
  157.             displayPreorder(n->getLeftNode());
  158.             displayPreorder(n->getRightNode());
  159.            
  160.         }
  161.        
  162.         // recursive program to display tree using Inorder traversal
  163.         void displayInorder(node* n){
  164.            
  165.             if(n == NULL){
  166.                 return;
  167.             }
  168.            
  169.             displayInorder(n->getLeftNode());
  170.             cout<<n->getElement()<<"  ";
  171.             displayInorder(n->getRightNode());
  172.            
  173.         }
  174.        
  175.         // recursive program to display tree using Postorder traversal
  176.         void displayPostorder(node* n){
  177.            
  178.             if(n == NULL){
  179.                 return;
  180.             }
  181.            
  182.             displayPostorder(n->getLeftNode());
  183.             displayPostorder(n->getRightNode());
  184.             cout<<n->getElement()<<"  ";
  185.         }
  186.  
  187. };
  188.  
  189. int main()
  190. {
  191.     BST b1;
  192.     b1.insert(7);
  193.     b1.insert(29);
  194.     b1.insert(25);
  195.     b1.insert(36);
  196.     b1.insert(71);
  197.     b1.insert(24);
  198.     b1.insert(5);
  199.     b1.insert(9);
  200.     b1.insert(1);
  201.  
  202.     node* root = b1.getRoot();
  203.     cout<<"The Root element of the BST is : "<<root->getElement()<<endl;
  204.  
  205.     cout<<"\\nThe Preorder traversal of the BST is : ";
  206.     b1.displayPreorder(root);
  207.  
  208.     cout<<"\\n\\nThe Postorder traversal of the BST is : ";
  209.     b1.displayPostorder(root);
  210.  
  211.     cout<<"\\n\\nThe Inorder traversal of the BST is : ";
  212.     b1.displayInorder(root);
  213.  
  214.  
  215.     //searching an element in the Linked List
  216.     b1.search(24);
  217.     b1.search(77);
  218.  
  219. }
');