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:

$ 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
advertisement

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

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.