#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char line[100]; /* buffer for input data */
int n; /* control for loop */
struct node {
char *data; /* word for this tree */
struct node *left; /* tree to the left */
struct node *right; /* tree to the right */
};
struct node *root = NULL;
char *saveString();
void enter();
void scan();
void printTree();
struct node *findTree();
void deleteTree();
int deepChild();
struct node *percolateDown();
struct node *searchParent();
void complexDelete();
void complexDeleteR();
struct node *searchParentL();
int main(int argc, char *argv[]) {
struct node *cur_node; /* node to delete */
printf("Enter file name\n");
fgets(line, sizeof(line), stdin);
line[strlen(line) - 1] = '\0';
scan(line);
printTree(root);
printf("Enter word to delete\n");
fgets(line, sizeof(line), stdin);
line[strlen(line) - 1] = '\0';
cur_node = root;
cur_node = findTree(cur_node, line);
if (cur_node == NULL ) {
printf("Don't find word");
} else {
printf("Find! word\n");
printTree(root);
deleteTree(cur_node, root);
printTree(root);
}
return 0;
}
char *saveString(char *st) {
char *newst; /* char array for copy */
newst = malloc((unsigned) (strlen(st) + 1));
if (newst == NULL ) {
fprintf(stderr,"out of memory\n");
exit(8);
}
strcpy(newst, st);
return newst;
}
void enter(struct node **node, char *st) {
int res; /* result of compare data with st */
if ((*node) == NULL ) {
(*node) = malloc(sizeof(struct node));
if ((*node) == NULL ) {
fprintf(stderr,"out of memory\n");
exit(8);
}
(*node)->data = saveString(st);
(*node)->left = NULL;
(*node)->right = NULL;
}
res = strcmp((*node)->data, st);
/* if already contain word return */
if (res == 0) {
return;
} else if (res < 0) {
enter(&(*node)->right, st);
} else {
enter(&(*node)->left, st);
}
}
void scan(char *li) {
char word[100]; /* char array for each word */
int ch; /* temporary char and used int for EOF */
FILE *in_file; /* file from user */
in_file = fopen(li, "r");
if (in_file == NULL ) {
fprintf(stderr,"unable to open file %s\n",li);
exit(8);
}
while (1) {
while (1) {
ch = fgetc(in_file);
if (ch != ' ' || ch == EOF)
break;
}
if (ch == EOF)
break;
word[0] = ch;
for (n = 1; n < 100; ++n) {
ch = fgetc(in_file);
if (ch == ' ' || ch == EOF)
break;
word[n] = ch;
}
word[n] = '\0';
enter(&root, word);
}
fclose(in_file);
}
void printTree(struct node *top) {
if (top == NULL )
return;
printTree(top->left);
printf("%s ", top->data);
printTree(top->right);
}
struct node *findTree(struct node *cur, char *w) {
int resu = 1;
if (cur != NULL ) {
resu = strcmp(cur->data, w);
if (resu < 0) {
return findTree(cur->right, w);
} else if (resu > 0) {
return findTree(cur->left, w);
} else {
return cur;
}
} else {
return NULL ;
}
}
void deleteTree(struct node *cur, struct node *sroot) {
struct node *childl = NULL;
struct node *childr = NULL;
struct node *parent = NULL;
printf("%s %s\n", cur->data, sroot->data);
if (strcmp(sroot->data, cur->data) == 0) {
if (sroot->left != NULL )
childl = sroot->left;
if (sroot->right != NULL )
childr = sroot->right;
if (childl == NULL && childr == NULL ) {/* if block 1 */
parent = searchParentL(sroot,root);
if(parent->left==sroot)
parent->left = NULL;
if(parent->right==sroot)
parent->right = NULL;
free(sroot);
sroot = NULL;
} else if (childl == NULL ) {
if(childr->left == NULL&&childr->right == NULL){
sroot->data = childr->data;
free(childr);
sroot->right = NULL;
}else{
complexDeleteR(childr,sroot);
}
} else if (childr == NULL ) {
sroot->data = childl->data;
if(childl->left==NULL&&childl->right==NULL)
sroot->left = NULL;
if(childl->left!=NULL){
sroot->left = childl->left;
}
if(childl->right!=NULL){
sroot->right = childl->right;
if(childl->left==NULL)
sroot->left = NULL;
}
free(childl);
} else {/* block 1 childl&childr != NULL*/
if (childl->left != NULL && childl->right != NULL ) {/* if block 2 */
if (childr->left == NULL && childr->right == NULL ) {
sroot->data = childr->data;
sroot->right = NULL;
free(childr);
childr = NULL;
} else if (childr->left == NULL ) {
sroot->data = childr->data;
sroot->right = childr->right;
free(childr);
childr = NULL;
} else if (childr->right == NULL ) {
sroot->data = childr->data;
sroot->right = childr->left;
free(childr);
childr = NULL;
}
} else if (childl->left == NULL && childl->right == NULL ) {
sroot->data = childl->data;
sroot->left = NULL;
free(childl);
childl = NULL;
} else if (childl->left == NULL ) {
if(childl->right->left == NULL&&childl->right->right == NULL){
sroot->data = childl->right->data;
free(childl->right);
childl->right = NULL;
}else{
complexDelete(childl,sroot);
}
} else if (childl->right == NULL ) {
sroot->data = childl->data;
sroot->left = childl->left;
free(childl);
childl = NULL;
} else {/* childl & childr full *//* block 2 */
complexDelete(childl,sroot);
}/* end if block 2 */
}/* end if block 1 */
} else if (strcmp(sroot->data, cur->data) > 0) {
deleteTree(cur, sroot->left);
} else if (strcmp(sroot->data, cur->data) < 0) {
deleteTree(cur, sroot->right);
}
}
int deepChild(struct node *cur) {
struct node *childl = NULL;
struct node *childr = NULL;
int deepcount = 0;
int leftcount = 0;
int rightcount = 0;
if (cur->left != NULL )
childl = cur->left;
if (cur->right != NULL )
childr = cur->right;
if (childl == NULL && childr == NULL ) {
return 0;
} else {
if (childl != NULL || childr != NULL )
++deepcount;
if (childl != NULL )
leftcount = deepChild(childl);
if (childr != NULL )
rightcount = deepChild(childr);
if (leftcount >= rightcount)
deepcount += leftcount;
else
deepcount += rightcount;
return deepcount;
}
}
struct node *percolateDown(struct node *cur) {
struct node *childr = NULL;
if (cur->right != NULL )
childr = cur->right;
if (childr == NULL ) {
return cur;
} else {
return (percolateDown(childr));
}
}
struct node *searchParent(struct node *cur, struct node *ssroot) {
struct node *childr = NULL;
if (ssroot->right != NULL )
childr = ssroot->right;
if (childr == cur) {
return ssroot;
} else {
return (searchParent(cur, childr));
}
}
void complexDelete(struct node *childl, struct node *sroot) {
struct node *pchild = NULL;
struct node *schild = NULL;
struct node *pchildl = NULL;
int deepl = 0;
int deepr = 0;
/*deepl = deepChild(childl);
deepr = deepChild(childr);
if(deepl>=deepr)
pchild = percolateDown(childr);
else*/
pchild = percolateDown(childl);
schild = searchParent(pchild, childl);
if (pchild->left != NULL ) {/* if block 3 */
pchildl = pchild->left;
if (schild != childl) {
sroot->data = pchild->data;
schild->right = pchildl;
free(pchild);
pchild = NULL;
} else {/* schild == childl */
sroot->data = pchild->data;
childl->right = pchildl;
free(pchild);
pchild = NULL;
}
} else {/* block 3 pchild->left == NULL*/
if (schild != childl) {
sroot->data = pchild->data;
schild->right = NULL;
free(pchild);
pchild = NULL;
} else {/* schild == childl */
sroot->data = pchild->data;
childl->right = NULL;
free(pchild);
pchild = NULL;
}
}/* end if block 3 */
}
void complexDeleteR(struct node *childr, struct node *sroot){
struct node *pchild = NULL;
struct node *pchildl = NULL;
struct node *schild = NULL;
pchild = percolateDown(childr);
if(pchild==childr){
if (pchild->left != NULL ) {/* if block 3 */
pchildl = pchild->left;
sroot->data = pchild->data;
sroot->left = pchildl;
sroot->right = NULL;
free(pchild);
pchild = NULL;
} else {/* block 3 pchild->left == NULL*/
sroot->data = pchild->data;
sroot->right = NULL;
free(pchild);
pchild = NULL;
}/* end if block 3 */
}else{
schild = searchParentL(sroot,root);
schild->left = childr;
free(sroot);
sroot = NULL;
}
}
struct node *searchParentL(struct node *cur, struct node *sroot){
struct node *childl = NULL;
struct node *childr = NULL;
int res =1;
if(sroot->left!=NULL)
childl = sroot->left;
if(sroot->right!=NULL)
childr = sroot->right;
res = strcmp(sroot->data,cur->data);
if(res<0){
res = strcmp(childr->data,cur->data);
if(res==0){
return sroot;
}else{
return searchParentL(cur,childr);
}
}else if(res>0){
res = strcmp(childl->data,cur->data);
if(res==0){
return sroot;
}else{
return searchParentL(cur,childl);
}
}
}
คือ ผมเอง ลองไปแค่ file เดียวเอง ยังไม่ค่อย แน่ใจ เท่าไหร่
แต่ ที่รู้คือ tree นี่ยาก กว่า linked_list และ double linked_list เยอะ มาก ๆ
