文档介绍：.
实****报告
一：需求分析
1．差不多要求
a）以回车（'\n'）为输入结束标志，输入数列L,生成一棵二叉
排序树 T；
b）对二叉排序树 T 作中序遍历，输出结果；
c）输入元素x,查找二叉排序树T,若存在含x的结点，则删除
该结点 , 并作中序遍历（执行操作 2）；否则输出信息“无 x”；
2．数据类型
要实现二叉排序数，必须先定义数据类型，本设计的输
1 / 16
入数据为整型，输出的数据也为整型。
3．题目功能详细讲明
要生成一棵二叉排序数 T,元素类型为ElemType
在二叉排序树中查找其关键字等于给定值的结点是否存在
在二叉排序树中插入一个新结点，中序遍历所建二叉排
序树，将得到一个按关键字有序的元素序列
二叉排序树的查找，可多次查找，并输出查找的结果
4．最后对输出结构进行分析
二．概要分析
1. 二叉树是另一种树型结构，他的特点是每个结点至多只有两棵子树，同时，二叉树的子树有左右之分，其次序不能任意颠倒。
2. 二叉树的存储结构
// 二叉树的顺序存储表示
#define MAX-TREE-SIZE 100 // 二叉树的最大结点数
Typedef TELem type sqbitree[MAX-TREE-SIZE];//0 号单元存
2 / 16
储根结点
sqBiTree bt
3. 在不同的存储结构中 , 实现二叉树的操作方法也不同 , 如找结点 X 的双亲 PARENT(T,E), 在三叉链表中专门容易实现 , 而在二叉链表中则需从根指针动身巡查 .
4.
if(!t) {*p=f;return (0);} /*
查找不成功 */
else if(key==t->data) {*p=t;return (1);} /* 查找成
功*/
else
if(key<t->data)
searchBST(t->lchild,key,t,p); /*
在左子树中接着查找 */
else searchBST(t->rchild,key,t,p); /*
在右子树中接着
查找 */
5
calculateASL(node *t,int *s,int *j,int i) /*
计算平均查找
长度 */
{
if(*t){
i++; /*i 记录当前结点的在当前树中的深度 */
3 / 16
*s=*s+i; /*s
记录已遍历过的点的深度之和 */
if(calculateASL(&(*t)->lchild,s,j,i))/*
左子树的 ASL*/
三 . 详细程序
#include<>
# include<>
计算
typedef struct Tnode{
int data; /*
struct Tnode *lchild,*rchild; /* 指针，分不指向结点的左右小孩 */
}*node,BSTnode;
输入的数据 */
结点的左右
searchBST(node t,int key,node f,node *p) /* {
if(!t) {*p=f;return (0);} /*
else if(key==