C++ - Binary Tree Traversal
Binary tree is often used in many application. I have given here the sample code for Binary Tree structure, filling elements and traversal in all 3 notations - infix, prefix and postfix.
Note: I have written the code using recursive function.
Source Code
// Program for binary tree stucture and traversal
#include <iostream>
#include <string>
struct BTree
{
BTree() : data(""), left(NULL), right(NULL), parent(NULL)
{
}
BTree(const char* value) : data(value), left(NULL), right(NULL), parent(NULL)
{
}
std::string data;
BTree *left;
BTree *right;
BTree *parent;
void InsertLeft(const char* value)
{
left = new BTree(value);
left->parent = this;
}
void InsertRight(const char* value)
{
right = new BTree(value);
right->parent = this;
}
};
int TraverseAndDisplayNode(BTree *node, int notation)
{
if(node == NULL)
return -1;
if(node->parent == NULL)
{
if( notation == 0)
std::cout << "\nThe prefix notation for the expression is: ";
else if( notation == 1)
std::cout << "\nThe infix notation for the expression is: ";
else if( notation == 2)
std::cout << "\nThe postfix notation for the expression is: ";
}
if(node->left == NULL && node->right == NULL)
{
std::cout << " " << node->data;
return 0;
}
if(notation == 0)
{
// Prefix notation
std::cout << " " << node->data;
TraverseAndDisplayNode(node->left, notation);
TraverseAndDisplayNode(node->right, notation);
}
if(notation == 1)
{
// Infix notation
TraverseAndDisplayNode(node->left, notation);
std::cout << " " << node->data;
TraverseAndDisplayNode(node->right, notation);
}
if(notation == 2)
{
// Postfix notation
TraverseAndDisplayNode(node->left, notation);
TraverseAndDisplayNode(node->right, notation);
std::cout << " " << node->data;
}
}
int main()
{
BTree *root = new BTree("+");
root->InsertLeft("*");
root->InsertRight("%");
BTree *node = root->left;
node->InsertLeft("2");
node->InsertRight("4");
node = root->right;
node->InsertLeft("100");
node->InsertRight("25");
TraverseAndDisplayNode(root, 1);
std::cout << "\n";
TraverseAndDisplayNode(root, 0);
std::cout << "\n";
TraverseAndDisplayNode(root, 2);
std::cout << "\n";
return 0;
}
Output
The infix notation for the expression is: 2 * 4 + 100 % 25
The prefix notation for the expression is: + * 2 4 % 100 25
The postfix notation for the expression is: 2 4 * 100 25 % +
|
|