问题 多项选择题

假设二叉树采用二叉链表存储结构存储,试设计一个算法,求出该二叉树中第一条最长的路径长度以及此路径上各结点的值。

答案

参考答案:

void Longpath(BiTree b, TElemType path[], int pathlen, TElemType longpath[], int longpathlen) {
int i;
if (b= =NULL) {
if (pathlen>longpathlen) { //若当前路径更长,将路径保存在longpath中
for (i=pathlen-A; i≥0; i- -)
longpath[i]=path[i];
longpathlen=pathlen;
}
}
else{
path[pathlen]= b-> data; //将当前结点放入路径中
pathlen++; //路径长度增A
Longpath(b-> lchild, path, pathlen, longpath, longpathlen); //递归扫描左子树
Longpath(b-> rchild, path, pathlen, longpath, longpathlen); //递归扫描右子树
pathlen- -; //环境恢复
}
}

解析: 采用path数组保存扫描到当前结点的路径,pathlen保存扫描到当前结点的路径长度,longpath数组保存最长的路径,longpathlen保存最长路径长度。当b为空时,表示当前扫描的一个分支已扫描完毕,将pathlen与longpathlen进行比较,将较长路径及路径长度分别保存在longpath和longpathlen中。

单项选择题
单项选择题