Binary Tree Traversal And Implementation In C++

Project: Suppose we wish to list the nodes of a tree in preorder, inorder, and postorder.
1. Propose a data structure for the representation of trees.
2. Write an algorithm to list the nodes of a tree in preorder.
3. Write an algorithm to list the nodes of a tree in inorder.
4. Write an algorithm to list the nodes of a tree in postorder.
5. Give a corresponding C++ program that has a menu, which enables the user to choose any of the above operations on trees.

The implementation of this tree traversal software should be as structured as possible.Deliverables: Students may choose to work in team of up to two members. You should turn in a report explaining all the design decisions and your code should be commented appropriately for readability and understanding. More precisely, a report should include the problem statement, proposed approach/solution along with a detailed discussion, algorithm (high-level description of all the design parts along with some details when necessary), commented C++ code, tests (input given by the user and output generated by your program execution), and lessons learned from such an implementation experience. 

Data Structure for Trees

The Binary tree is the data structure which follows the tree like structure. Each node in the binary tree holds the data and two child pointers. One child pointer points to left child and another pointer points to the right child. In order to implement efficient search data are inserted in the binary tree in a manner that nodes in the left part of the subtree are less than the data in parent node and the data in right subtree are greater than the data in the parent node.

The data stored in the binary tree are traversed in three methodologies

• Preorder traversal
• Inorder traversal
• Postorder traversal

Algorithm for the Preorder Traversal from root node:

• Visit the root
• Traverse the left sub tree
• Traverse the right sub tree

Algorithm for the Inorder Traversal from root node:

• Traverse the left sub tree
• Visit the root
• Traverse the right sub tree

Algorithm for the Preorder Traversal from root node:

• Traverse the left sub tree
• Traverse the right sub tree
• Visit the root

The program stores the structure of the Binary Tree Node in the BTNode class. The BinaryTree class performs the binary tree implementation like inserting data into the binary tree, preorder traversal, inorder traversal and postorder traversal of the binary tree. A Driver program is written which acts like the controller for the execution of the program. The driver program displays the menu and based on the user choice specific operation is carried out.

Coding:

BTNode.h

#ifndef BTNODE_H

#define BTNODE_H

#include

// BTNode defines structure of each node in the Binary Tree

class BTNode{

    public:

        // constructor of the class

        BTNode(int);

        // accessor of data

        int getData();

        // accessor of left child

        BTNode *getLeftChild();

        // accessor of right child

        BTNode *getRightChild();

        // mutuator for left child

        void setLeftChild(BTNode *);

        // mutuator for right child

        void setRightChild(BTNode *);

    private:

        // variable data is used to store the data

        int data;

        // pointer to the left child

        BTNode *leftChild;

        // pointer to the right child

        BTNode *rightChild;

#endif // BTNODE_H 

BTNode.cpp 

#include "BTNode.h"

// constructor of the BTNode

BTNode::BTNode(int data){

    // iniitalize the fields

    this->data=data;

    this->leftChild=NULL;

    this->rightChild=NULL;

// accessor of data

int BTNode::getData(){

    return data;

// accessor of left child

BTNode *BTNode::getLeftChild(){

    return leftChild;

// accessor of right child

BTNode *BTNode::getRightChild(){

    return rightChild;

// mutuator for left child

void BTNode::setLeftChild(BTNode *child){

    leftChild=child;

// mutuator for right child

void BTNode::setRightChild(BTNode *child){

    rightChild=child;

BinaryTree.h

#ifndef BINARYTREE_H

#define BINARYTREE_H

#include

#include "BTNode.h

// This class provides the definition for Binary tree to be implemented

class BinaryTree

    public:

        // constructor of the class

        BinaryTree();

        // insert data in to the binary tree

        void insert(int);

        // traverse the tree in preorder

Preorder Traversal of Binary Tree

        void preOrder();

        // traverse the tree in inorder

        void inOrder();

        // traverse the tree in postorder

        void postOrder();

    protected

    private:

        BTNode *root;

        void preOrder(BTNode *);

        void inOrder(BTNode *);

        void postOrder(BTNode *);

#endif // BINARYTREE_H

BinaryTree.cp 

#include "BinaryTree.h"

using namespace std;

// constructor of the class

BinaryTree::BinaryTree()

    root=NULL;

// insert() is used to insert data in to the binary tree

void BinaryTree::insert(int data){

    //create memory for the binary node

    BTNode *newNode=new BTNode(data);

    //check if the root is null

    if(root==NULL){

        // make the new node as the root of the tree

        root=newNode

    else{

        BTNode *current=root;

        BTNode *parent=NULL;

        bool isLeft=false;

        // traverse the tree until the valid position to place node is located

        while(current!=NULL){

            parent=current;

            // as per the algorithm the data in left sub tree are less than the parent node

            // and the data in right subtree are greater than the parent node

            if(current->getData()>=data){

                // notifies whether the last traversal was made left

                isLeft=true;

                current=current->getLeftChild();

            else{

                // notifies whether the last traversal was made right

                isLeft=false;

                current=current->getRightChild();

        // if the last traversal was made left then add the new node to the left of the parent

        if(isLeft)

            parent->setLeftChild(newNode);

        else

            parent->setRightChild(newNode); // make the new node as the right child of the parent

// traverse the tree in preorder

void BinaryTree::preOrder(){

    preOrder(root);//calls the recursive function to traverse the tree in preorder

// traverse the tree in inorder

void BinaryTree::inOrder(){

    inOrder(root);//calls the recursive function to traverse the tree in inorder

// traverse the tree in postorder

void BinaryTree::postOrder(){

    postOrder(root);//calls the recursive function to traverse the tree in postorder

// private recursive helper function to traverse the tree in preorder

void BinaryTree::preOrder(BTNode *parent){

    //check if the parent node is not null

    if(parent!=NULL){

        // Display the current node data

        cout<getData()<<" ";

        // traverse the left child of current node

        preOrder(parent->getLeftChild());

        // traverse the right child of current node

        preOrder(parent->getRightChild());

// private recursive helper function to traverse the tree in inorder

void BinaryTree::inOrder(BTNode *parent){

    //check if the parent node is not null

    if(parent!=NULL){

        // traverse the left child of current node

        inOrder(parent->getLeftChild());

        // Display the current node data

        cout<getData()<<" ";

        // traverse the right child of current node

        inOrder(parent->getRightChild());

// private recursive helper function to traverse the tree in postorder

void BinaryTree::postOrder(BTNode *parent){

    //check if the parent node is not null

    if(parent!=NULL){

        // traverse the left child of current node

        postOrder(parent->getLeftChild());

        // traverse the right child of current node

        postOrder(parent->getRightChild());

        // Display the current node data

        cout<getData()<<" "; 

main.cpp

#include

#include "BinaryTree.h

using namespace std

int main(

    bool loop=true;

    // create object for the binary tree

    BinaryTree binaryTree;

    // perform the following function repeatedly until the user exits the application

    while(loop){

        // display the menu

        cout<<"Menu"<<endl;

        cout<<"1) Insert Data"<<endl;

        cout<<"2) Display in Preorder"<<endl;

        cout<<"3) Display in Inorder"<<endl;

        cout<<"4) Display in Postorder"<<endl;

        cout<<"5) Exit"<<endl;

        //get the user choice

        cout<<"Enter your choice: ";

        int choice=0;

        cin>>choice;

        // switch based on the choice requested

        switch(choice){

            case 1:{

                // Get the data to insert from the user

                cout<<"Enter the data: ";

                int data;

                cin>>data;

                // insert the data into the binary tree

                binaryTree.insert(data);

                break

            case 2:{

                // traverse the tree in preorder traversal

                cout<<"Preorder Traversal"<<endl;

                binaryTree.preOrder();

                cout<<endl;

                break;

            case 3:{

                // traverse the tree in inorder traversal

                cout<<"Inorder Traversal"<<endl;

                binaryTree.inOrder();

                cout<<endl;

            case 4:{

                // traverse the tree in postorder traversal

                cout<<"Postorder Traversal"<<endl;

                binaryTree.postOrder();

                cout<<endl;

            case 5:{

                // set loop to false to exit the application

                loop=false;

                break;