117 lines
2.1 KiB
C
117 lines
2.1 KiB
C
/*
|
|
* Author: Walter
|
|
* Student ID: 1930006025
|
|
* programming_assignment_2
|
|
*/
|
|
|
|
#include "BST.h"
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
|
|
Node *insertNode(Node **proot, int x) {
|
|
Node **tmpNode;
|
|
|
|
/* find the position needs to be insert */
|
|
tmpNode = proot;
|
|
while (*tmpNode) {
|
|
if (x < (*tmpNode)->key) {
|
|
tmpNode = &(*tmpNode)->left;
|
|
} else if (x > (*tmpNode)->key) {
|
|
tmpNode = &(*tmpNode)->right;
|
|
} else {
|
|
/* same key exists */
|
|
return NULL;
|
|
}
|
|
}
|
|
|
|
/* create node */
|
|
*tmpNode = (Node *)malloc(sizeof(Node));
|
|
if (tmpNode == NULL) {
|
|
fprintf(stderr, "Can not allocate new space for node\n");
|
|
exit(1);
|
|
}
|
|
|
|
/* copy value */
|
|
(*tmpNode)->key = x;
|
|
(*tmpNode)->left = (*tmpNode)->right = NULL;
|
|
|
|
return *tmpNode;
|
|
}
|
|
|
|
Node *findNode(Node *root, int x) {
|
|
while (root) {
|
|
/* find in children */
|
|
if (x < root->key) {
|
|
root = root->left;
|
|
} else if (x > root->key) {
|
|
root = root->right;
|
|
} else {
|
|
/* equal */
|
|
return root;
|
|
}
|
|
}
|
|
|
|
/* not found */
|
|
return NULL;
|
|
}
|
|
|
|
Node *deleteNode(Node **proot, int x) {
|
|
Node **rMin, **delNode, *freeNode;
|
|
|
|
/* find the node needs to be delete */
|
|
delNode = proot;
|
|
while (*delNode) {
|
|
if (x < (*delNode)->key) {
|
|
delNode = &(*delNode)->left;
|
|
} else if (x > (*delNode)->key) {
|
|
delNode = &(*delNode)->right;
|
|
} else {
|
|
/* found */
|
|
break;
|
|
}
|
|
}
|
|
/* check not found */
|
|
if (!(*delNode)) {
|
|
return NULL;
|
|
}
|
|
|
|
if ((*delNode)->left && (*delNode)->right) {
|
|
/* two children, find the right min and replace */
|
|
rMin = &((*delNode)->right);
|
|
while ((*rMin)->left) {
|
|
rMin = &(*rMin)->left;
|
|
}
|
|
|
|
/* replace */
|
|
(*delNode)->key = (*rMin)->key;
|
|
|
|
/* now let's delete rMin */
|
|
delNode = rMin;
|
|
}
|
|
|
|
/* delete delNode, freeNode is the one needs to be free,
|
|
* here delNode will not have two children */
|
|
freeNode = *delNode;
|
|
if ((*delNode)->left) {
|
|
*delNode = (*delNode)->left;
|
|
} else if ((*delNode)->right) {
|
|
*delNode = (*delNode)->right;
|
|
} else {
|
|
/* no child */
|
|
*delNode = NULL;
|
|
}
|
|
|
|
return freeNode;
|
|
}
|
|
|
|
void destroyTree(Node *root) {
|
|
/* end situation */
|
|
if (root == NULL) {
|
|
return;
|
|
}
|
|
destroyTree(root->left);
|
|
destroyTree(root->right);
|
|
free(root);
|
|
return;
|
|
}
|