二叉树的定义是个递归定义。

设二叉树以二叉链表方式存储，试完成下列问题的递归算法。 设二叉树结点和二叉树结构体定义如下： 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) { ____________________; }

【说明】

对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二叉树的每个结点，且每个结点仅访问一次的过程。函数InOrder。()借助栈实现二叉树的非递归中序遍历运算。

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

typedef struct BtNode{

ElemTypedata； ／*结点的数据域，ElemType的具体定义省略*／

struct BtNode*ichiid，*rchild； ／*结点的左、右弦子指针域*／

)BtNode，*BTree；

在函数InOrder()中，用栈暂存二叉树中各个结点的指针，并将栈表示为不含头结点

的单向链表(简称链栈)，其结点类型定义如下：

typedef struct StNode{ ／*链栈的结点类型*／

BTree elem； ／*栈中的元素是指向二叉链表结点的指针*／

struct StNode*link；

}S％Node；

假设从栈顶到栈底的元素为en、en-1、…、e1，则不含头结点的链栈示意图如图5—5

所示。

【C函数】

int InOrder(BTree root) ／*实现二叉树的非递归中序遍历*／

{

BTree ptr； ／*ptr用于指向二又树中的结点*／

StNode*q； ／*q暂存链栈中新创建或待删除的结点指针+／

StNode*stacktop=NULL； ／*初始化空栈的栈顶指针stacktop*／

ptr=root； ／*ptr指向二叉树的根结点*／

while( (1 ) I I stacktop!=NULL){

while(ptr!=NULL){

q=(StNode*)malloc(sizeof(StNode))；

if(q==NULL)

return-1；

q->elem=ptr；(2) ；

stacktop=q； ／*stacktop指向新的栈顶*／

ptr=(3 ) ； ／*进入左子树*／

}

q=stacktop； (4) ； ／*栈顶元素出栈*／

visit(q)； ／*visit是访问结点的函数，其具体定义省略*／

ptr= (5) ； ／*进入右子树*／

free(q)； ／*释放原栈顶元素的结点空间*／

}

return 0；

}／*InOrder*／

阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。

【说明4．1】

假设两个队列共享一个循环向量空间(如图1-2所示)，其类型Queue2定义如下：

typedef struct{

DateType data ［MaxSize］；

int front［2］，rear［2］；

}Queue2；

对于i=0或1，front［i］和rear［i］分别为第i个队列的头指针和尾指针。函数EnQueue(Queue2*Q，int i，DateType x)的功能是实现第i个队列的入队操作。

【函数4．1】

int EnQueue(Queue2*Q，int i，DateType x)

{∥若第i个队列不满，则元素x入队列，并返回1；否则，返回0

if(i＜0‖i>1)return 0；

if(Q->rear［i］==Q->front［ (1) ］

return 0；

Q->data［ (2) ］=x；

Q->rear［i］=［ (3) ］；

return 1；

}

【说明4．2】

函数BTreeEqual(BinTreeNode*T1，BinTreeNode*T2)的功能是递归法判断两棵二叉树是否相等，若相等则返回1，否则返回0。函数中参数T1和T2分别为指向这两棵二叉树根结点的指针。当两棵树的结构完全相同，并且对应结点的值也相同时才被认为相等。

已知二叉树中的结点类型BinTreeNode定义为：

struct BinTreeNode{

char data；

BinTreeNode*left，*right；

}；

其中data为结点值域，left和right分别为指向左、右子女结点的指针域，

【函数4．2】

int BTreeEqual(BinTreeNode*T1，BinTreeNode*T2)

{

if(T1==NULL ＆＆ T2==NULL)return 1；∥若两棵树均为空，则相等

else if( (4) )return 0；∥若一棵为空一棵不为空，则不等

else if( (5) )return 1；∥若根结点值相等并且左、右子树

∥也相等，则两棵树相等，否则不等

else return 0；

}

阅读下列说明和流程图，将应填入(n)的语句写在答题纸的对应栏内。

【流程图说明】

下面的流程(如图1所示)用N-S盒图形式描述了在一棵二叉树排序中查找元素的过程，节点有3个成员：data，left和right。其查找的方法是：首先与树的根节点的元素值进行比较：若相等则找到，返回此结点的地址；若要查找的元素小于根节点的元素值，则指针指向此结点的左子树，继续查找；若要查找的元素大于根节点的元素值，则指针指向此结点的右子树，继续查找。直到指针为空，表示此树中不存在所要查找的元素。

【算法说明】

【流程图】

将上题的排序二叉树中查找元素的过程用递归的方法实现。其中NODE是自定义类型：

typedef struct node{

int data；

struct node*left；

struct node*right；

}NODE；

【算法】

NODE*SearchSortTree(NODE*tree，int e)

{

if(tree!=NULL)

{

if(tree->data<e)

(4) ；∥小于查找左子树

else if(tree->data<e)

(5) ；∥大于查找左子树

else return tree；

}

return tree；

}