构造平衡二叉排序树
程序如下：
#include"stdio.h"
#include"stdlib.h"
typedef int KeyType;
typedef struct node
{KeyType key;
struct node *lchild,*rchild;
}BSTNode;
typedef BSTNode *BSTree;
BSTree CreateBST(void);
void DelBSTNode(BSTree *Tptr,KeyType Key);
void InorderBST(BSTree T);
void InsertBST(BSTree *bst,KeyType key);
main()
{BSTree T;
char ch1,ch2;
KeyType Key;
printf("建立一棵二叉排序树的二叉链表存储\n");
T=CreateBST();
ch1='y';
while (ch1=='y'||ch1=='Y')
{printf("请选择下列操作:\n");
printf("1------更新二叉树上的存储\n");
printf("2------二叉排序树上的删除\n");
printf("3------二叉排序树中序输出\n");
printf("4------退出\n");
scanf("\n%c",&ch2);
switch(ch2)
{case '1':T=CreateBST();break;
case '2':printf("\n请输入要删除的数据:");
scanf("\n%d",&Key);
DelBSTNode(&T,Key);
printf("删除操作完毕.\n");break;
case '3':InorderBST(T);
printf("\n二叉排序树输出完毕.\n");
break;
case '4':ch1='n';break;
default:ch1='n';
}
}
}
void InsertBST(BSTree *bst,KeyType key)
{BSTree s;
if(*bst==NULL) /*递归结束条件*/
{s=(BSTree)malloc(sizeof(BSTNode)); /*申请新的结点*/ s->key=key;
s->lchild=NULL;
s->rchild=NULL;
*bst=s;
}
else
if(key<(*bst)->key)
InsertBST(&((*bst)->lchild),key); /*将S插入左子树*/ else
if(key>(*bst)->key)
InsertBST(&((*bst)->rchild),key); /*将S插入右子树*/ }
BSTree CreateBST(void)
{BSTree T;
KeyType Key;
T=NULL;
printf("请输入一个关键字（输入0时结束输入）:\n"); scanf("%d",&Key);
while(Key)
{InsertBST(&T,Key);
printf("请输入下一个关键字（输入0时结束输入）:\n"); scanf("\n%d",&Key);
}
return T;
}
void DelBSTNode(BSTree *T,KeyType Key) {BSTNode *parent=NULL,*p,*q,*child;
p=*T;
while(p)
{if(p->key==Key) break;
parent=p;
p=(Key<p->key)?p->lchild:p->rchild;
}
if(!p)
{printf("没有找到要删除的结点\n");return;}
q=p;
if(q->lchild && q->rchild)
for(parent=q,p=q->rchild;p->lchild;parent=q,p=p->lchild); child=(p->lchild)?p->lchild:p->rchild;
if(!parent)
*T=child;
else
{if(p==parent->lchild)
parent->lchild=child;
else
parent->rchild=child;
if(p!=q)
q->key=p->key;
}
free(p);
}
void InorderBST(BSTree T)
{if(T!=NULL)
{InorderBST(T->lchild);
printf("%5d",T->key);
InorderBST(T->rchild);
}
}
实验结果：
建立二叉检索树并输入数据：
输出数据：（二叉检索树中序输出）
删除二叉检索树中的一个点：
最后的输出结果：（二叉检索树中序输出）。