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;
}
| |