Hello, I am having difficulties figuring out how to implement a driver given the
ID: 3766382 • Letter: H
Question
Hello, I am having difficulties figuring out how to implement a driver given the header files of a BST. Primarly how to create the node to insert at the root, expand the root, and insert nodes at the externals, then how to access each node in inorder, preorder, postorder traversal. Here are my header files:
LinkedBinaryTree.h
#ifndef LINKEDBINARYTREE
#define LINKEDBINARYTREE
#include "BinaryTree.h"
#include "RuntimeException.h"
template <typename E>
class SearchTree // a binary search tree
{
public: // public types
typedef typename E::Key K; // a key
typedef typename E::Value V; // a value
class Iterator; // an iterator/position
public: // public functions
SearchTree() : T(), n(0)
{
T.addRoot(); T.expandExternal(T.root());
} // constructor for super root
int size() const; // number of entries
bool empty() const; // is the tree empty?
Iterator find(const K& k){ // find entry with key k
TPos v = finder(k, root()); // search from virtual root
if (!v.isExternal()) return Iterator(v); // found it
else return end();
} // didn't find it
Iterator insert(const K& k, const V& x) { // insert (k, x)
TPos v = inserter(k, x); return Iterator(v);
}
void erase(const K& k){ // remove key k entry
TPos v = finder(k, root()); // search from virtual root
if (v.isExternal()) // not found?
throw Nonexistentelement("Erase of nonexistent");
erase(v); // remove it
}
void erase(const Iterator& p){ // remove entry at p
eraser(p.v);
}
Iterator begin(){ // iterator to first entry
TPos v = root(); // start at virtual root
while (v.isInternal()) v = v.left(); // find leftmost node
return Iterator(v.parent());
}
Iterator end(){ // iterator to end entry;
return Iterator(T.root());
}
protected: // local utilities
typedef BinaryTree<E> BinaryTree; // linked binary tree
typedef typename BinaryTree::Position TPos; // position in the tree
TPos root() const{ // left child of super root
return T.root().lefT();
}
TPos finder(const K& k, const TPos& v){ // find utility
if (v.isExternal()) return v; // key not found
if (k < (*v).key()) return finder(k, v.left()); // search left subtree
else if ((*v).key() < k) return finder(k, v.right()); // search right subtree
else return v; // found it here
}
TPos inserter(const K& k, const V& x){ // insert utility
TPos v = finder(k, root()); // search from virtual root
while (!v.isExternal()) // key already exists?
v = finder(k, v.right()); // look further
T.expandExternal(v); // add new internal node
(*v).setKey(k); (*v).setValue(x); // set entry
n++; // one more entry
return v; // return insert position
}
TPos eraser(TPos& v){ // erase utility
TPos w;
if (v.left().isExternal()) w = v.left(); // remove from left
else if (v.right().isExternal()) w = v.right(); // remove from right
else { // both internal?
w = v.right(); // go to right subtree
do { w = w.left(); } while (!w.isExternal()); // get leftmost node
TPos u = w.parent();
(*v).setKey((*u).key()); (*v).setValue((*u).value()); // copy w's parent
}
n--; // one less entry
return T.removeAboveExternal(w); // remove w and parent
}
TPos restructure(const TPos& v); // restructure
//throw(BoundaryViolation);
private: // member data
BinaryTree T; // the binary tree
int n; // number of entries
public:
// ... insert Iterator class declaration here
class Iterator {
private:
TPos v; // which entry
public:
Iterator(const TPos& vv) : v(vv) { } // constructor
const E& operator*() const { return *v; } // get entry (read only)
E& operator*() { return *v; } // get entry (read/write)
bool operator==(const Iterator& p) const // are iterators equal?
{
return v.v == p.v.v;
}
Iterator& operator++(){
TPos w = v.right();
if (w.isInternal()) { // have right subtree?
do { v = w; w = w.left(); } // move down left chain
while (w.isInternal());
}
else {
w = v.parent(); // get parent
while (v == w.right()) // move up right chain
{
v = w; w = w.parent();
}
v = w; // and first link to left
}
return *this;
}
friend class SearchTree; // give search tree access
};
};
#endif
BinaryTree.h
#ifndef BINARYTREE_H
#define BINARYTREE_H
#include <list>
using namespace std;
template <typename Elem>
class BinaryTree {
protected:
struct Node { // a node of the tree
Elem elt; // element value
Node* par; // parent
Node* left; // left child
Node* right; // right child
Node() : elt(), par(NULL), left(NULL), right(NULL) { } // constructor
};
public:
// insert Position declaration here...
class Position { // position in the tree
public:
Node* v; // pointer to the node
public:
Position(Node* _v = NULL) : v(_v) { } // constructor
Elem& operator*() // get element
{ return v->elt; }
Position left() const // get left child
{ return Position(v->left); }
Position right() const // get right child
{ return Position(v->right); }
Position parent() const // get parent
{ return Position(v->par); }
bool isRoot() const // root of the tree?
{ return v->par == NULL; }
bool isExternal() const // an external node
{ return v->left == NULL && v->right == NULL; }
friend class BinaryTree; // give tree access
};
typedef std::list<Position> PositionList; // list of positions
public:
BinaryTree(); // constructor
int size() const; // number of nodes
bool empty() const; // is tree empty?
Position root() const // get the root
{ return Position(_root); }
PositionList positions() const // list of nodes
{
PositionList p1;
preorder(_root, p1); // preorder traversal
return PositionList(p1); // return resulting list
}
void addRoot(); // add root to empty tree
void expandExternal(const Position& p); // expand external node
Position removeAboveExternal(const Position& p) // remove p and parent
{
Node* w = p.v; Node* v = w->par; // get p's node and parent
Node* sib = (w == v->left ? v->right : v->left);
if (v == _root) { // child of root?
_root = sib; // ...make sibling root
sib->par = NULL;
}
else {
Node* gpar = v->par; // w's grandparent
if (v == gpar->left) gpar->left = sib; // replace parent by sib }
else gpar->right = sib;
sib->par = gpar;
}
delete w; delete v; // delete removed nodes
n -= 2;
return Position(sib);
}
// housekeeping functions omitted...
protected: // local utilities
void preorder(Node* v, PositionList& p1) const; // preorder utility
private:
Node* _root; // pointer to the root
int n; // number of nodes
};
template <typename Elem>
BinaryTree<Elem>::BinaryTree() // constructor
: _root(NULL), n(0) { }
template <typename Elem>
int BinaryTree<Elem>::size() const // number of nodes
{ return n; }
template <typename Elem>
bool BinaryTree<Elem>::empty() const // is tree empty?
{ return size() == 0; }
template <typename Elem>
void BinaryTree<Elem>::addRoot() // add root to empty tree
{ _root = new Node; n = 1; }
template <typename Elem>
void BinaryTree<Elem>::expandExternal(const Position& p) {
Node* v = p.v; // p's node
v->left = new Node; // add a new left child
v->left->par = v; // v is its parent
v->right = new Node; // and a new right child
v->right->par = v; // v is its parent
n += 2; // two more nodes
}
// preorder traversal
template <typename Elem>
void BinaryTree<Elem>::preorder(Node* v, PositionList& pl) const
{
pl.push_back(Position(v)); // add this node
if (v->left != NULL) // traverse left subtree
preorder(v->left, pl);
if (v->right != NULL) // traverse right subtree
preorder(v->right, pl);
}
#endif
Entry.h
#ifndef ENTRY_H
#define ENTRY_H
// Modified for CSCI 220 Fall 15
template <typename K, typename V>
class Entry { // a (key, value) pair
public: // public functions
typedef K Key; // key type
typedef V Value; // value type
Entry(const K& k = K(), const V& v = V()) // constructor
: _key(k), _value(v) { }
const K& key() const { return _key; } // get key
const V& value() const { return _value; } // get value
void setKey(const K& k) { _key = k; } // set key
void setValue(const V& v) { _value = v; } // set value
private: // private data
K _key; // key
V _value; // value
};
#endif
RuntimeException.h
#ifndef RUNTIMEEXCEPTION_H
#define RUNTIMEEXCEPTION_H
// Modified for CSCI 220 Fall 13
#include <exception>
using namespace std;
class RuntimeException : public exception
{
public:
RuntimeException(const char *err) : exception(err) {}
};
class NonexistentElement : public RuntimeException
{
public:
NonexistentElement(const char *err) : RuntimeException(err) {}
};
class BoundaryViolation : public RuntimeException
{
public:
BoundaryViolation(const char *err) : RuntimeException(err) {}
};
#endif
Explanation / Answer
#include <cstdio>
#include <iostream>
#include <cstring>
#include <stack>
using namespace std;
struct binaryTreeNode
{
binaryTreeNode* left;
binaryTreeNode* right;
int data;
};
void createBinaryTree(binaryTreeNode*& root)
{
int itmp = 0;
cin >> itmp;
if(itmp > 0)
{
if(root == NULL)
{
root = new binaryTreeNode();
}
root->data = itmp;
root->left = 0;
root->right = 0;
createBinaryTree(root->left);
createBinaryTree(root->right);
}
}
int sumBinaryTreeNodeValue(binaryTreeNode* root)
{
int sum = 0;
binaryTreeNode* top = 0;
stack<binaryTreeNode*> bstack;
bstack.push(root);
while(!bstack.empty())
{
top = bstack.top();
bstack.pop();
if(top->left || top->right)
{
sum += top->data;
}
if(top->right)
{
bstack.push(top->right);
}
if(top->left)
{
bstack.push(top->left);
}
}
return sum;
}
void destroyBinaryTree(binaryTreeNode*& root)
{
if(root)
{
if(root->left)
{
destroyBinaryTree(root->left);
}
if(root->right)
{
destroyBinaryTree(root->right);
}
delete root;
}
}
int main()
{
binaryTreeNode* root = 0;
createBinaryTree(root);
cout << sumBinaryTreeNodeValue(root) << endl;
destroyBinaryTree(root);
return 0;
}
Each node in the BST is represented by the below java class:
1
public class Node<T> {
2
public int value;
3
public Node left;
4
public Node right;
5
6
public Node(int value) {
7
this.value = value;
8
}
9
10
}
Lets look at the code in Java for achieving the above logic:
1
public class BinarySearchTree {
2
public Node root;
3
4
public void insert(int value){
5
Node node = new Node<>(value);
6
7
if ( root == null ) {
8
root = node;
9
return;
10
}
11
12
insertRec(root, node);
13
14
}
15
16
private void insertRec(Node latestRoot, Node node){
17
18
if ( latestRoot.value > node.value){
19
20
if ( latestRoot.left == null ){
21
latestRoot.left = node;
22
return;
23
}
24
else{
25
insertRec(latestRoot.left, node);
26
}
27
}
28
else{
29
if (latestRoot.right == null){
30
latestRoot.right = node;
31
return;
32
}
33
else{
34
insertRec(latestRoot.right, node);
35
}
36
}
37
}
38
}
Finding Maximum and Minimum Value in BST
If you have noticed in the above example that the leftmost node has the lowest value and the rightmost node has the highest value. This is due to the sorted nature of the tree.
Using this principle the below methods return us the lowest and highest value in the Binary Search Tree:
1
/**
2
* Returns the minimum value in the Binary Search Tree.
3
*/
4
public int findMinimum(){
5
if ( root == null ){
6
return 0;
7
}
8
Node currNode = root;
9
while(currNode.left != null){
10
currNode = currNode.left;
11
}
12
return currNode.value;
13
}
14
15
/**
16
* Returns the maximum value in the Binary Search Tree
17
*/
18
public int findMaximum(){
19
if ( root == null){
20
return 0;
21
}
22
23
Node currNode = root;
24
while(currNode.right != null){
25
currNode = currNode.right;
26
}
27
return currNode.value;
28
}
Traversing the Binary Search Tree (BST)
Traversing the tree or BST in this case is visiting each of the nodes present in the tree and performing some operation with the value present in the node which in this case will be printing the value present in the node. When we traverse the tree we have to visit the value present in the node, then node’s right sub tree and the left sub tree. Visiting the right and left sub tree will be a recursive operation. The order in which we perform the three operations i.e visiting the value, right sub tree and left sub tree gives rise to three traversal techniques:
1. Inorder Traversal
2. Preorder Traversal
3. Postorder Traversal
Inorder Traversal
In this traversal the left sub tree of the given node is visited first, then the value at the given node is printed and then the right sub tree of the given node is visited. This process is applied recursively all the node in the tree until either the left sub tree is empty or the right sub tree is empty.
Applying the Inorder traversal for the give example we get: 3, 10, 17, 25, 30, 32, 38, 40, 50, 78, 78, 93.
1
/**
2
* Printing the contents of the tree in an inorder way.
3
*/
4
public void printInorder(){
5
printInOrderRec(root);
6
System.out.println("");
7
}
8
9
/**
10
* Helper method to recursively print the contents in an inorder way
11
*/
12
private void printInOrderRec(Node currRoot){
13
if ( currRoot == null ){
14
return;
15
}
16
printInOrderRec(currRoot.left);
17
System.out.print(currRoot.value+", ");
18
printInOrderRec(currRoot.right);
19
}
Preorder traversal
In this traversal the value at the given node is printed first and then the left sub tree of the given node is visited and then the right sub tree of the given node is visited. This process is applied recursively all the node in the tree until either the left sub tree is empty or the right sub tree is empty.
Applying the Preorder traversal for the give example we get: 40, 25, 10, 3, 17, 32, 30, 38, 78, 50, 78, 93.
1
/**
2
* Printing the contents of the tree in a Preorder way.
3
*/
4
public void printPreorder() {
5
printPreOrderRec(root);
6
System.out.println("");
7
}
8
9
/**
10
* Helper method to recursively print the contents in a Preorder way
11
*/
12
private void printPreOrderRec(Node currRoot) {
13
if (currRoot == null) {
14
return;
15
}
16
System.out.print(currRoot.value + ", ");
17
printPreOrderRec(currRoot.left);
18
printPreOrderRec(currRoot.right);
19
}
Postorder Traversal
In this traversal the left sub tree of the given node is traversed first, then the right sub tree of the given node is traversed and then the value at the given node is printed. This process is applied recursively all the node in the tree until either the left sub tree is empty or the right sub tree is empty.
Applying the Postorder traversal for the give example we get: 3, 17, 10, 30, 38, 32, 25, 50, 93, 78, 78, 40.
1
/**
2
* Printing the contents of the tree in a Postorder way.
3
*/
4
public void printPostorder() {
5
printPostOrderRec(root);
6
System.out.println("");
7
}
8
9
/**
10
* Helper method to recursively print the contents in a Postorder way
11
*/
12
private void printPostOrderRec(Node currRoot) {
13
if (currRoot == null) {
14
return;
15
}
16
printPostOrderRec(currRoot.left);
17
printPostOrderRec(currRoot.right);
18
System.out.print(currRoot.value + ", ");
19
20
}
The complete code which builds the tree for the example explained in this code and prints the maximum, minimum value, inorder traversal, preorder traversal and post order traversal can be found below:
view source
print?
1
/**
2
* Represents a node in the Binary Search Tree.
3
*/
4
public class Node<T> {
5
//The value present in the node.
6
public int value;
7
8
//The reference to the left subtree.
9
public Node left;
10
11
//The reference to the right subtree.
12
public Node right;
13
14
public Node(int value) {
15
this.value = value;
16
}
17
18
}
19
20
/**
21
* Represents the Binary Search Tree.
22
*/
23
public class BinarySearchTree {
24
25
//Refrence for the root of the tree.
26
public Node root;
27
28
public BinarySearchTree insert(int value) {
29
Node node = new Node<>(value);
30
31
if (root == null) {
32
root = node;
33
return this;
34
}
35
36
insertRec(root, node);
37
return this;
38
}
39
40
private void insertRec(Node latestRoot, Node node) {
41
42
if (latestRoot.value > node.value) {
43
44
if (latestRoot.left == null) {
45
latestRoot.left = node;
46
return;
47
} else {
48
insertRec(latestRoot.left, node);
49
}
50
} else {
51
if (latestRoot.right == null) {
52
latestRoot.right = node;
53
return;
54
} else {
55
insertRec(latestRoot.right, node);
56
}
57
}
58
}
59
60
/**
61
* Returns the minimum value in the Binary Search Tree.
62
*/
63
public int findMinimum() {
64
if (root == null) {
65
return 0;
66
}
67
Node currNode = root;
68
while (currNode.left != null) {
69
currNode = currNode.left;
70
}
71
return currNode.value;
72
}
73
74
/**
75
* Returns the maximum value in the Binary Search Tree
76
*/
77
public int findMaximum() {
78
if (root == null) {
79
return 0;
80
}
81
82
Node currNode = root;
83
while (currNode.right != null) {
84
currNode = currNode.right;
85
}
86
return currNode.value;
87
}
88
89
/**
90
* Printing the contents of the tree in an inorder way.
91
*/
92
public void printInorder() {
93
printInOrderRec(root);
94
System.out.println("");
95
}
96
97
/**
98
* Helper method to recursively print the contents in an inorder way
99
*/
100
private void printInOrderRec(Node currRoot) {
101
if (currRoot == null) {
102
return;
103
}
104
printInOrderRec(currRoot.left);
105
System.out.print(currRoot.value + ", ");
106
printInOrderRec(currRoot.right);
107
}
108
109
/**
110
* Printing the contents of the tree in a Preorder way.
111
*/
112
public void printPreorder() {
113
printPreOrderRec(root);
114
System.out.println("");
115
}
116
117
/**
118
* Helper method to recursively print the contents in a Preorder way
119
*/
120
private void printPreOrderRec(Node currRoot) {
121
if (currRoot == null) {
122
return;
123
}
124
System.out.print(currRoot.value + ", ");
125
printPreOrderRec(currRoot.left);
126
printPreOrderRec(currRoot.right);
127
}
128
129
/**
130
* Printing the contents of the tree in a Postorder way.
131
*/
132
public void printPostorder() {
133
printPostOrderRec(root);
134
System.out.println("");
135
}
136
137
/**
138
* Helper method to recursively print the contents in a Postorder way
139
*/
140
private void printPostOrderRec(Node currRoot) {
141
if (currRoot == null) {
142
return;
143
}
144
printPostOrderRec(currRoot.left);
145
printPostOrderRec(currRoot.right);
146
System.out.print(currRoot.value + ", ");
147
148
}
149
}
150
151
public class BinarySearchTreeDemo {
152
153
public static void main(String[] args) {
154
BinarySearchTree bst = new BinarySearchTree();
155
bst .insert(40)
156
.insert(25)
157
.insert(78)
158
.insert(10)
159
.insert(3)
160
.insert(17)
161
.insert(32)
162
.insert(30)
163
.insert(38)
164
.insert(78)
165
.insert(50)
166
.insert(93);
167
System.out.println("Inorder traversal");
168
bst.printInorder();
169
170
System.out.println("Preorder Traversal");
171
bst.printPreorder();
172
173
System.out.println("Postorder Traversal");
174
bst.printPostorder();
175
176
System.out.println("The minimum value in the BST: " + bst.findMinimum());
177
System.out.println("The maximum value in the BST: " + bst.findMaximum());
178
179
}
180
}
1
public class Node<T> {
2
public int value;
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.