C++ Program to Implement Threaded Binary Tree

«
»
This C++ Program demonstrates the implementation of Threaded Binary Tree.

Here is source code of the C++ Program to demonstrate the implementation of Threaded Binary Tree. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1.  /*
  2.   * C++ Program to Implement Threaded Binary Tree
  3.   */
  4. #include <iostream>
  5. #include <cstdlib>
  6. #define MAX_VALUE 65536
  7. using namespace std;
  8.  
  9. /* Class Node */
  10.  
  11. class Node
  12. {
  13. 	public:
  14.         int key;
  15.         Node *left, *right;
  16.         bool leftThread, rightThread; 
  17. };
  18.  
  19. /* Class ThreadedBinarySearchTree */
  20.  
  21. class ThreadedBinarySearchTree
  22. {
  23. 	private:
  24.         Node *root;
  25.     public: 
  26.         /* Constructor */
  27.         ThreadedBinarySearchTree() 
  28.         {
  29.             root = new Node();
  30.             root->right = root->left = root;
  31.             root->leftThread = true;
  32.             root->key = MAX_VALUE;
  33.         }
  34.  
  35.         /* Function to clear tree */
  36.         void makeEmpty()
  37.         {
  38.             root = new Node();
  39.             root->right = root->left = root;
  40.             root->leftThread = true;
  41.             root->key = MAX_VALUE;
  42.         }
  43.  
  44.         /* Function to insert a key */
  45.         void insert(int key) 
  46.         {
  47.             Node *p = root;
  48.             for (;;) 
  49.             {
  50.                 if (p->key < key) 
  51.                 {
  52.                     if (p->rightThread) 
  53.                         break;
  54.                     p = p->right;
  55.                 } 
  56.                 else if (p->key > key) 
  57.                 {
  58.                     if (p->leftThread) 
  59.                         break;
  60.                     p = p->left;
  61.                 }
  62.                 else 
  63.                 {
  64.                     /* redundant key */
  65.                     return; 
  66.                 }
  67.             }
  68.             Node *tmp = new Node();
  69.             tmp->key = key;
  70.             tmp->rightThread = tmp->leftThread = true;
  71.             if (p->key < key) 
  72.             { 
  73.                 /* insert to right side */
  74.                 tmp->right = p->right;
  75.                 tmp->left = p;
  76.                 p->right = tmp;
  77.                 p->rightThread = false;
  78.             }
  79.             else
  80.             {
  81.                 tmp->right = p;
  82.                 tmp->left = p->left;
  83.                 p->left = tmp;
  84.                 p->leftThread = false;
  85.             }
  86.         }
  87.  
  88.         /* Function to search for an element */
  89.         bool search(int key) 
  90.         {
  91.             Node *tmp = root->left;
  92.             for (;;) 
  93.             {
  94.                 if (tmp->key < key) 
  95.                 {
  96.                     if (tmp->rightThread) 
  97.                         return false;
  98.                     tmp = tmp->right;
  99.                 } 
  100.                 else if (tmp->key > key) 
  101.                 {
  102.                     if (tmp->leftThread) 
  103.                         return false;
  104.                     tmp = tmp->left;
  105.                 } 
  106.                 else 
  107.                 {
  108.                     return true;
  109.                 }
  110.             }
  111.         }
  112.  
  113.         /* Fuction to delete an element */
  114.         void Delete(int key)
  115.         {
  116.             Node *dest = root->left, *p = root;
  117.             for (;;) 
  118.             {
  119.                 if (dest->key < key) 
  120.                 {
  121.                     /* not found */
  122.                     if (dest->rightThread) 
  123.                         return; 
  124.                     p = dest;
  125.                     dest = dest->right;
  126.                 } 
  127.                 else if (dest->key > key) 
  128.                 {
  129.                     /* not found */
  130.                     if (dest->leftThread) 
  131.                         return; 
  132.                     p = dest;
  133.                     dest = dest->left;
  134.                 }
  135.                 else 
  136.                 {
  137.                     /* found */
  138.                     break; 
  139.                 }
  140.             }
  141.             Node *target = dest;
  142.             if (!dest->rightThread && !dest->leftThread) 
  143.             { 
  144.                 /* dest has two children*/
  145.                 p = dest;
  146.                 /* find largest node at left child */
  147.                 target = dest->left;
  148.                 while (!target->rightThread) 
  149.                 {
  150.                     p = target;
  151.                     target = target->right;
  152.                 }
  153.                 /* using replace mode*/
  154.                 dest->key = target->key; 
  155.             }
  156.             if (p->key >= target->key) 
  157.             {
  158.                 if (target->rightThread && target->leftThread) 
  159.                 {
  160.                     p->left = target->left;
  161.                     p->leftThread = true;
  162.                 } 
  163.                 else if (target->rightThread) 
  164.                 {
  165.                     Node *largest = target->left;
  166.                     while (!largest->rightThread)
  167.                     {
  168.                         largest = largest->right;
  169.                     }
  170.                     largest->right = p;
  171.                     p->left = target->left;
  172.                 }
  173.                 else 
  174.                 {
  175.                     Node *smallest = target->right;
  176.                     while (!smallest->leftThread) 
  177.                     {
  178.                         smallest = smallest->left;
  179.                     }
  180.                     smallest->left = target->left;
  181.                     p->left = target->right;
  182.                 }
  183.             } 
  184.             else 
  185.             {
  186.                 if (target->rightThread && target->leftThread) 
  187.                 {
  188.                     p->right = target->right;
  189.                     p->rightThread = true;
  190.                 }
  191.                 else if (target->rightThread) 
  192.                 {
  193.                     Node *largest = target->left;
  194.                     while (!largest->rightThread) 
  195.                     {
  196.                         largest = largest->right;
  197.                     }
  198.                     largest->right =  target->right;
  199.                     p->right = target->left;
  200.                 } 
  201.                 else 
  202.                 {
  203.                     Node *smallest = target->right;
  204.                     while (!smallest->leftThread)
  205.                     {
  206.                         smallest = smallest->left;
  207.                     }
  208.                     smallest->left = p;
  209.                     p->right = target->right;
  210.                 }
  211.             }
  212.         }
  213.  
  214.         /* Function to print tree */
  215.         void printTree() 
  216.         {
  217.             Node *tmp = root, *p;
  218.             for (;;) 
  219.             {
  220.                 p = tmp;
  221.                 tmp = tmp->right;
  222.                 if (!p->rightThread) 
  223.                 {
  224.                     while (!tmp->leftThread) 
  225.                     {
  226.                         tmp = tmp->left;
  227.                     }
  228.                 }
  229.                 if (tmp == root) 
  230.                     break;
  231.                 cout<<tmp->key<<"   ";
  232.             }
  233.             cout<<endl;
  234.         }    
  235. };
  236.  
  237. /* Main Contains Menu */
  238.  
  239. int main()
  240. {            
  241.     ThreadedBinarySearchTree tbst; 
  242.     cout<<"ThreadedBinarySearchTree Test\n";          
  243.     char ch;
  244.     int choice, val;
  245.     /*  Perform tree operations  */
  246.     do    
  247.     {
  248.         cout<<"\nThreadedBinarySearchTree Operations\n";
  249.         cout<<"1. Insert "<<endl;
  250.         cout<<"2. Delete"<<endl;
  251.         cout<<"3. Search"<<endl;
  252.         cout<<"4. Clear"<<endl; 
  253.         cout<<"Enter Your Choice: ";
  254.         cin>>choice;
  255.         switch (choice)
  256.         {
  257.         case 1 : 
  258.             cout<<"Enter integer element to insert: ";
  259.             cin>>val;
  260.             tbst.insert(val);                     
  261.             break;                          
  262.         case 2 : 
  263.             cout<<"Enter integer element to delete: ";
  264.             cin>>val;
  265.             tbst.Delete(val);                     
  266.             break;                         
  267.         case 3 : 
  268.             cout<<"Enter integer element to search: ";
  269.             cin>>val;
  270.             if (tbst.search(val) == true)
  271.                 cout<<"Element "<<val<<" found in the tree"<<endl;
  272.             else
  273.                 cout<<"Element "<<val<<" not found in the tree"<<endl;
  274.             break;       
  275.         case 4 : 
  276.             cout<<"\nTree Cleared\n";
  277.             tbst.makeEmpty();
  278.             break;           
  279.         default : 
  280.             cout<<"Wrong Entry \n ";
  281.             break;   
  282.         }
  283.         /*  Display tree  */ 
  284.         cout<<"\nTree = ";
  285.         tbst.printTree();            
  286.         cout<<"\nDo you want to continue (Type y or n): ";
  287.         cin>>ch;                       
  288.     } 
  289.     while (ch == 'Y'|| ch == 'y');               
  290.     return 0;
  291. }

