Java求二叉树根结点到r结点之间的路径

Question

问题描述：求二叉树根结点到r结点之间的路径

Description：
假设二叉树采用二叉链表方式存储，root指向根结点，r所指结点为任一给定的结点。请编程，求出从根结点到结点r之间的路径。
Input
输入有若干种情况，每种情况二行，第一行是一个按顺序存储的二叉树。如果结点处空用半角的‘.’代替。第二行是一个要查找的结点r。
Output
每个案例输出一行，输出从根结点到结点r之间的路径。

import java.util.*;

public class Main {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner cin = new Scanner(System.in);
        while (cin.hasNext()) {
            String str = cin.next();
            // 根据顺序存储的二叉树创建连式存储的二叉树
            BinaryTree<Character> tree = new BinaryTree<Character>(str);
            

        }

    }


}

class BinaryNode<T> {
    // 数据
    T data;
    // 左孩子
    BinaryNode<T> left;
    // 右孩子
    BinaryNode<T> right;

    public BinaryNode(T data, BinaryNode<T> left, BinaryNode<T> right) {
        super();
        this.data = data;
        this.left = left;
        this.right = right;
    }

    public BinaryNode() {
        super();
    }

    // 根据节点的内容创建节点
    public BinaryNode(T data) {
        this(data, null, null);
    }

    // 判断节点是否为叶子节点
    public boolean isLeaf() {
        return left == null && right == null;
    }

    // 遍历节点
    @Override
    public String toString() {
        return data.toString();
    }

}

class BinaryTree<T> {

    BinaryNode<T> root;

    public BinaryTree(BinaryNode<T> root) {
        super();
        this.root = root;
    }

    // 1 空树
    public BinaryTree() {
        super();
        root = null;
    }

    public BinaryTree(String str) {
        super();
        root = createTree(str, 0);
    }

    // 2 判空
    public boolean isEmpty() {
        return root == null;
    }

    public void levelOrder() {

        this.levelOrder(root);
    }

    // 层次遍历
    public void levelOrder(BinaryNode<T> p) {
        Queue<BinaryNode<T>> q = new LinkedList<BinaryNode<T>>();
        q.add(p);

        while (!q.isEmpty()) {
            BinaryNode<T> t = q.poll();
            System.out.print(t.data.toString());
            if (t.left != null) {
                q.add(t.left);

            }
            if (t.right != null) {
                q.add(t.right);
            }

        }

    }

    //
    public BinaryNode<T> createTree(String str, int i) {

        BinaryNode p = null;

        if (i < str.length() && str.charAt(i) != '.') {
            // 创建根节点
            p = new BinaryNode(str.charAt(i));
            p.left = createTree(str, 2 * i + 1);
            p.right = createTree(str, 2 * i + 2);

        }

        return p;

    }

}

Answer 1

你把树存对，然后用深搜 找节点不就能完成需求了吗。