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

$ 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
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.