二叉排序樹的程式碼

#include<stdio.h>

#include<malloc.h>

typedef int ElemType;

typedef int KeyType;

typedef struct bstnode

{

KeyType key;

ElemType data;

struct bstnode *lchild,*rchild;

}BSTNode;

BSTNode *BSTSearch(BSTNode *bt,KeyType k)

{

BSTNode *p=bt;

while(p!=NULL)

{

if(p->key==k)

return p;

else if(k<p->key)

p=p->lchild;

else

p=p->rchild;

}

return NULL;

}

int BSTInsert(BSTNode *&bt,KeyType k)

{

BSTNode *f,*p=bt;

while(p!=NULL)

{

if(p->key==k)

return 0;

f=p;

if(k<p->key)

p=p->lchild;

else

p=p->rchild;

}

p=(BSTNode *)malloc(sizeof(BSTNode));

p->key=k;

p->lchild=p->rchild=NULL;

if(bt==NULL)

bt=p;

else if(k<f->key)

f->lchild=p;

else

f->rchild=p;

return 1;

}

void CreateBST(BSTNode *&bt,KeyType a[],int n)

{

bt=NULL;

int i=0;

while(i<n)

{

BSTInsert(bt,a[i]);

i++;

}

}

void DestroyBST(BSTNode *&bt)

{

if(bt!=NULL)

{

DestroyBST(bt->lchild);

DestroyBST(bt->rchild);

free(bt);

}

}

void DispBST(BSTNode *bt)

{

if(bt!=NULL)

{

printf("%d",bt->key);

if(bt->lchild!=NULL||bt->rchild!=NULL)

{

printf("(");

DispBST(bt->lchild);

if(bt->rchild!=NULL)

printf(",");

DispBST(bt->rchild);

printf(")");

}

}

}

int BSTDelete(BSTNode *&bt,KeyType k)

{

BSTNode *p=bt,*f,*q,*q1,*f1;

f=NULL;

if(bt==NULL)return 0;

while(p!=NULL)

{

if(p->key==k)

break;

f=p;

if(k<p->key)

p=p->lchild;

else

p=p->rchild;

}

if(p==NULL)return 0;

else if(p->lchild==NULL)

{

if(f==NULL)

bt=p->rchild;

else if(f->lchild==p)

f->lchild=p->rchild;

else if(f->rchild==p)

f->rchild=p->rchild;

free(p);

}

else if(p->rchild==NULL)

{

if(f==NULL)

bt=p->lchild;

if(f->lchild==p)

f->lchild=p->lchild;

else if(f->rchild==p)

f->rchild=p->lchild;

free(p);

}

else

{

q=p->lchild;

if(q->rchild==NULL)

{

p->key=q->key;

p->data=q->data;

p->lchild=p->lchild;

free(q);

}

else

{

f1=q;q1=f1->rchild;

while(q1->rchild!=NULL)

{

f1=q1;

q1=q1->rchild;

}

p->key=q1->key;

p->data=q1->data;

if(f1->rchild==q1)

f1->lchild=q1->rchild;

else if(f1->rchild==q1)

f1->rchild=q1->lchild;

free(q1);

}

}

return 1;

}

main()

{

KeyType a[]={25,18,46,2,53,39,32,4,74,67,60,11},k=25;

int n=12;

BSTNode *bt;

CreateBST(bt,a,n);

printf("BST:");DispBST(bt);printf("\n");

if(BSTDelete(bt,k))

{

printf("BST:");

DispBST(bt);printf("\n");

}

else printf("插入關鍵字%d的結點\n",k);

printf("插入的關鍵字%d\n",k);

if(BSTInsert(bt,k))

{

printf("BST:");

DispBST(bt);printf("\n");

}

else printf("存在重複的關鍵字%d\n",k);

DestroyBST(bt);

}