1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
|
#ifndef TREE_H
#define TREE_H
#include <iostream>
using namespace std;
#include "TreeNode.h"
template <typename T>
class Tree
{
public:
Tree();
void insertNewNode(T); //inserts new node in the tree
void preOrderPrint(); //prints out tree in the order in which it was entered
void inOrderPrint(); //prints out tree in accending order
void postOrderPrint(); //prints out the tree after the order
TreeNode<T>* search(T); //search for node thats data equals the search key and returns the pointer to that node
private:
TreeNode<T> *rootPtr;
bool isEmpty();
//utility functions to make the insert, print, and search functions more understandable
void insertNewNodeUtility(TreeNode<T>**,T);
void preOrderPrintUtility(TreeNode<T>*);
void inOrderPrintUtility(TreeNode<T>*);
void postOrderPrintUtility(TreeNode<T>*);
TreeNode<T>* searchUtility(TreeNode<T>*,T);
};
template <typename T>
Tree<T>::Tree()
{
rootPtr = 0;
}
template <typename T>
void Tree<T>::insertNewNode(T dataIn)
{
insertNewNodeUtility(&rootPtr, dataIn); //calls insert new node function passing refernce of the root node and the data to be inserted in the new node
}
template <typename T>
void Tree<T>::insertNewNodeUtility(TreeNode<T>** temp, T dataIn)
{
if(*temp == 0) //if node is null create a new node with input data
*temp = new TreeNode<T>(dataIn);
else
{
if(dataIn < (*temp)->data) //if input data is less than data in current node
insertNewNodeUtility(&((*temp)->leftPtr),dataIn); //recursive function call with current node's left child as input leaf
else
{
if(dataIn > (*temp)->data) //if input data is greater than data in current node
insertNewNodeUtility(&((*temp)->rightPtr),dataIn); //recursive function call with current node's right child as input leaf
else //if input data is equal to data in current node
cout << dataIn << " is a duplicate value " << endl; //duplicate values ignored
}
}
}
template <typename T>
void Tree<T>::preOrderPrint()
{
preOrderPrintUtility(rootPtr);
}
template <typename T>
void Tree<T>::preOrderPrintUtility(TreeNode<T>* temp)
{
if(temp != 0)
{
cout << temp->data << ' '; //process node
preOrderPrintUtility(temp->leftPtr); //recursive traversal of left subtree
preOrderPrintUtility(temp->rightPtr); //recursive traversal of right subtree
}
}
template <typename T>
void Tree<T>::inOrderPrint()
{
inOrderPrintUtility(rootPtr);
}
template <typename T>
void Tree<T>::inOrderPrintUtility(TreeNode<T>* temp)
{
if(temp != 0)
{
inOrderPrintUtility(temp->leftPtr); //recursive traversal of left subtree
cout << temp->data << ' '; //process node
inOrderPrintUtility(temp->rightPtr); //recursive traversal of right subtree
}
}
template <typename T>
void Tree<T>::postOrderPrint()
{
postOrderPrintUtility(rootPtr);
}
template <typename T>
void Tree<T>::postOrderPrintUtility(TreeNode<T>* temp)
{
if(temp != 0)
{
postOrderPrintUtility(temp->leftPtr); //recursive traversal of left subtree
postOrderPrintUtility(temp->rightPtr); //recursive traversal of right subtree
cout << temp->data << ' '; //process node
}
}
template <typename T>
TreeNode<T>* Tree<T>::search(T key)
{
return searchUtility(rootPtr, key);
}
template <typename T>
TreeNode<T>* Tree<T>::searchUtility(TreeNode<T>* leaf, T key)
{
if(leaf != NULL)
{
if(key == leaf->data)
return leaf;
if(key < leaf->data)
return searchUtility(leaf->leftPtr, key);
else
return searchUtility(leaf->rightPtr, key);
}
else
return NULL;
}
#endif
|