advertisement
$ g++ threaded_binary_tree.cpp
$ a.out
 
ThreadedBinarySearchTree Test
 
ThreadedBinarySearchTree Operations
1. Insert
2. Delete
3. Search
4. Clear
Enter Your Choice: 1
Enter integer element to insert: 28
 
Tree = 28
 
Do you want to continue (Type y or n): y
 
ThreadedBinarySearchTree Operations
1. Insert
2. Delete
3. Search
4. Clear
Enter Your Choice: 1
Enter integer element to insert: 5
 
Tree = 5   28
 
Do you want to continue (Type y or n):
y
 
ThreadedBinarySearchTree Operations
1. Insert
2. Delete
3. Search
4. Clear
Enter Your Choice: 1
Enter integer element to insert: 19
 
Tree = 5   19   28
 
Do you want to continue (Type y or n): y
 
ThreadedBinarySearchTree Operations
1. Insert
2. Delete
3. Search
4. Clear
Enter Your Choice: 1
Enter integer element to insert: 63
 
Tree = 5   19   28   63
 
Do you want to continue (Type y or n): y
 
ThreadedBinarySearchTree Operations
1. Insert
2. Delete
3. Search
4. Clear
Enter Your Choice: 1
Enter integer element to insert: 14
 
Tree = 5   14   19   28   63
 
