2016最新广工anyview数据结构答案

【题目】若两棵二叉树T1和T2皆为空，或者皆不空 且T1的左、右子树和T2的左、右子树分别相似，则 称二叉树T1和T2相似。试编写算法，判别给定两棵 二叉树是否相似。 二叉链表类型定义： typedef struct BiTNode { TElemType data;

struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; **********/

Status Similar(BiTree T1, BiTree T2) /* 判断两棵二叉树是否相似的递归算法 */ {

if(!T1&&!T2)//同为空时，两树相似 return TRUE;

else if(T1&&T1){

if(Similar(T1 -> lchild,T2 -> lchild) && Similar(T1 -> rchild,T2 -> rchild))

//两树都不为空时，判断左右子树是否相似 return TRUE; else

return FALSE;

}else//以上两种情况都不符合，就直接返回FALSE return FALSE; } /**********

【题目】编写递归算法，求对二叉树T先序遍历时 第k个访问的结点的值。 二叉链表类型定义： typedef struct BiTNode {

TElemType data;

struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; **********/

TElemType PreOrder(BiTree T, int &k) {

TElemType x='#'; if(T==NULL)return '#'; if(k==1)return T->data; if(T->lchild!=NULL) { k--;

x=PreOrder(T->lchild,k); }

if(T->rchild!=NULL&&x=='#')

{ k--;

x=PreOrder(T->rchild, k); } return x; }

TElemType PreOrderK(BiTree T, int k)

/* 求对二叉树T先序遍历时第k个访问的结点的值。*/ /* 若失败，则返回'#' */ { int t=k;

return PreOrder(T,t) ; } /**********

【题目】编写递归算法，计算二叉树T中叶子结点的数目。