二叉排序树与平衡二叉树的实现(2)

mian():主函数模块。在主函数模块中调用一下函数： （1）int Insert(BiTreeNode **root,int item):插入函数； （2）int Search(BiTreeNode *root,int item)：查找函数； （3）void InorderTraverse(BiTreeNode *root)：中序遍历输出函数；

（4）BiTreeNode* Delete(BiTreeNode *root,int x)：删除函数；

顺序表：

main()：主函数模块。在主函数模块中调用以下函数： （1）void Insert(BST T,int i,int key)：插入函数； （2）BST Create(int *data,int num)：生成顺序表BST； （3）void InorderTraverse(BST T,int i)：中序遍历显示函数； （4）int Search(BST T,int key,int i)：查找函数； （5）BST Delete(BST T,int key)：删除函数；

（6）computeASL(BST T,int i,int *s,int j)：计算平均查找长度函数。

2.4主函数流程图：

6/18

开始 回车（’\\\\n’）为输入结束标志生成二叉排序树T，调用Insert（）； 调用menu函数 显示菜单 输入choice=1 实现中序遍历，输入 输入choice=2 计算二叉排序树的平均长度 输入choice=3 输入你要删除的元素x

7/18

N 元素是否存在 Y 输入此二叉排序树无元素x 删除此元素，然后再输出中序遍历的结果 输入choice=0 结 束

3.详细设计和代码： 3.1二叉链表：

源程序：

int Insert(BiTreeNode **root,int item) //插入 {

BiTreeNode *current,*parent=NULL,*p;

current= *root;

while(current != NULL) {

if(current->data == item) return 0;

parent=current;

if(current->data < item)

current = current->rightChild; else

current= current->leftChild; }

8/18

p=(BiTreeNode *)malloc(sizeof(BiTreeNode)); if(p==NULL) {

printf(\空间不够！\ exit(1); }

p->data = item;

p->leftChild = NULL; p->rightChild = NULL;

if(parent == NULL) *root = p;

else if(item< parent->data) parent->leftChild =p; else

parent->rightChild =p; return 1; }

int Search(BiTreeNode *root,int item) {

BiTreeNode *p;

if(root!=NULL) {

p=root;

while(p!=NULL) {

if(p->data == item) return 1; if(item>p->data) p=p->rightChild; else

p=p->leftChild; } }

return 0; }

void InorderTraverse(BiTreeNode *root) //{

if(root == NULL) return;

9/18

中序遍历显示 if(root->leftChild != NULL)

InorderTraverse(root->leftChild);

printf(\

if(root->rightChild !=NULL)

InorderTraverse(root->rightChild); }

BiTreeNode* Delete(BiTreeNode *root,int x) //删除操作 {

BiTreeNode *s,*curr,*f,*q; int flag=0; curr=root;

while((curr!=NULL)&&(!flag)) //找到要删除的结点 {

if(curr->data==x) flag=1;

else if(xdata) {

f=curr; //记住双亲的指针 curr=curr->leftChild; } else {

f=curr;

curr=curr->rightChild; } }

if(flag) {

if(curr->leftChild==NULL&&curr->rightChild==NULL) //左右子树都为空

{

if(curr==root) {

free(curr); root=NULL; } else {

10/18