Binary Tree Traversals in C++
In this tutorial, we will learn Binary tree traversals in C++. Three standard ways to traverse a binary tree T with root R are preorder, inorder, postorder, are as follows:
Preorder:
- Process root R.
- Travel in the left subtree of R in preorder.
- Travel in the right subtree of R in preorder.
Inorder:
- Travel in left subtree of R in inorder.
- Process root R.
- Travel in right subtree of R in inorder.
Postorder:
- Travel in left subtree of R in postorder.
- Travel in right subtree of R in postorder.
- Process root R.
The three algorithm are sometimes called , respectively , the node-left-right(NLR) traversal ,the left-node-right(LNR) traversal and the left-right-root(LRN) traversal.
You may also learn:
Program: Perform Binary Tree Traversals in C++
Below is the C++ Code to perform the mentioned operation.
#include<iostream> #include<stdlib.h> using namespace std; struct st { int data; struct st *left; struct st *right; }; struct st *root=NULL,*temp; void insertElements(); void preorder(struct st *); void inorder(struct st *); void postorder(struct st *); int main() { int ch; while(1) { cout<<"\n 1.insert Elements \n 2.preorder \n 3.inorder \n 4.postorder \n5.exit"; cout<<"\n enter ur choice "; cin>>ch; switch(ch) { case 1:insertElements();break; case 2:preorder(root);break; case 3:inorder(root);break; case 4:postorder(root);break; case 5:exit(1);break; default:cout<<"invalid operation"; } } } void insertElements() { struct st *nc,*pNode; int v; cout<<"\n enter the value "; cin>>v; temp=new st; temp->data=v; temp->left=NULL; temp->right=NULL; if(root==NULL) { root=temp; } else { nc=root; while(nc!=NULL) { pNode=nc; if(v<nc->data) nc=nc->left; else nc=nc->right; } if(v<pNode->data) { pNode->left=temp; } else pNode->right=temp; } } void preorder(struct st *temp) { if(temp!=NULL) { cout<<" "<<temp->data; preorder(temp->left); preorder(temp->right); } } void inorder(struct st *temp) { if(temp!=NULL) { inorder(temp->left); cout<<" "<<temp->data; inorder(temp->right); } } void postorder(struct st *temp) { if(temp!=NULL) { postorder(temp->left); postorder(temp->right); cout<<" "<<temp->data; } }
Output:
1.insert Elements 2.preorder 3.inorder 4.postorder 5.exit enter your choice 1 enter the value 5 1.insert Elements 2.preorder 3.inorder 4.postorder 5.exit enter your choice 1 enter the value 1 1.insert Elements 2.preorder 3.inorder 4.postorder 5.exit enter your choice 1 enter the value 3 1.insert Elements 2.preorder 3.inorder 4.postorder 5.exit enter your choice 1 enter the value 2 1.insert Elements 2.preorder 3.inorder 4.postorder 5.exit enter your choice 1 enter the value 4 1.insert Elements 2.preorder 3.inorder 4.postorder 5.exit enter your choice 2 5 1 3 2 4 1.insert Elements 2.preorder 3.inorder 4.postorder 5.exit enter your choice 3 1 2 3 4 5 1.insert Elements 2.preorder 3.inorder 4.postorder 5.exit enter your choice 4 2 4 3 1 5 1.insert Elements 2.preorder 3.inorder 4.postorder 5.exit enter your choice 5
Leave a Reply