Task 1. Defining a class, BSTNode Start this task by designing the BSTNode class

Question

Task 1. Defining a class,

BSTNode Start this task by designing the BSTNode class for the BST. For the initial development you should just build the node to hold a std::string as its data. The BSTNode class will consist of a string and left and right pointers. It will initialize the node using it’s constructor. You will also overload the stream insertion operator << to output a node. Will you need access and/or modify the contents of the nodes from outside the node? Yes! Then you should implement getters/setters. Note: you will be inserting data into the tree using recursion. How will this impact your getters in the BSTNode class? Consider passing the left and right pointers back by reference. The data in the node is a std::string, should we pass the newData value into the setter using pass-by-reference? Recall, a std::string is an object type, and hence, if the object is not passed by reference, then a copy of the object is made (std::string copy constructor is invoked). Is this the intent? Probably not!

Task 2. Now create the BST class Implement a BST class.

You are now ready to define the BST class. You should create an attribute member for a pointer that will be the root of the BST. The pointers should be of type BSTNode. You will also implement the constructor, the deep copy constructor, and the destructor (should destroy the tree through postorder traversing of nodes). Additionally, you need: insertNode ( ) - that adds an item to the BST. Recall the properties of a BST. The values in any left subtree are less than its parent node, and any values in the right subtree are greater than its parent node. Use recursion in your implementation! inOrderTraversal ( ) - that prints the contents of the BST inorder. Use recursion in your implementation! preOrderTraversal ( ) - that prints the contents of the BST preorder. Use recursion in your implementation! postOrderTraversal ( ) - that prints the contents of the BST postorder. Use recursion in your implementation! isEmpty ( ) - that is a Boolean function that indicates that the BST is empty or not. You will overload the stream insertion operator << to output a BST in an elegant way. NOTE: Listed below are the algorithms for the traversals.

In-Order Traversal: 1. Traverse the “left” subtree by recursively calling inOrderTraversal() 2. Access the “data” of the current node 3. Traverse the “right” subtree by recursively calling inOrderTraversal() Pre-Order Traversal: 1. Access the “data” of the current node 2. Traverse the “left” subtree by recursively calling preOrderTraversal() 3. Traverse the “right” subtree by recursively calling preOrderTraversal() Post-Order Traversal: 1. Traverse the “left” subtree by recursively calling postOrderTraversal() 2. Traverse the “right” subtree by recursively calling postOrderTraversal() 3. Access the “data” of the current node Let’s say we have the following

BST: 42 / 25 75 / / 10 30 65 100 / / / / 15 70 The in-order traversal would print: 10 15 25 30 42 65 70 75 100 The pre-order traversal would print: 42 25 10 15 30 75 65 70 100 The post-order traversal would print: 15 10 30 25 70 65 100 75 42 // The value in each node is not printed until the values of its children are printed

Explanation / Answer

Following is the for the Binary Search Tree creation and its pre,in and post order traversal.

#######################################################################

#include <iostream>
using namespace std;

// Node class
class Node {
int key;
Node* left;
Node* right;
public:
Node() { key=-1; left=NULL; right=NULL; };
void setKey(int aKey) { key = aKey; };
void setLeft(Node* aLeft) { left = aLeft; };
void setRight(Node* aRight) { right = aRight; };
int Key() { return key; };
Node* Left() { return left; };
Node* Right() { return right; };
};

// Tree class
class Tree {
Node* root;
public:
Tree();
~Tree();
Node* Root() { return root; };
void addNode(int key);
void inOrder(Node* n);
void preOrder(Node* n);
void postOrder(Node* n);
private:
void addNode(int key, Node* leaf);
void freeNode(Node* leaf);
};

// Constructor
Tree::Tree() {
root = NULL;
}

// Destructor
Tree::~Tree() {
freeNode(root);
}

// Free the node
void Tree::freeNode(Node* leaf)
{
if ( leaf != NULL )
{
freeNode(leaf->Left());
freeNode(leaf->Right());
delete leaf;
}
}

// Add a node
void Tree::addNode(int key) {
// No elements. Add the root
if ( root == NULL ) {
cout << "add root node ... " << key << endl;
Node* n = new Node();
n->setKey(key);
root = n;
}
else {
cout << "add other node ... " << key << endl;
addNode(key, root);
}
}

// Add a node (private)
void Tree::addNode(int key, Node* leaf) {
if ( key <= leaf->Key() ) {
if ( leaf->Left() != NULL )
addNode(key, leaf->Left());
else {
Node* n = new Node();
n->setKey(key);
leaf->setLeft(n);
}
}
else {
if ( leaf->Right() != NULL )
addNode(key, leaf->Right());
else {
Node* n = new Node();
n->setKey(key);
leaf->setRight(n);
}
}
}

// Print the tree in-order
// Traverse the left sub-tree, root, right sub-tree
void Tree::inOrder(Node* n) {
if ( n ) {
inOrder(n->Left());
cout << n->Key() << " ";
inOrder(n->Right());
}
}

// Print the tree pre-order
// Traverse the root, left sub-tree, right sub-tree
void Tree::preOrder(Node* n) {
if ( n ) {
cout << n->Key() << " ";
preOrder(n->Left());
preOrder(n->Right());
}
}

// Print the tree post-order
// Traverse left sub-tree, right sub-tree, root
void Tree::postOrder(Node* n) {
if ( n ) {
postOrder(n->Left());
postOrder(n->Right());
cout << n->Key() << " ";
}
}

// Test main program
int main() {
Tree* tree = new Tree();
tree->addNode(42);
tree->addNode(25);
tree->addNode(75);
tree->addNode(10);
tree->addNode(30);
tree->addNode(65);
tree->addNode(100);
tree->addNode(15);
tree->addNode(70);

cout << "In order traversal" << endl;
tree->inOrder(tree->Root());
cout << endl;

cout << "Pre order traversal" << endl;
tree->preOrder(tree->Root());
cout << endl;

cout << "Post order traversal" << endl;
tree->postOrder(tree->Root());
cout << endl;

delete tree;
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.