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

[题目分析]上题是打印从根结点到某结点p的路径上所有祖先结点本题是打印由根结点到叶子结点的所有路径只要在上题基础上把q是否等于p的判断改为q是否是叶子结点即可其语句段如下

if(q>lchild==null&&q>rchild==null) //q为叶子结点

{printf(从根结点到p结点的路径为\n);

for(i=;i<=top;i++) printf(s[i]>data);//输出从根到叶子路径上叶子q的所有祖先

printf(q>data); }

[题目分析]因为后序遍历栈中保留当前结点的祖先的信息用一变量保存栈的最高栈顶指针每当退栈时栈顶指针高于保存最高栈顶指针的值时则将该栈倒入辅助栈中辅助栈始终保存最长路径长度上的结点直至后序遍历完毕则辅助栈中内容即为所求

void LongestPath(BiTree bt)//求二叉树中的第一条最长路径长度

{BiTree p=btl[]s[]; //l s是栈元素是二叉树结点指针l中保留当前最长路径中的结点

int itop=tag[]longest=;

while(p || top>)

{ while(p) {s[++top]=ptag[top]=; p=p>Lc;} //沿左分枝向下

if(tag[top]==) //当前结点的右分枝已遍历

{if(!s[top]>Lc && !s[top]>Rc) //只有到叶子结点时才查看路径长度

if(top>longest) {for(i=;i<=top;i++) l[i]=s[i]; longest=top; top;}

//保留当前最长路径到l栈记住最高栈顶指针退栈

}

else if(top>) {tag[top]=; p=s[top]Rc;} //沿右子分枝向下

}//while(p!=null||top>)

}//结束LongestPath

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