11）二叉排序树的实现（二叉链表）,用c语言实现

题目如下：

二叉排序树的实现（二叉链表）

[问题描述]

采用二叉链表储存结构，实现对二叉排序树的操作。

[基本要求]

1）以回车符(‘\n’)为输入结束标志，输入数列L，生成一棵二叉排序树T；

2）对二叉排序树T作中序遍历，输出结果；

3）计算二叉排序树T查找成功的平均查找长度，输出结果；

4）输入元素x，查找二叉排序树T，若存在含x的结点，则删除该结点，并作中序遍历；否则二叉排序树 数据结构，输出信息“无x”。

！！！！其中//计算查找成功的平均查找长度//函数不会写！！！下面的代码又有好多错误，菜鸟调试不了啊

求大神们帮我解决，谢谢啊！！！

我的代码：#include<stdio.h>

#include<stdlib.h>

typedefintKeyType;

//typedefcharElemType[10];

typedefstructnode

{

KeyTypekey;/*关键字的值*/

structnode*lchild,*rchild;

}BSTNode,*BSTree;

/*插入*/voidInsertBST(BSTree*T,KeyTypekey)/*若在二叉排序树bst中不存在关键字key的元素二叉排序树 数据结构，插入该元素*/

{

BSTrees;

if(*T=NULL)/*递归结束条件*/

{

s=(BSTree)malloc(sizeof(BSTNode));/*申请新的结点s*/

s->key=key;

s->lchild=NULL;s->rchild=NULL;

*T=s;

}

elseif(key<(*T)->key)

InsertBST(&((*T)->lchild),key);/*将s插入左子树*/

elseif(key>(*T)->key)

InsertBST(&((*T)->rchild),key);/*将s插入右子树*/

}

/*建树*/voidCreateBST(BSTree*T)

/*从键盘输入元素的值，创建相应的二叉排序树*/

{

KeyTypekey;

*T=NULL;

scanf("%d",&key);

while(key!='\n')

{

InsertBST(T,key);/*在二叉排序树T中插入结点key*/

scanf("%d",&key);

}

}

/*查找*/BSTreeSearchBST(BSTreeT,KeyTypekey)

/*在根指针bst所指二叉树T上，查找关键字等于key的结点，若查找成功，返回指向该元素结点指针，否则返回空指针*/

{

BSTreeq;

q=T;

while(q)

{

if(q->key==key)returnq;/*查找成功*/

if(q->key>key)q=q->lchild;/*在左子树中查找*/

elseq=q->rchild;/*在右子树中查找*/

}

returnNULL;/*查找失败*/

}

/*删除*/BSTNode*DelBST(BSTreeT,KeyTypek)/*在二叉排序树t中删去关键字key的结点*/

{

BSTNode*p,*f,*s,*q;

p=T;f=NULL;

while(p)/*查找关键字为k的待删结点p*/

{

if(p->key==k)break;/*找到则跳出循环*/

f=p;/*f指向p结点的双亲结点*/

if(p->key>k)p=p->lchild;

elsep=p->rchild;

}

if(p==NULL)returnT;/*若找不到，返回原来的二叉排序树*/

if(p->lchild==NULL)/*无左子树*/

{

if(f==NULL)T=p->rchild;/*p是原二叉排序树的根*/

elseif(f->lchild==p)/*p是f的左孩子*/

f->lchild=p->rchild;/*将p的右子树链到f的左链上*/

else

f->rchild=p->rchild;/*将p的右子树链到f的右链上*/

free(p);

}

else

{

q=p;s=p->lchild;

while(s->rchild)

{q=s;s=s->rchild;}

if(q=p)q->lchild=s->lchild;

elseq->rchild=s->lchild;

p->key=s->key;

free(s);

}

returnT;

}

/*中序遍历*/intInorder(BSTree*T)

{

if(*T){

if(Inorder(&(*T)->lchild))

printf("%d",(*T)->key);

if(Inorder(&(*T)->rchild));

}

return(1);

}

voidmenu()

{

printf("----------------菜单目录--------------");

printf("\n\n\n\n请输入正确的选项数字");

printf("\n0:退出");

printf("\n1:中序输出");

printf("\n2:查找/删除元素");

printf("\n3:计算查找成功的平均查找长度");

}

voidmain()

{BSTreeT=NULL;

intnum;

ints=0,j=0,i=0;

intch=0;

BSTreep=NULL;

printf("输入一串数，每个数以空格分开:");

while(num!='\n')

{InsertBST(T,&num)}

printf("完成输入!\n");

/*printf("是否调用菜单，Y代表是，N代表否");

scanf("%c",&a);*/

menu();

while(ch!='\n')

{

scanf("%d",&ch);

switch(ch){

case0:exit(0);

break;

case1:Inorder(&T);

break;

case2:printf("输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历，否则输出无x:");

scanf("%d",&num);

if(BSTreeSearchBST(T,num,NULL,&p))

{

T=DelBST(T,num);

printf("删除成功!中序遍历输出：\n");

Inorder(&T);

}

else

printf("无%d",num);

break;

//case3:计算查找成功的平均查找长度

default:

printf("无此结点\n");

break;

}

}

}

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-112891-1.html