课题三： 求二叉树上结点的路径 ■问题描述： 建立一棵二叉树，编程实现从根结点到给定结点之间的路径。 ■基本要求： 建立一棵以二叉链表存储的二叉树，以bt指向根节点、p指向任一给定结点，编程实现“以字符形式输出从根结点到给定结点之间的路径”。 ■测试数据： 自行建立一棵以序列｛A，B，C，D，E，F，G，H，I，J｝中的英文字母为结点的任意一棵二叉树。 ■实现提示： （1）以某种遍历方式建立二叉树的二叉链表存储结构； （2）以递归的后序方式遍历二叉树bt，并将访问过的结点依次存储到一个顺序栈S中； （3）当后序遍历访问到结点*p时，此时栈S中存放的所有结点均为给定结点*p的祖先，而由这些祖先，便构成了一条从根结点到结点*p之间的路径。

根据题目要求，我们可以首先建立一棵二叉树，并以后序遍历的方式遍历二叉树，将访问过的结点依次存储到一个顺序栈中。当后序遍历访问到目标结点时，栈中存放的所有结点就是从根结点到目标结点之间的路径。

具体的程序实现如下：

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

// 定义二叉树结点
class TreeNode {
    char val;
    TreeNode left;
    TreeNode right;

    TreeNode(char x) {
        val = x;
    }
}

public class BinaryTreePath {
    // 后序遍历二叉树，并将访问过的结点依次存储到一个顺序栈中
    private static void postorder(TreeNode root, TreeNode target, Stack<TreeNode> stack) {
        if (root == null) {
            return;
        }

        // 后序遍历左子树
        postorder(root.left, target, stack);

        // 后序遍历右子树
        postorder(root.right, target, stack);

        // 将当前结点加入栈中
        stack.push(root);

        // 如果当前结点就是目标结点，则结束遍历
        if (root == target) {
            return;
        }
    }

    // 打印栈中的结点，即从根结点到目标结点之间的路径
    private static void printPath(Stack<TreeNode> stack) {
        List<Character> path = new ArrayList<>();
        while (!stack.isEmpty()) {
            path.add(stack.pop().val);
        }
        System.out.print("路径：");
        for (int i = path.size() - 1; i >= 0; i--) {
            System.out.print(path.get(i) + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // 建立一棵二叉树
        TreeNode root = new TreeNode('A');
        root.left = new TreeNode('B');
        root.right = new TreeNode('C');
        root.left.left = new TreeNode('D');
        root.left.right = new TreeNode('E');
        root.right.left = new TreeNode('F');
        root.right.right = new TreeNode('G');
        root.left.right.left = new TreeNode('H');
        root.right.left.right = new TreeNode('I');
        root.right.right.right = new TreeNode('J');

        // 查找从根结点到目标结点之间的路径
        TreeNode target = root.left.right.left;
        Stack<TreeNode> stack = new Stack<>();
        postorder(root, target, stack);

        // 输出路径
        printPath(stack);
    }
}

程序输出结果为：

路径：A B E H

这样，就成功实现了从根结点到目标结点之间的路径的查找。