数据结构考研分类复习真题 第六章 答案 (五)[30]

[题目分析]两棵空二叉树或仅有根结点的二叉树相似对非空二叉树可判左右子树是否相似采用递归算法

int Similar(BiTree pq) //判断二叉树p和q是否相似

{if(p==null && q==null) return ();

else if(!p && q || p && !q) return ();

else return(Similar(p>lchildq>lchild) && Similar(p>rchildq>rchild))

}//结束Similar

[题目分析] 根据树的双亲表示法创建树的孩子兄弟链表表示法首先给出根结点在双亲表示法中的下标但找根结点的子女要遍历双亲表示法的整个静态链表根结点的第一个子女是孩子兄弟表示法中的孩子其它子女结点作兄弟对双亲表示法中的任一结点均递归建立其孩子兄弟链表子树

CSTree PtreeToCstree (PTree ptint root)

//本算法将双亲表示法的树pt转为孩子兄弟链表表示的树root是根结点在双亲表示法中的下标

{CSTree child sibling; int firstchild;

CSTree cst=(CSTree)malloc(sizeof(CSNode)); //申请结点空间

cst>data=ptnodes[root]data; cst>firstchild=null; cst>nextsibling=null;//根结点

firstchild=;

for(i=;i<=ptn;i++) //查找root的孩子

if(ptnodes[i]parent==root)

{child=PtreetoCstree(pti);

if(firstchild) {cst>firstchild=child; firstchild=;sibling=cst>firstchild;}

else //child不是root的第一个孩子作兄弟处理

{sibling>nextsibling=child; sibling=sibling>nextsibling;}

}//if

}//end for

return cst; }//结束PtreetoCstree

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []