题目：求二叉树节点的路径

【问题描述】

建立一棵二叉树，编程实现求从根结点到给定结点之间的路径。

【基本要求】

建立一棵以二叉链表形式存储二叉树，以bt指向根结点，p指向任一给定的结点，编程实现“以字符形式输出从根结点到给定结点之间的路径”；求出根结点到给定结点之间的路径长度；以两种不同的遍历方式，建立二叉树的链式存储结构。

1.问题分析：

设有下图二叉树：

image-20210704232847829 style=“float=left”

我们要找到根节点到G的路径。则从根节点开始，先序遍历。

可见，路径存储有着栈的特点：实现元素的出栈和入栈。

所以，A,B,D依次入栈，D不符合要求，D出栈。见下图：

而后判断到D时，没找到G，且D无左右子树。遍历右子树：

E,G入栈，如下图：

找到G，路径A->B->E->G。由此，我们可以看出，当遍历到的节点时，未找到目标节点而且该节点左右子树为空时，把它弹栈。

2.算法如下

int flag=1;
void FindBiTree(BiTree T, char p)  //查找指定结点，并且记录路径
{if (T == NULL)  //二叉树为空{return;}if (flag){Push(T->data);  //入栈if (T->data == p){printf("指定结点%c\n", T->data);flag = 0;  //找到指定结点，标志取0return;}}FindBiTree(T->lChild, p);FindBiTree(T->rChild, p);if ((!flag == 0)) //左右子树为空时{Pop();}
}void way(BiTree T, char p)  //输出路径
{int i;char temp[max];flag = 1;  //标志为1if (T == NULL)return;FindBiTree(T, p);for (i = 0; S.top >= 0; i++){temp[i] = Pop();  //4}printf("根结点到%c路径为长度为%d\n", p, i-1);printf("根结点到%c的路径为：\n",p);for (i--; i >= 0; i--)    //3{printf("%c", temp[i]);  //输出正确路径if(i>0)printf("->");}printf("\n");
}