二叉排序树的定义是递归定义

二叉排序树的类型定义如下：

typedef struet BSTNode{//二叉排序树的结点结构

int data; //数据域

struct BSTNode*lchild,*rchild;//左、右孩子指针

}BSTNode,*BSTree;

设计递归算法，统计一棵二叉排序树T中值小于a的结点个数。

阅读以下说明、C函数和问题，将解答填入答题纸的对应栏内。

【说明】

二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具有如下性质的二叉树：

●若它的左子树非空，则其左子树上所有结点的键值均小于根结点的键值;

●若它的右子树非空，则其右子树上所有结点的键值均大于根结点的键值;

●左、右子树本身就是二叉查找树。

设二叉查找树采用二叉链表存储结构，链表结点类型定义如下：

typedefstructBiTnode{

intkey_value;/*结点的键值，为非负整数*/

structBiTnode*left,*right;/*结点的左、右子树指针*/

}*BSTree;

函数find_key(root,key)的功能是用递归方式在给定的二叉查找树(root指向根结点)中查找键值为key的结点并返回结点的指针;若找不到，则返回空指针。

【函数】

BSTreefind_key(BSTreeroot,intkey)

{

if((1))

returnNULL;

else

if(key==root->key_value)

return(2);

elseif(keykey_value)

return(3);

else

return(4);

}

【问题1】

请将函数find_key中应填入(1)~(4)处的字句写在答题纸的对应栏内。

【问题2】

若某二叉查找树中有n个结点，则查找一个给定关键字时，需要比较的结点个数取决于(5).

设二叉树以二叉链表方式存储，试完成下列问题的递归算法。 设二叉树结点和二叉树结构体定义如下： typedef struct btnode { ElemType element; struct btnode* lchild, *rchild; }BTNode; typedef struct binarytree{ BTNode* root; }BinaryTree; （1）求一棵二叉树的高度； int Depth(BTNode *p) { int lh, rh; if (!p) return 0; lh = ______________; rh = _____________; if (lh > rh) return _________; else return ________; } int DepthofBT(BinaryTree Bt) { return ___________; } （2）求一棵二叉树中的结点个数； int Size(BTNode * p) { if (!p) return _____ ; else return Size(p->lchild)+______________+1; } int SizeofBT(BinaryTree Bt) { return ______________); } （3）交换一棵二叉树中每个结点的左、右子树。 void exchange ( BTNode * p) { if(!p) return; if ( p->lchild != NULL || p->rchild != NULL ) { temp = p->lchild; p->lchild = ____________; p->rchild = temp; exchange (___________ ); exchange ( p->rchild ); } } void exchange(BinaryTree *bt) { ____________________; }

【Test-9-3】假设二叉树存放于二叉链表中，树中结点的关键字值互不相同。下面算法的功能是：判别给定的二叉树是否二叉排序树。请在空白处填入正确的语句。 void binSearchTree(BiTNode *t, BiTNode *&pr, int& bs) { //在以 t 为根的子树中判断该子树是否二叉排序树。是则引用参数 bs 为 1，否则 bs //为 0。引用参数 pr 是当前子树根结点 t 的前驱指针，在主调程序中应为各参数初 //始化： t 赋予根结点指针 root， pr 赋予 NULL， bs 赋予 1。 if(t != NULL && bs) { _______________①_________________; //递归到左子树判断 if(pr == NULL) { pr = t; //t 为中序第一个结点 bs = 1; } else { if(__________②___________) { pr = t; bs = 1; } else bs = 0; } if(bs) ____________③__________________; //递归到右子树判断 } }

用类Pascal语言编写一非递归算法，求二叉树上叶子结点的数量。二叉树用二叉链表存储，左指针定义为lchild，右指针定义为rchild。【燕山大学2000七、2(8分)】