Many time we need to perform certain tasks on Binary trees. These tasks can be,

  • Counting nodes that satisfy some criteria.
  • Displaying all nodes in particular pattern like, printing expression from expression tree.
  • Creating mirror image of tree.
  • etc.


To perform these tasks we follow a pattern i.e. traverse the tree and perform certain action on each node. i.e. TASK        =    BINARY TREE TRAVERSAL     +    ACTION ON NODE Now Binary Tree Traversal can be done in following way,

In Order Traversal

Pre Order Traversal

Post Order Traversal

  • Traverse Left Child
  • Visit the node
  • Traverse Right Child
  • Visit the node
  • Traverse Left Child
  • Traverse Right Child
  • Traverse Left Child
  • Traverse Right Child
  • Visit the node
btree
Binary Tree

 

For maximum tasks we choose any one of the above order of traversal. But action that needs to be done on each visiting node changes from task to task. In this combination of BINARY TREE TRAVERSAL and ACTION, the ACTION remains open for extension but BINARY TREE TRAVERSAL remains closed for modification. Thus it fit exactly with the “open-closed principle” i.e. Software entities like classes, modules and functions should be open for extension but closed for modifications. Now we will create an object oriented binary tree traversal that is also an example of strategy design pattern. Intent of  strategy design pattern: “Define a family of algorithms, encapsulate each one, and make them interchangeable. Strategy lets the algorithm vary independently from the clients that use it.” Here in our example Strategy is NodeVisitor and BTTraversal is the algorithm that uses this strategy. Based on the concrete implementation of Strategy result of BTTraversal algorithm will vary. Algorithm: BTTraversal btree_3 Base Class : BTTraversal This class acts as the base class of Traversal Algorithms. It contains a pure virtual function traverse that accepts a pointer of NodeVisitor class. Its implementation in derived classes will use this NodeVisitor pointer as a strategy to visit each node. Based on the strategy (NodeVisitor * ) passed inside the traverse function result of traversal algorithm will vary.

Derived Class : PreOrderTraversal Specifies the Pre-Order Binary Tree Traversal

Derived Class : PostOrderTraversal Specifies the Post-Order Binary Tree Traversal

Derived Class : InOrderTraversal Specifies the In-Order Binary Tree Traversal

Strategy: NodeVisitor btree_4 Base Class : NodeVisitor It Specified the signature of Strategy i.e. action to be taken on each node.

Derived Class : DisplayVisitor Action : It just displays the node on console.

Derived Class : ExpressionVisitor Action : It displays the expression on console.

Derived Class : MirrorCreator Action : It just swaps the left and right child to visiting node.

Derived Class : CountingVisitor Action : It just counts each visiting node.

Task Handling: Task of Displaying nodes of tree though in order traversal,

Task of counting total nodes in B Tree = Inorder traversal + Counting Visitor

Creating Mirror image of B Tree = Pre traversal + Mirror Creator Visitor

Creating arithmetic expression from exp tree = Inorder traversal + Expression Display Visitor

I hope you like the article. Complete executable Code is as follows,

#include

typedef struct node
{
int value;
node * pLeft;
node * pRight;
node(int val)
{
value = val;
pLeft = NULL;
pRight = NULL;
}
}node;

class NodeVisitor
{
public:
virtual void beforeVisitingLeftChild(node * pNode){}
virtual void beforeVisitingRightChild(node * pNode){}
virtual void afterVisitingLeftChild(node * pNode){}
virtual void afterVisitingRightChild(node * pNode){}
virtual void visit(node * pNode) = 0;
};

class DisplayVisitor : public NodeVisitor
{
public:
void visit(node * pNode)
{
std::cout<value<<"  ";
}
};

class ExpressionVisitor : public NodeVisitor
{
public:
void beforeVisitingLeftChild(node * pNode)
{
std::cout<<"( ";
}
void afterVisitingRightChild(node * pNode)
{
std::cout<<") ";
}
void visit(node * pNode)
{
if(pNode->value == '+')
std::cout<<"+ ";
else if(pNode->value == '-')
std::cout<<"- ";
else if(pNode->value == '*')
std::cout<<"* ";
else
std::cout<value<" ";
}
};

class MirrorCreator : public NodeVisitor
{
public:
void visit(node * pNode)
{
node *pTemp = pNode->pLeft;
pNode->pLeft = pNode->pRight;
pNode->pRight = pTemp;
}
};