Do you want to continue (Type y or n): y
 
ThreadedBinarySearchTree Operations
1. Insert
2. Delete
3. Search
4. Clear
Enter Your Choice: 1
Enter integer element to insert: 7
 
Tree = 5   7   14   19   28   63
 
Do you want to continue (Type y or n): y
 
ThreadedBinarySearchTree Operations
1. Insert
2. Delete
3. Search
4. Clear
Enter Your Choice: 1
Enter integer element to insert: 70
 
Tree = 5   7   14   19   28   63   70
 
Do you want to continue (Type y or n): y
 
ThreadedBinarySearchTree Operations
1. Insert
2. Delete
3. Search
4. Clear
Enter Your Choice: 2
Enter integer element to delete: 24
 
Tree = 5   7   14   19   28   63   70
 
Do you want to continue (Type y or n): y
 
ThreadedBinarySearchTree Operations
1. Insert
2. Delete
3. Search
4. Clear
Enter Your Choice: 2
Enter integer element to delete: 14
 
Tree = 5   7   19   28   63   70
 
Do you want to continue (Type y or n): y
 
ThreadedBinarySearchTree Operations
1. Insert
2. Delete
3. Search
4. Clear
Enter Your Choice: 3
Enter integer element to search: 63
Element 63 found in the tree
 
Tree = 5   7   19   28   63   70
 
Do you want to continue (Type y or n): y
 
ThreadedBinarySearchTree Operations
1. Insert
2. Delete
3. Search
4. Clear
Enter Your Choice: 4
 
Tree Cleared
 
Tree =
 
Do you want to continue (Type y or n): n
 
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn