Question

write a program (in main.cpp) to do the following: a. build a binary search tree t1. b. do a postorder traversal of t1 and, while doing the postorder traversal, insert the nodes into a second binary search tree t2 . c. do a preorder traversal of t2 and, while doing the preorder traversal, insert the node into a third binary search tree t3. d. do an inorder traversal of t3. e. output the heights and the number of leaves in each of the three binary search trees.

Answer 1

#include <iostream>

using namespace std;

struct TreeNode

{

int value;

TreeNode *left;

TreeNode *right;

};

class Tree

{

private:

TreeNode *root;

void insert(TreeNode *&, TreeNode *&);

void destroySubTree(TreeNode *);

void deleteNode(int, TreeNode *&);

void makeDeletion(TreeNode *&);

void displayInOrder(TreeNode *) const;

void displayPreOrder(TreeNode *) const;

void displayPostOrder(TreeNode *) const;

int height(TreeNode *) const;

int nodeCount(TreeNode *) const;

int leafCount(TreeNode *) const;

public:

Tree()

{ root = NULL; }

~Tree()

{ destroySubTree(root); }

void insertNode(int);

bool searchNode(int);

void remove(int);

void displayInOrder() const

{ displayInOrder(root); }

void displayPreOrder() const

{ displayPreOrder(root); }

void displayPostOrder() const

{ displayPostOrder(root); }

int height() const

{ return height(root); }

int nodeCount() const

{ return nodeCount(root); }

int leafCount() const

{ return leafCount(root); }

};

void Tree::insert(TreeNode *&nodePtr, TreeNode *&newNode)

{

if (nodePtr == NULL)

nodePtr = newNode;

else if (newNode->value < nodePtr->value)

insert(nodePtr->left, newNode);

else

insert(nodePtr->right, newNode);

}

void Tree::insertNode(int num)

{

TreeNode *newNode;

newNode = new TreeNode;

newNode->value = num;

newNode->left = newNode->right = NULL;

insert(root, newNode);

}

void Tree::destroySubTree(TreeNode *nodePtr)

{

if (nodePtr)

{

if (nodePtr->left)

destroySubTree(nodePtr->left);

if (nodePtr->right)

destroySubTree(nodePtr->right);

delete nodePtr;

}

}

void Tree::deleteNode(int num, TreeNode *&nodePtr)

{

if (num < nodePtr->value)

deleteNode(num, nodePtr->left);

else if (num > nodePtr->value)

deleteNode(num, nodePtr->right);

else

makeDeletion(nodePtr);

}

void Tree::makeDeletion(TreeNode *&nodePtr)

{

TreeNode *tempNodePtr;

if (nodePtr == NULL)

cout << "Cannot delete empty node.\\";

else if (nodePtr->right == NULL)

{

tempNodePtr = nodePtr;

nodePtr = nodePtr->left;

delete tempNodePtr;

}

else if (nodePtr->left == NULL)

{

tempNodePtr = nodePtr;

nodePtr = nodePtr->right;

delete tempNodePtr;

}

else

{

tempNodePtr = nodePtr->right;

while (tempNodePtr->left)

tempNodePtr = tempNodePtr->left;

tempNodePtr->left = nodePtr->left;

tempNodePtr = nodePtr;

nodePtr = nodePtr->right;

delete tempNodePtr;

}

}

void Tree::remove(int num)

{

deleteNode(num, root);

}

bool Tree::searchNode(int num)

{

TreeNode *nodePtr = root;

while (nodePtr)

{

if (nodePtr->value == num)

return true;

else if (num < nodePtr->value)

nodePtr = nodePtr->left;

else

nodePtr = nodePtr->right;

}

return false;

}

void Tree::displayInOrder(TreeNode *nodePtr) const

{

if (nodePtr)

{

displayInOrder(nodePtr->left);

cout << nodePtr->value << endl;

displayInOrder(nodePtr->right);

}

}

void Tree::displayPreOrder(TreeNode *nodePtr) const

{

if (nodePtr)

{

cout << nodePtr->value << endl;

displayPreOrder(nodePtr->left);

displayPreOrder(nodePtr->right);

}

}

void Tree::displayPostOrder(TreeNode *nodePtr) const

{

if (nodePtr)

{

displayPostOrder(nodePtr->left);

displayPostOrder(nodePtr->right);

cout << nodePtr->value << endl;

}

}

int Tree::height(TreeNode *nodePtr) const

{

if (nodePtr == NULL)

return 0;

else

{

int lHeight = height(nodePtr->left);

int rHeight = height(nodePtr->right);

if (lHeight > rHeight)

return (lHeight + 1);

else

return (rHeight + 1);

}

}

int Tree::nodeCount(TreeNode *nodePtr) const

{

if (nodePtr == NULL)

return 0;

else

return (nodeCount(nodePtr->left) + nodeCount(nodePtr->right) + 1);

}

int Tree::leafCount(TreeNode *nodePtr) const

{

if (nodePtr == NULL)

return 0;

else if (nodePtr->left == NULL && nodePtr->right == NULL)

return 1;

else

return (leafCount(nodePtr->left) + leafCount(nodePtr->right));

}

int main()

{

Tree tree;

int num;

cout << "Enter numbers to be inserted in the tree, then enter -1 to stop.\\";

cin >> num;

while (num != -1)

{

tree.insertNode(num);

cin >> num;

}

cout << "Here are the values in the tree, listed in order:\\";

tree.displayInOrder();

cout << "Here are the values in the tree, listed in preorder:\\";

tree.displayPreOrder();

cout << "Here are the values in the tree, listed in postorder:\\";

tree.displayPostOrder();

cout << "Here are the heights of the tree:\\";

cout << tree.height() << endl;

cout << "Here are the number of nodes in the tree:\\";

cout << tree.nodeCount() << endl;

cout << "Here are the number of leaves in the tree:\\";

cout << tree.leafCount() << endl;

return 0;

}