class CountingVisitor : public NodeVisitor
{
int count;
public:
CountingVisitor()
{
count = 0;
}
void visit(node * pNode)
{
count++;
}
int getCount()
{
return count;
}
};

class BTTraversal
{
NodeVisitor * mPNodeVisitor;
public:
BTTraversal()
{
mPNodeVisitor = new DisplayVisitor();
}

virtual void traverse(node * pNode, NodeVisitor * pNodeVisitor) = 0;

void traverse(node * pNode)
{
traverse(pNode, mPNodeVisitor);
}
};

class PreOrderTraversal : public BTTraversal
{
public:
void traverse(node * pNode, NodeVisitor * pNodeVisitor)
{
if(pNode == NULL)
return;
pNodeVisitor->visit(pNode);

pNodeVisitor->beforeVisitingLeftChild(pNode);
traverse(pNode->pLeft, pNodeVisitor);
pNodeVisitor->afterVisitingLeftChild(pNode);

pNodeVisitor->beforeVisitingRightChild(pNode);
traverse(pNode->pRight, pNodeVisitor);
pNodeVisitor->afterVisitingRightChild(pNode);
}
};

class PostOrderTraversal : public BTTraversal
{
public:
void traverse(node * pNode, NodeVisitor * pNodeVisitor)
{
if(pNode == NULL)
return;
pNodeVisitor->beforeVisitingLeftChild(pNode);
traverse(pNode->pLeft, pNodeVisitor);
pNodeVisitor->afterVisitingLeftChild(pNode);

pNodeVisitor->beforeVisitingRightChild(pNode);
traverse(pNode->pRight, pNodeVisitor);
pNodeVisitor->afterVisitingRightChild(pNode);

pNodeVisitor->visit(pNode);
}
};

class InOrderTraversal : public BTTraversal
{
public:
void traverse(node * pNode, NodeVisitor * pNodeVisitor)
{
if(pNode == NULL)
return;
pNodeVisitor->beforeVisitingLeftChild(pNode);
traverse(pNode->pLeft, pNodeVisitor);
pNodeVisitor->afterVisitingLeftChild(pNode);

pNodeVisitor->visit(pNode);

pNodeVisitor->beforeVisitingRightChild(pNode);
traverse(pNode->pRight, pNodeVisitor);
pNodeVisitor->afterVisitingRightChild(pNode);
}
};

node * createTree(int left, int val, int right)
{
node * pNode = new node(val);
pNode->pLeft = new node (left);
pNode->pRight = new node (right);
return pNode;
}
int main()
{
node * pRoot = createTree(4,8,9);
pRoot->pLeft->pLeft = createTree(1,2,3);
pRoot->pLeft->pRight = createTree(5,6,7);

// Default NodeVisitor i.e. DisplayVisitor will be used to display the elements of tree using in order
BTTraversal * pInOrderTraversal = new InOrderTraversal();
pInOrderTraversal->traverse(pRoot);
std::cout<<std::endl;

// DisplayVisitor will be used to display the elements of tree using in order
NodeVisitor * pVisitor = new DisplayVisitor();
pInOrderTraversal->traverse(pRoot, pVisitor);
std::cout<<std::endl;

// Counting the number of nodes using In order Traversal
CountingVisitor * pCountingVisitor = new CountingVisitor();
pInOrderTraversal->traverse(pRoot, pCountingVisitor);
std::cout<<"Total Nodes in tree = "<getCount()<<std::endl;

// Converting tree into mirror image
MirrorCreator * pMrrCreator = new MirrorCreator();
BTTraversal * pPreOrderTraversal = new PreOrderTraversal();
pPreOrderTraversal->traverse(pRoot, pMrrCreator);

// Default NodeVisitor i.e. DisplayVisitor will be used to display the elements of tree using in order
pInOrderTraversal->traverse(pRoot);
std::cout<<std::endl;

node * pExpRoot = createTree('-','+', 2);
pExpRoot->pLeft->pLeft = createTree(1,'+',3);
pExpRoot->pLeft->pRight = createTree(5,'+',7);

// Displaying expression with brackets using Expression Visitor through In Order Traversal
NodeVisitor * pExpVisitor = new ExpressionVisitor();
pInOrderTraversal->traverse(pExpRoot, pExpVisitor);
std::cout<<std::endl;
return 0;
}