#include <stdio.h> #include <stdlib.h> #include <stdbool.h> typedef struct BSTNode{ int data; struct BSTNode * lchild; struct BSTNode * rchild; }BSTNode,* BSTree; BSTNode * InitNode(int data){ BSTNode * node = (BSTNode *)malloc(sizeof(BSTNode)); if(node==NULL)exit(0); node->data=data; node->lchild=NULL; node->rchild=NULL; return node; } bool Insert(BSTree *tree,int data){ BSTNode * node = InitNode(data); if(*tree == NULL){ *tree= node; return true; } if(data<(*tree)->data){ Insert(&((*tree)->lchild),data); }else{ Insert(&((*tree)->rchild),data); } } void VisitInOrder(BSTree * tree){ if(*tree==NULL) { printf("This is a invalid tree."); return; } if((*tree)->lchild !=NULL){ VisitInOrder(&((*tree)->lchild)); } printf("%d \n",(*tree)->data); if((*tree)->rchild !=NULL){ VisitInOrder(&((*tree)->rchild)); } } BSTNode * Query(BSTree tree,int data){ if(tree==NULL)return NULL; if(tree->data == data){ return tree; } if(data<tree->data) { return Query(tree->lchild,data); } else { return Query(tree->rchild,data); } } BSTNode * FindParent(BSTNode * tree,BSTNode * node){ if(tree==NULL || node == NULL)return NULL; if((tree->lchild && tree->lchild==node)||(tree->rchild && tree->rchild == node)){ return tree; } if(tree->lchild)return FindParent(tree->lchild,node); if(tree->rchild)return FindParent(tree->rchild,node); } bool DeleteData(BSTree* tree,int data){ if(tree==NULL || *tree == NULL)return false; BSTNode * current = Query(*tree,data); if(current==NULL){ printf("Data does not exist"); return false; } BSTNode * q=NULL; BSTNode * s=NULL; if(current->lchild==NULL && current->rchild==NULL){ if(current== *tree){//如果是根节点,直接赋值为空树即可。 *tree=NULL; free(current); return; } BSTNode * p = FindParent(*tree ,current);//如果是叶子节点,需要找到父节点并把其child指针置空。 if(p && p->lchild == current){ p->lchild=NULL; } if(p && p->rchild==current){ p->rchild=NULL; } free(current); }else if(current->lchild!=NULL && current->rchild==NULL){ q=current->lchild; current->data=q->data; current->lchild=q->lchild; current->rchild=q->rchild; free(q); }else if(current->lchild==NULL && current->rchild!=NULL){ q=current->rchild; current->data=q->data; current->lchild=q->lchild; current->rchild=q->rchild; free(q); }else{ s=current->lchild; q=current; while(s->rchild){ q=s; s=s->rchild; } current->data=s->data; if(current!=q){//根节点下有多层 q->rchild=s->lchild; }else{//根节点下只有一层 q->lchild=s->lchild; } free(s); } } int main() { BSTree tree= NULL; int data=-1; printf("Entering data to create a node:\n"); scanf("%d",&data); while(data!=-1){ Insert(&tree,data); printf("Entering data to create a node:\n"); scanf("%d",&data); } VisitInOrder(&tree); printf("enter a char to delete:\n"); scanf("%d",&data); while(data!=-1){ bool result = DeleteData(&tree,data); printf("delete result:%d\n",result); VisitInOrder(&tree); printf("enter a char to delete:\n"); scanf("%d",&data); } return 0; }
标签:lchild,current,C语言,tree,二叉,链表,rchild,NULL,data From: https://www.cnblogs.com/quota/p/17441116.html