Question

假设二叉树采用二叉链存储结构，p为任一给定的节点，设计一个算法输出从根节点到p所指节点之间的路径

急求！！！

Answer 1

1. 调用如下方法即可，最终的路径存储在数组array中。
2. 其中返回的pos即为路径中的结点个数。从pos-1位置反序输出数组即为从根到结点的路径
3. array的长度需要大于树的深度，否则可能溢出，调用形式如下：
#define MAX_LEN 100 //树的最大深度，假设不大于100
TreeNode *array[MAX_LEN];
int path_len = 0;
findTheRoad(&root, p, array, path_len);//root是树的根结点，p是要找的结点的指针
4. 执行完后可以通过如下方式遍历整个路径：
for(int i = path_len - 1; i >= 0; i--)
{
//输出array[i]即可，如printf("%d ",array[i]->data);
}
5. findTheRoad方法的实现如下：
bool findTheRoad(TreeNode *root, TreeNode *p, TreeNode *array[], int &pos)
{
if (root == NULL)
return false;
if (findTheRoad(root->left, p, array, pos) || findTheRoad(root->right, p, array, pos))
{
array[pos++] = root;
return true;
}
if (root == p)
{
array[pos] = root;
return true;
}
return false;
}

Answer 2

数据结构中典型题