数据结构-二叉查找树

Binary search tree

Posted by xuepro on November 10, 2017

           50
/      \
30         70
/  \       /   \
20    40    60    80

/* copyright by hwdong*/

#include <stdio.h>

#include <stdlib.h>

#include <malloc.h>

typedef int EType;

typedef struct  binode{
EType data;
struct  binode *lchild,*rchild;
}BiTNode;

BiTNode *newNode(EType e ){
BiTNode *p  = (BiTNode *)malloc(sizeof(BiTNode));
p->data = e;
p->lchild = p->rchild = 0;
return p;
}

BiTNode* SearchBST(BiTNode* T, EType e){
if (!T) return 0; //递归出口

if (T->data == e) return T;      //处理根

if (e < T->data)                 //左子树

return SearchBST(T->lchild, e);

else                             //右子树

return SearchBST(T->rchild, e);
}

BiTNode* InsertBST( BiTNode* T, EType e){
if(T==0) return newNode(e);

if (e<T->data)          //左子树

T->lchild = InsertBST(T->lchild, e);

else if (e>T->data)     //右子树

T->rchild = InsertBST(T->rchild, e);

return T;
}

void Delete( BiTNode* p) ;

BiTNode* DeleteBST( BiTNode* T, EType e){
if(T==0) return T;
if (e<T->data)          //左子树

T->lchild = DeleteBST(T->lchild, e);

else if (e>T->data)     //右子树

T->rchild = DeleteBST(T->rchild, e);

else{ //T就是要删除的结点

if(T->rchild==0){ //左孩子顶替他

BiTNode *q = T->lchild;
free(T);
return q;
}
else  if(T->lchild==0) {
BiTNode *q = T->rchild;
free(T);
return q;
}
else{
Delete(T); return T;
}
}
}

void Delete( BiTNode* p) {
BiTNode* q = p,*s = p->lchild;
while (s->rchild) {
q = s; s = s->rchild;
}
p->data = s->data;
if (q != p)
q->rchild=s->lchild;
else
q->lchild=s->lchild;
free(s);
return;
}

void IOT(BiTNode* T)
{
if (T!= 0){
IOT(T->lchild);
printf("%d ", T->data);
IOT(T->rchild);
}
}

int main()
{
BiTNode* root = NULL;
root = InsertBST(root, 50);
root = InsertBST(root, 30);
root = InsertBST(root, 20);
root = InsertBST(root, 40);
root = InsertBST(root, 70);
root = InsertBST(root, 60);
root = InsertBST(root, 80);

printf("Inorder traversal of the given tree \n");
IOT(root);

printf("\nDelete 20\n");
root = DeleteBST(root, 20);
printf("Inorder traversal of the modified tree \n");
IOT(root);

printf("\nDelete 30\n");
root = DeleteBST(root, 30);
printf("Inorder traversal of the modified tree \n");
IOT(root);

printf("\nDelete 50\n");
root = DeleteBST(root, 50);
printf("Inorder traversal of the modified tree \n");
IOT(root);

return 0;
}