以二叉链表作为二叉树的存储结构，编写以下算法：求任意二叉树中第一条最长的路径长度，并输出此路径上各结点的值。
void LongestPath(BiTree bt)//求二叉树中的第一条最长路径长度{BiTree p=bt,l[],s[];//l, s 是栈，元素是二叉树结点指针，l 中保留当前最长路径中的结点int i，top=0,tag[],longest=0;while(p || top>0) {while(p) {s[++top]=p；tag[top]=0; p=p->Lc;} //沿左分枝向下 if(tag[top]==1) //当前结点的右分枝已遍历 {if(!s[top]->Lc && !s[top]->Rc) //只有到叶子结点时，才查看路径长度 if(top>longest) {for(i=1;i<=top;i++) l[i]=s[i]; longest=top; top--;} //保留当前最长路径到 l 栈，记住最高栈顶指针，退栈 } else if(top>0) {tag[top]=1; p=s[top].Rc;} //沿右子分枝向下 }//while(p!=null||top>0) }//结束 LongestPath
举一反三
内容
- 0
假设二叉树b采用二叉链存储结构存储,试设计一个算法,输出该二叉树中从根节点出发的第一条最长的路径长度,并输出此路径上各节点的值。并分析你设计的算法的时间复杂度和空间复杂度。
- 1
编写算法，交换二叉树左右子树上的所有结点（二叉树采用二叉链表结构存储）。
- 2
假设树采用二叉链表存储，编写计算整个二叉树高度的算法（二叉树的高度也叫 二叉树的深度）。
- 3
外存二叉查找树不易更新的问题可以通过将二叉树转化为多叉树解决
- 4
一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构。且树中结点的关键字均不同。