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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
|
/*
* intBST.cpp
*
* Created on: Jul 1, 2013
*/
#include "intBST.h"
#include<iostream>
using namespace std;
//***********************************************
//Function inserts a node into tree
//
//param- 1- node Ptr that is already in the tree
//param- 2- node that needs to be inserted to tree
//***********************************************
void biTree::insert(treeNode *&nodePtr, treeNode *&newNode){
if(nodePtr ==NULL)
nodePtr = newNode; //insert the node.
else if(newNode->data < nodePtr->data)
insert(nodePtr->left, newNode);
else
insert(nodePtr->right, newNode);
}
//***********************************************
//Function creates new nodes to tree
//
//param- 1- value to be store in treeNode
//***********************************************
void biTree::insertNode(int num){
treeNode *newNode; //pointer to new data
//create a node and store it in num
newNode = new treeNode;
newNode->data= num;
newNode->left = newNode->right = NULL;
//insert node
insert(root, newNode);
}
//***********************************************
//Function is called by destructor to delete nodes
//
//param- 1- tree to be deleted
//***********************************************
void biTree::destroySubTree(treeNode *nodePtr){
if(nodePtr){
if(nodePtr->left)
destroySubTree(nodePtr->left);
}
if(nodePtr->right)
destroySubTree(nodePtr->left);
delete nodePtr;
}
//***********************************************
//Function finds a node in tree
//
//param- 1- num we are serching for
//return- if node is found true, if not false.
//***********************************************
bool biTree::searchNode(int num){
treeNode *nodePtr = root;
while(nodePtr){
if(nodePtr->data ==num)
return true;
else if(num < nodePtr->data)
nodePtr= nodePtr->left;
else
nodePtr= nodePtr->right;
}
return false;
}
//***********************************************
//Function that is public and calls deleteNode
//
//param- 1- data to be removed
//***********************************************
void biTree::remove(int num){
deleteNode(num, root);
}
//***********************************************
//Function deletes a node, but not the whole tree
//
//param- 1- number/data we are looking to delete
//param- 2- the tree
//***********************************************
void biTree::deleteNode(int num, treeNode *&nodePtr){
if(num < nodePtr->data)
deleteNode(num, nodePtr->left);
else if(num > nodePtr->data)
deleteNode(num, nodePtr->right);
else
makeDeletion(nodePtr);
}
//***********************************************
//Function moves pointer to the node being removed/deleted
//
//param- 1- node that is being deleted
//***********************************************
void biTree::makeDeletion(treeNode*& nodePtr){
treeNode *buffer; //buffer locations to store data while moving ptr's around
if(nodePtr ==NULL)
cout<<"ERROR:: Node is empty, removal is not possible from an empty node. \n";
//if right empty, move child on left in it's place
else if(nodePtr->right ==NULL){
buffer = nodePtr;
nodePtr = nodePtr->left;
delete buffer;
}
//if left empty, move child on right in it's place
else if(nodePtr->left ==NULL){
buffer = nodePtr;
nodePtr = nodePtr->right;
delete buffer;
}
//Case when node has 2 children
else{
buffer = nodePtr->right;
while(buffer->left)
buffer = buffer->left;
buffer->left = nodePtr->left;
buffer = nodePtr;
nodePtr = nodePtr->right;
delete buffer;
}
}
//***********************************************
//Function displays list InOrder
//
//param- 1- tree is passed to the function
//***********************************************
void biTree::displayInOrder(treeNode* nodePtr) const{
if(nodePtr){
displayInOrder(nodePtr->left);
cout<< nodePtr->data <<endl;
displayInOrder(nodePtr->right);
}
}
//***********************************************
//Function displays the list in PreOrder
//
//param- 1- tree that needs to be displayed.
//***********************************************
void biTree::displayPreOrder(treeNode *nodePtr)const{
if(nodePtr){
cout<< nodePtr->data <<endl;
displayPreOrder(nodePtr->left);
displayPreOrder(nodePtr->right);
}
}
//***********************************************
//Function displays list in postOrder
//
//param- 1- tree to be displayed is passed
//***********************************************
void biTree::displayPostOrder(treeNode* nodePtr)const{
if(nodePtr){
displayPostOrder(nodePtr->left);
displayPostOrder(nodePtr->right);
cout<< nodePtr->data <<endl;
}
}
int biTree::leavesCount(treeNode* node)const{
if(node == NULL)
return 0;
if(node->left == NULL && node->right==NULL)
return 1;
else
return leavesCount(node->left)+
leavesCount(node->right);
}
int biTree::nodeCount(treeNode* node)const{
if (node == 0)
return 0;
return 1 + nodeCount(node->left) + nodeCount(node->right);
}
|
