构造平衡二叉排序树.doc

《构造平衡二叉排序树.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、构造平衡二叉排序树程序如下：#include"stdio.h"#include"stdlib.h"typedefintKeyType;typedefstructnode{KeyTypekey;structnode*lchild,*rchild;}BSTNode;typedefBSTNode*BSTree;BSTreeCreateBST(void);voidDelBSTNode(BSTree*Tptr,KeyTypeKey);voidInorderBST(BSTreeT);voidInsertBST(BSTree*bst,KeyTypekey);main(){BST

2、reeT;charch1,ch2;KeyTypeKey;printf("建立一棵二叉排序树的二叉链表存储");T=CreateBST();ch1='y';while(ch1=='y'

3、

4、ch1=='Y'){printf("请选择下列操作:");printf("1------更新二叉树上的存储");printf("2------二叉排序树上的删除");printf("3------二叉排序树中序输出");printf("4------退出");scanf("%c",&ch2);switch(ch2){case'1':T=CreateBST

5、();break;case'2':printf("请输入要删除的数据:");scanf("%d",&Key);DelBSTNode(&T,Key);printf("删除操作完毕.");break;case'3':InorderBST(T);printf("二叉排序树输出完毕.");break;case'4':ch1='n';break;default:ch1='n';}}}voidInsertBST(BSTree*bst,KeyTypekey){BSTrees;if(*bst==NULL)/*递归结束条件*/{s=(BSTree)malloc(

6、sizeof(BSTNode));/*申请新的结点*/s->key=key;s->lchild=NULL;s->rchild=NULL;*bst=s;}elseif(key<(*bst)->key)InsertBST(&((*bst)->lchild),key);/*将S插入左子树*/elseif(key>(*bst)->key)InsertBST(&((*bst)->rchild),key);/*将S插入右子树*/}BSTreeCreateBST(void){BSTreeT;KeyTypeKey;T=NULL;printf("请输入一个关键字（输入0时结束输入）

7、:");scanf("%d",&Key);while(Key){InsertBST(&T,Key);printf("请输入下一个关键字（输入0时结束输入）:");scanf("%d",&Key);}returnT;}voidDelBSTNode(BSTree*T,KeyTypeKey){BSTNode*parent=NULL,*p,*q,*child;p=*T;while(p){if(p->key==Key)break;parent=p;p=(Keykey)?p->lchild:p->rchild;}if(!p){printf("没有找到要删除

8、的结点");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;elseparent->rchild=child;if(p!=q)q->key=p->key;}free(p);}voidInorderBST(BSTreeT

9、){if(T!=NULL){InorderBST(T->lchild);printf("%5d",T->key);InorderBST(T->rchild);}}实验结果：建立二叉检索树并输入数据：输出数据：（二叉检索树中序输出）删除二叉检索树中的一个点：最后的输出结果：（二叉检索树中序输出）