i'm having a problem implementing a binary search tree delete operation.
my logic for the deleteNode operation is this:
if value to delete is greater than value at the node, try do delete node at the right
else if value to delete is less than value at node, try do delete node to the left
else if value is equal, perform delete.
the 3 general cases are:
1.node is a leaf node (left & right child are null)
2.node has exactly one child that is null
3.node has two children (left & right child are not null)
now i am having a problem with implementing case 3,
this is how i want to implement case 3:
1.find the maximum at the left of the node to be deleted
2.if the maximum has no children
---i have 2 cases for this:
----a.maximum node is direct child (a left child)of the node i want to delete: if the maximum node is a child of the 'node to be deleted', replace that node with the maximum node found then assign the right child of the new node to the previous right child.
----b.maximum node is not a direct child of the node i want to delete: else if the maximum node is not a child of the node to be deleted, assign also the left child of the new node to the previous right child.
this is where i'm getting problem because if LINE 161 is not commented i am getting an infinite loop when printing the tree. but if i comment it out, two values are deleted-- the node that i want to delete and the node with the smallest value.
3. if the maximum has a left child- (i think there is no problem here)
can someone help me trace my mistake? thanks in advance.
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
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
|
#include<stdio.h>
#include<stdlib.h>
struct charTreeNode{
char data;
struct charTreeNode *left;
struct charTreeNode *right;
};
typedef struct charTreeNode CharTreeNode;
typedef CharTreeNode *CharTreeNodePtr;
void insertTreeNode(CharTreeNodePtr *rootPtr,char value);
void inOrder(CharTreeNodePtr *rootPtr);
void preOrder(CharTreeNodePtr *rootPtr);
void postOrder(CharTreeNodePtr *rootPtr);
//void deleteTreeNode(CharTreeNodePtr *rootPtr, char value);
void deleteNode(CharTreeNodePtr *rootPtr,char value);
CharTreeNodePtr findMax(CharTreeNodePtr *rootPtr);
int main(){
CharTreeNodePtr rootPtr= NULL;
insertTreeNode(&rootPtr,'d');
insertTreeNode(&rootPtr,'a');
insertTreeNode(&rootPtr,'c');
insertTreeNode(&rootPtr,'z');
insertTreeNode(&rootPtr,'m');
insertTreeNode(&rootPtr,'k');
insertTreeNode(&rootPtr,'j');
insertTreeNode(&rootPtr,'l');
insertTreeNode(&rootPtr,'n');
inOrder(&rootPtr);
printf("\n");
preOrder(&rootPtr);
printf("\n");
postOrder(&rootPtr);
printf("\n");
deleteNode(&rootPtr, 'm');
inOrder(&rootPtr);
printf("\n");
preOrder(&rootPtr);
printf("\n");
postOrder(&rootPtr);
printf("\n");
deleteNode(&rootPtr, 'k');
inOrder(&rootPtr);
printf("\n");
preOrder(&rootPtr);
printf("\n");
postOrder(&rootPtr);
printf("\n");
deleteNode(&rootPtr, 'z');
inOrder(&rootPtr);
printf("\n");
preOrder(&rootPtr);
printf("\n");
postOrder(&rootPtr);
printf("\n");
deleteNode(&rootPtr, 'a');
inOrder(&rootPtr);
printf("\n");
preOrder(&rootPtr);
printf("\n");
postOrder(&rootPtr);
printf("\n");
return 0;
}
void insertTreeNode(CharTreeNodePtr *rootPtr,char value){
if(*rootPtr == NULL){
*rootPtr = malloc(sizeof(CharTreeNode));
if(*rootPtr != NULL){
(*rootPtr)->data = value;
(*rootPtr)->left = NULL;
(*rootPtr)->right = NULL;
}else{
printf("Error: failed to allocate memory");
}
}
else{
if(value < (*rootPtr)->data){
insertTreeNode(&((*rootPtr)->left),value);
}
else if(value > (*rootPtr)->data){
insertTreeNode(&((*rootPtr)->right),value);
}
else{
printf("dup");
}
}
}
void inOrder(CharTreeNodePtr *rootPtr){
if(*rootPtr != NULL){
inOrder(&((*rootPtr)->left));
printf("%c",(*rootPtr)->data);
inOrder(&((*rootPtr)->right));
}
}
void preOrder(CharTreeNodePtr *rootPtr){
if(*rootPtr != NULL){
printf("%c",(*rootPtr)->data);
preOrder(&((*rootPtr)->left));
preOrder(&((*rootPtr)->right));
}
}
void postOrder(CharTreeNodePtr *rootPtr){
if(*rootPtr != NULL){
postOrder(&((*rootPtr)->left));
postOrder(&((*rootPtr)->right));
printf("%c",(*rootPtr)->data);
}
}
void deleteNode(CharTreeNodePtr *rootPtr,char value){
if(*rootPtr != NULL){
if(value == (*rootPtr)->data){
if((*rootPtr)->left == NULL && (*rootPtr)->right == NULL){
CharTreeNodePtr newPtr = (*rootPtr);
(*rootPtr) = NULL;
free(newPtr);
}
else if((*rootPtr)->right == NULL){
CharTreeNodePtr newPtr = (*rootPtr);
(*rootPtr) = (*rootPtr)->left;
free(newPtr);
}
else if((*rootPtr)->left == NULL){
CharTreeNodePtr newPtr = (*rootPtr);
(*rootPtr) = (*rootPtr)->right;
free(newPtr);
}
else{
CharTreeNodePtr newPtr;
newPtr = (*rootPtr)->left;
while(newPtr->right != NULL){
newPtr = newPtr->right;
}
//newPtr = findMax(&((*rootPtr)->left));
//if max is a leaf node
if((newPtr->left == NULL) && (newPtr->right == NULL)){
//if max node is a child of root node
if(newPtr == (*rootPtr)->left){
CharTreeNodePtr tempPtr;
tempPtr = (*rootPtr);
(*rootPtr) = newPtr;
newPtr = NULL;
(*rootPtr)->right = tempPtr->right;
free(tempPtr);
}
else if(newPtr != (*rootPtr)->left){//else if max node is not a child of root node
/*PROOOOOOBLEM*/
CharTreeNodePtr tempPtr;
tempPtr = (*rootPtr);
(*rootPtr) = newPtr;
(*rootPtr)->right = tempPtr->right;
//(*rootPtr)->left = tempPtr->left;
newPtr = NULL;
free(tempPtr);
}
}
else if((newPtr->left != NULL) || (newPtr->right != NULL)){//if max has a child
//if maxnode is a child of root node
if((*rootPtr)->left == newPtr){
CharTreeNodePtr tempPtr;
tempPtr = (*rootPtr);
(*rootPtr) = newPtr;
(*rootPtr)->right = tempPtr->right;
(*rootPtr)->left = newPtr->left;
newPtr = NULL;
free(tempPtr);
}
else{//else if max node is not a child of root node
CharTreeNodePtr tempPtr;
tempPtr = (*rootPtr);
(*rootPtr) = newPtr;
(*rootPtr)->right = tempPtr->right;
(*rootPtr)->left = tempPtr->left;
newPtr = newPtr->left;
free(tempPtr);
}
}
}
}
else if(value < (*rootPtr)->data){
deleteNode(&(*rootPtr)->left,value);
}
else if(value > (*rootPtr)->data){
deleteNode(&(*rootPtr)->right,value);
}
}
}
CharTreeNodePtr findMax(CharTreeNodePtr *rootPtr){
CharTreeNodePtr temp = *rootPtr;
while((temp->right != NULL)){
temp = temp->right;
}
return temp;
}
|
