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 % +