C++ Program to Implement Double Order Traversal of a Binary Tree

«
»
This is a C++ Program to print the double order traversal of the given tree.
Recurse through:
1. Visit root of (sub)tree.
2. Visit left sub-tree.
3. Revisit root of (sub)tree.
4. Visit right sub-tree.

Here is source code of the C++ Program to Implement Double Order Traversal of a 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 Perform double-order Recursive Traversal of a Given Binary Tree
  3.  */
  4. # include <iostream>
  5. # include <cstdlib>
  6. using namespace std;
  7. /*
  8.  * Node Declaration
  9.  */
  10. struct node
  11. {
  12.         int info;
  13.         struct node *left;
  14.         struct node *right;
  15. }*root;
  16. /*
  17.  * Class Declaration
  18.  */
  19. class BST
  20. {
  21.     public:
  22.         void insert(node *, node *);
  23.         void doubleOrder(node *);
  24.         void display(node *, int);
  25.         BST()
  26.         {
  27.             root = NULL;
  28.         }
  29. };
  30. /*
  31.  * Main Contains Menu
  32.  */
  33. int main()
  34. {
  35.     int choice, num;
  36.     BST bst;
  37.     node *temp;
  38.     while (1)
  39.     {
  40.         cout << "-----------------" << endl;
  41.         cout << "Operations on BST" << endl;
  42.         cout << "-----------------" << endl;
  43.         cout << "1.Insert Element " << endl;
  44.         cout << "2.Double-Order Traversal" << endl;
  45.         cout << "3.Display" << endl;
  46.         cout << "4.Quit" << endl;
  47.         cout << "Enter your choice : ";
  48.         cin >> choice;
  49.         switch (choice)
  50.         {
  51.             case 1:
  52.                 temp = new node;
  53.                 cout << "Enter the number to be inserted : ";
  54.                 cin >> temp->info;
  55.                 bst.insert(root, temp);
  56.                 break;
  57.             case 2:
  58.                 cout << "Double-Order Traversal of BST:" << endl;
  59.                 bst.doubleOrder(root);
  60.                 cout << endl;
  61.                 break;
  62.             case 3:
  63.                 cout << "Display BST:" << endl;
  64.                 bst.display(root, 1);
  65.                 cout << endl;
  66.                 break;
  67.             case 4:
  68.                 exit(1);
  69.             default:
  70.                 cout << "Wrong choice" << endl;
  71.         }
  72.     }
  73. }
  74. /*
  75.  * Inserting Element into the Tree
  76.  */
  77. void BST::insert(node *tree, node *newnode)
  78. {
  79.     if (root == NULL)
  80.     {
  81.         root = new node;
  82.         root->info = newnode->info;
  83.         root->left = NULL;
  84.         root->right = NULL;
  85.         cout << "Root Node is Added" << endl;
  86.         return;
  87.     }
  88.     if (tree->info == newnode->info)
  89.     {
  90.         cout << "Element already in the tree" << endl;
  91.         return;
  92.     }
  93.     if (tree->info > newnode->info)
  94.     {
  95.         if (tree->left != NULL)
  96.         {
  97.             insert(tree->left, newnode);
  98.         }
  99.         else
  100.         {
  101.             tree->left = newnode;
  102.             (tree->left)->left = NULL;
  103.             (tree->left)->right = NULL;
  104.             cout << "Node Added To Left" << endl;
  105.             return;
  106.         }
  107.     }
  108.     else
  109.     {
  110.         if (tree->right != NULL)
  111.         {
  112.             insert(tree->right, newnode);
  113.         }
  114.         else
  115.         {
  116.             tree->right = newnode;
  117.             (tree->right)->left = NULL;
  118.             (tree->right)->right = NULL;
  119.             cout << "Node Added To Right" << endl;
  120.             return;
  121.         }
  122.     }
  123. }
  124. /*
  125.  * In Order Traversal
  126.  */
  127. void BST::doubleOrder(node *ptr)
  128. {
  129.     if (root == NULL)
  130.     {
  131.         cout << "Tree is empty" << endl;
  132.         return;
  133.     }
  134.     if (ptr != NULL)
  135.     {
  136.         cout << ptr->info << "  ";
  137.         doubleOrder(ptr->left);
  138.         cout << ptr->info << "  ";
  139.         doubleOrder(ptr->right);
  140.     }
  141. }
  142. /*
  143.  * Display Tree Structure
  144.  */
  145. void BST::display(node *ptr, int level)
  146. {
  147.     int i;
  148.     if (ptr != NULL)
  149.     {
  150.         display(ptr->right, level + 1);
  151.         cout << endl;
  152.         if (ptr == root)
  153.             cout << "Root->:  ";
  154.         else
  155.         {
  156.             for (i = 0; i < level; i++)
  157.                 cout << "       ";
  158.         }
  159.         cout << ptr->info;
  160.         display(ptr->left, level + 1);
  161.     }
  162. }

Output:

advertisement
$ g++ DoubleOrrderTraversal.cpp
$ a.out
 
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Double-Order Traversal
3.Display
4.Quit
Enter your choice : 1
Enter the number to be inserted : 12
Root Node is Added
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Double-Order Traversal
3.Display
4.Quit
Enter your choice : 1
Enter the number to be inserted : 10
Node Added To Left
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Double-Order Traversal
3.Display
4.Quit
Enter your choice : 1
Enter the number to be inserted : 11
Node Added To Right
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Double-Order Traversal
3.Display
4.Quit
Enter your choice : 1
Enter the number to be inserted : 02
Node Added To Left
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Double-Order Traversal
3.Display
4.Quit
Enter your choice : 1
Enter the number to be inserted : 15
Node Added To Right
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Double-Order Traversal
3.Display
4.Quit
Enter your choice : 1
Enter the number to be inserted : 19
Node Added To Right
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Double-Order Traversal
3.Display
4.Quit
Enter your choice : 1
Enter the number to be inserted : 3
Node Added To Right
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Double-Order Traversal
3.Display
4.Quit
Enter your choice : 1
Enter the number to be inserted : 1
Node Added To Left
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Double-Order Traversal
3.Display
4.Quit
Enter your choice : 1
Enter the number to be inserted : 4
Node Added To Right
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Double-Order Traversal
3.Display
4.Quit
Enter your choice : 1
Enter the number to be inserted : 70
Node Added To Right
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Double-Order Traversal
3.Display
4.Quit
Enter your choice : 3
Display BST:
 
                            70
                     19
              15
Root->:  12
                     11
              10
                                   4
                            3
                     2
                            1
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Double-Order Traversal
3.Display
4.Quit
Enter your choice : 2
Double-Order Traversal of BST:
12  10  2  1  1  2  3  3  4  4  10  11  11  12  15  15  19  19  70  70  
-----------------
Operations on BST
-----------------
1.Insert Element 
2.Double-Order Traversal
3.Display
4.Quit
Enter your choice : 4
 
------------------
(program exited with code: 0)
Press return to continue

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

advertisement

Here’s the list of Best Reference Books in C++ Programming, Data Structures and Algorithms.

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