Leafhead=s； }
Inorder(T－>rchild); } }
答案：
2、已知二叉树中的结点类型BinTreeNode定义为: struct BinTreeNode
{ ElemType data;
BinTreeNode *left, *right; };
其中data为结点值域，left和right分别为指向左、右孩子结点的指针域。
下面函数的功能是从二叉树BT中查找值为x的结点，若查找成功则返回结点地址，否则返回空。按标号填写空缺的内容，要求统一填写在算法后面的标记处。 BinTreeNode* BTF(BinTreeNode* BT，ElemType x) {
if(BT==NULL) _ return NULL __; else { if(BT->data==x) _ return BT _; else { BinTreeNode* t;
if(t=BTF(BT->left, x)) return t;
___ if(t=BTF(BT->right, x)) return t _____; return NULL; } } }
3、由二叉树的前序序列和中序序列能否唯一确定一棵二叉树？ 由二叉树的中序序列和后序序列能否唯一确定一棵二叉树？ 由二叉树的前序序列和后序序列能否唯一确定一棵二叉树？ 请分别进行论述。 答案：
(1)给定二叉树结点的前序序列和中序序列，可以唯一确定该二叉树。因为前序序列的第一个元素是根结点，该元素将二叉树中序序列分成两部分，左边（设l个元素）表示左子树，若左边无元素，则说明左子树为空；右边（设r个元素）是右子树，若为空，则右子树为空。根据前序遍历中―根—左子树—右子树‖的顺序，则由从第二元素开始的l个结点序列和中序序列根左边的l个结点序列构造左子树，由前序序列最后r个元素序列与中序序列根右边的r个元素序列构造右子树。
(2)由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。证明如下：
6
当n=1时，只有一个根结点，由中序序列和后序序列可以确定这棵二叉树。 设当n=m-1时结论成立，现证明当n=m时结论成立。
设中序序列为S1，S2，…，Sm,后序序列是P1,P2,…，Pm。因后序序列最后一个元素Pm是根，则在中序序列中可找到与Pm相等的结点（设二叉树中各结点互不相同）Si(1≤i≤m)，因中序序列是由中序遍历而得，所以Si是根结点，S1，S2，…，Si-1是左子树的中序序列，而Si+1,Si+2,…,Sm是右子树的中序序列。
若i=1，则S1是根，这时二叉树的左子树为空，右子树的结点数是m-1,则{S2，S3，…，Sm}和{P1，P2，…，Pm-1}可以唯一确定右子树，从而也确定了二叉树。
若i=m,则Sm是根，这时二叉树的右子树为空，左子树的结点数是m-1，则{S1，S2，…，Sm-1}和{P1，P2，…，Pm-1}唯一确定左子树，从而也确定了二叉树。
最后，当1 可唯一确定二叉树的左子树，由{Si+1,Si+2,…，Sm}和{Pi,Pi+1,…，Pm-1}可唯一确定二叉树的右子树 。 (3)由二叉树的前序序列和后序序列不能唯一确定一棵二叉树。因为无法确定左右子树两部分。例如，任何结点只有左子树的二叉树和任何结点只有右子树的二叉树，其前序序列相同，后序序列相同，但却是两棵不同的二叉树。 五、算法描述题 试写出复制一棵二叉树的递归函数的算法。 BiTree Copy(BiTree t)//复制二叉树t { BiTree bt; if (t==null) bt=null; else{ bt=(BiTree)malloc(sizeof(BiNode)); bt->data=t->data; bt->lchild=Copy(t->lchild); bt->rchild=Copy(t->rchild); } return(bt); } 7