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.
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.
/*
* C++ Program to Perform double-order Recursive Traversal of a Given Binary Tree
*/
# include <iostream>
# include <cstdlib>
using namespace std;
/*
* Node Declaration
*/
struct node
{
int info;
struct node *left;
struct node *right;
}*root;
/*
* Class Declaration
*/
class BST
{
public:
void insert(node *, node *);
void doubleOrder(node *);
void display(node *, int);
BST()
{
root = NULL;
}
};
/*
* Main Contains Menu
*/
int main()
{
int choice, num;
BST bst;
node *temp;
while (1)
{
cout << "-----------------" << endl;
cout << "Operations on BST" << endl;
cout << "-----------------" << endl;
cout << "1.Insert Element " << endl;
cout << "2.Double-Order Traversal" << endl;
cout << "3.Display" << endl;
cout << "4.Quit" << endl;
cout << "Enter your choice : ";
cin >> choice;
switch (choice)
{
case 1:
temp = new node;
cout << "Enter the number to be inserted : ";
cin >> temp->info;
bst.insert(root, temp);
break;
case 2:
cout << "Double-Order Traversal of BST:" << endl;
bst.doubleOrder(root);
cout << endl;
break;
case 3:
cout << "Display BST:" << endl;
bst.display(root, 1);
cout << endl;
break;
case 4:
exit(1);
default:
cout << "Wrong choice" << endl;
}
}
}
/*
* Inserting Element into the Tree
*/
void BST::insert(node *tree, node *newnode)
{
if (root == NULL)
{
root = new node;
root->info = newnode->info;
root->left = NULL;
root->right = NULL;
cout << "Root Node is Added" << endl;
return;
}
if (tree->info == newnode->info)
{
cout << "Element already in the tree" << endl;
return;
}
if (tree->info > newnode->info)
{
if (tree->left != NULL)
{
insert(tree->left, newnode);
}
else
{
tree->left = newnode;
(tree->left)->left = NULL;
(tree->left)->right = NULL;
cout << "Node Added To Left" << endl;
return;
}
}
else
{
if (tree->right != NULL)
{
insert(tree->right, newnode);
}
else
{
tree->right = newnode;
(tree->right)->left = NULL;
(tree->right)->right = NULL;
cout << "Node Added To Right" << endl;
return;
}
}
}
/*
* In Order Traversal
*/
void BST::doubleOrder(node *ptr)
{
if (root == NULL)
{
cout << "Tree is empty" << endl;
return;
}
if (ptr != NULL)
{
cout << ptr->info << " ";
doubleOrder(ptr->left);
cout << ptr->info << " ";
doubleOrder(ptr->right);
}
}
/*
* Display Tree Structure
*/
void BST::display(node *ptr, int level)
{
int i;
if (ptr != NULL)
{
display(ptr->right, level + 1);
cout << endl;
if (ptr == root)
cout << "Root->: ";
else
{
for (i = 0; i < level; i++)
cout << " ";
}
cout << ptr->info;
display(ptr->left, level + 1);
}
}
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.
Related Posts:
- Check Programming Books
- Check Computer Science Books
- Practice Computer Science MCQs
- Apply for Computer Science Internship
- Check Data Structure Books