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

[题目分析]二叉树顺序存储是按完全二叉树的格式存储利用完全二叉树双亲结点与子女结点编号间的关系求下标为i和j的两结点的双亲双亲的双亲等等直至找到最近的公共祖先

void Ancestor(ElemType A[]int nij)

//二叉树顺序存储在数组A[n]中本算法求下标分别为i和j的结点的最近公共祖先结点的值

{while(i!=j)

if(i>j) i=i/; //下标为i的结点的双亲结点的下标

else j=j/; //下标为j的结点的双亲结点的下标

printf(所查结点的最近公共祖先的下标是%d值是%diA[i]);//设元素类型整型

}// Ancestor

[题目分析]用二叉树表示出父子夫妻和兄弟三种关系可以用根结点表示父（祖先）根结点的左子女表示妻妻的右子女表示子这种二叉树可以看成类似树的孩子兄弟链表表示法根结点是父根无右子女左子女表示妻妻的右子女（右子女的右子女等）均可看成兄弟（即父的所有儿子）兄弟结点又成为新的父其左子女是兄弟（父的儿子）妻妻的右子女（右子女的右子女等）又为儿子的儿子等等首先递归查找某父亲结点若查找成功则其左子女是妻妻的右子女及右子女的右子女等均为父亲的儿子

BiTree Search(BiTree tElemType father)//在二叉树上查找值为father的结点

{if(t==null) return (null); //二叉树上无father结点

else if(t>data==father) return(t); //查找成功

p=Search(t>lchildfather); p=Search(t>rchildfather); }

}//结束Search

void PrintSons(BiTree tElemType p) //在二叉树上查找结点值为p的所有的儿子

{p=Serach(tp); //在二叉树t上查找父结点p

if(p!=null) //存在父结点

{q=p>lchild; q=q>rchild; //先指向其妻结点再找到第一个儿子

while(q!=null) {printf(q>data); q=q>rchild;} //输出父的所有儿子

}

}//结束PrintSons

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