二叉排序树实现及结果截屏.doc

: .
二叉排序树实现及结果截屏
D
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记录当前结点的在当前树中的深度*/
*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==t->data) {*p=t;return (1);} /*查找成功*/
else if(key<t->data) searchBST(t->lchild,key,t,p); /*在左子树中继续查找*/
else searchBST(t->rchild,key,t,p); /*在右子树中继续查找*/
}
insertBST(node *t,int key) /*插入函数*/
{
node p=NULL,s=NULL;
if(!searchBST(*t,key,NULL,&p)) /*查找不成功*/
{
s=(node)malloc(sizeof(BSTnode));
s->data=key;
s->lchild=s->rchild=NULL;
if(!p) *t=s; /*被插结点*s为新的根结点*/
else if(key<p->data) p->lchild=s;/*被插结点*s为左孩子*/
else p->rchild=s; /*被插结点*s为右孩子*/
return (1);
}
else return (0);/*树中已有关键字相同的结点，不再插入*/
}
inorderTraverse(node *t) /*中序遍历函数*/
{
if(*t){
if(inorderTraverse(&(*t)->lchild)) /*中序遍历根的左子树*/
printf("%d ",(*t)->data); /*输出根结点*/
if(inorderTraverse(&(*t)->rchild)); /*中序遍历根的右子树*/
}
return(1) ;
}
calculateASL(node *t,int *s,int *j,int i) /*计算平均查找长度*/
{
if(*t){
i++; /*i记录当前结点的在当前树中的深度*/
*s=*s+i; /*s记录已遍历过的点的深度之和*/
if(calculateASL(&(*t)->lchild,s,j,i))/*计算左子树的ASL*/
{
(*j)++; /*j记录树中结点的数目*/
if(calculateASL(&(*t)->rchild