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

．[题目分析]二叉树先序序列的最后一个结点若二叉树有右子树则是右子树中最右下的叶子结点若无右子树仅有左子树则是左子树最右下的叶子结点若二叉树无左右子树则返回根结点

BiTree LastNode(BiTree bt)//返回二叉树bt先序序列的最后一个结点的指针

{BiTree p=bt;

if(bt==null) return(null);

else while(p)

if (p>rchild) p=p>rchild; //若右子树不空沿右子树向下

else if (p>lchild) p=p>lchild; //右子树空左子树不空沿左子树向下

else return(p); //p即为所求

}//结束lastnode

[题目分析]高度为K的二叉树按顺序方式存储要占用K 个存储单元与实际结点个数n关系不大对不是完全二叉树的二叉树要增加虚结点使其在形态上成为完全二叉树

int m=K ; //全局变量

void PreOrder(ElemType bt[]i )

//递归遍历以顺序方式存储的二叉树bt i是根结点下标（初始调用时为）

{if (i<=m) //设虚结点以表示

{printf(bt[i]) //访问根结点

if(*i<=m && bt[*i]!=) PreOrder(bt*i); //先序遍历左子树

if(*i+<=m && bt[*i+]!=) PreOrder(bt*i+);// 先序遍历右子树

} }//结束PreOrder

二叉树中最大序号的叶子结点是在顺序存储方式下编号最大的结点

void Ancesstor(ElemType bt[]) //打印最大序号叶子结点的全部祖先

{c=m; while(bt[c]==) c; //找最大序号叶子结点该结点存储时在最后

f=c/; //c的双亲结点f

while(f!=) //从结点c的双亲结点直到根结点路径上所有结点均为祖先结点

{printf(bt[f]); f=f/; }//逆序输出最老的祖先最后输出

} //结束

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