第 42 题
（12 分）假设二叉树采用二叉链存储结构存储，设计一个算法，求出根结点到给定某结点之间的路径，要求：
（1）给出算法的基本设计思想。
（2）写出二叉树采用的存储结构代码。
（3）根据设计思想，采用 C 或 C++语言描述算法，关键之处给出注释。
[tag_link]
【答案】
（1）算法的基本设计思想：采用递归的深度优先搜索（DFS）方法。从根结点开始，先序遍历二叉树，在遍历过程中使用一个动态数组（如向量）记录当前访问路径。当访问到目标结点时，当前数组中的结点序列即为根结点到目标结点的路径；如果当前结点不是目标结点，则递归遍历其左子树和右子树。若左右子树均未找到目标结点，则进行回溯，从路径中移除当前结点，并返回上一层继续搜索。这种方法利用回溯确保路径的正确性。
（2）二叉树采用的存储结构代码（C 语言描述）：
typedef struct BiTNode {
char data; // 结点数据，假设为字符型
struct BiTNode *lchild, *rchild; // 左右孩子指针
} BiTNode, *BiTree;
（3）算法描述（C++ 语言，基于上述存储结构）：
#include <vector>
using namespace std;
// 函数功能：查找从根结点到目标结点的路径
// 参数：root 为当前子树根结点，target 为目标结点，path 用于存储路径
// 返回值：bool 类型，找到路径返回 true，否则返回 false
bool findPath(BiTree root, BiTree target, vector<BiTree> &path) {
if (root == nullptr) return false; // 空树，直接返回 false
path.push_back(root); // 当前结点加入路径
if (root == target) return true; // 找到目标结点，返回 true
if (findPath(root->lchild, target, path)) return true; // 递归搜索左子树
if (findPath(root->rchild, target, path)) return true; // 递归搜索右子树
path.pop_back(); // 左右子树均未找到，回溯，移除当前结点
return false;
}
// 调用示例：假设 root 为根结点指针，target 为目标结点指针，path 为空的 vector<BiTree> 类型，
// 调用 findPath(root, target, path) 后，若返回 true，则 path 中存储从根到目标的路径结点序列。
【解析】算法的核心思想是递归深度优先搜索，结合回溯记录路径。从根结点开始，先访问当前结点并加入路径，然后判断是否为给定结点：若是则成功；否则递归搜索左子树和右子树。递归调用前将当前结点加入路径，调用后若子树中找到目标，则当前结点保留在路径中（因为它是路径的一部分），否则通过 pop_back() 移除当前结点，实现回溯。这保证了路径从根结点到目标结点的顺序性。存储结构采用二叉链，每个结点包含数据域和左右孩子指针，便于递归遍历。算法的时间复杂度为 O(n)，其中 n 为二叉树结点数，最坏情况下需要遍历所有结点；空间复杂度为 O(h)，h 为二叉树高度，主要由递归栈和路径向量占用，路径向量最多存储 h 个结点。该算法简洁有效，适用于二叉链存储的二叉树路径查找问题。