import java.util.Stack; public class BinaryTree { private TreeNode root;//根节点 public BinaryTree() { root = null; } public void inOrder(TreeNode root) { if(root == null) { return; } inOrder(root.leftChild); System.out.print(root.item+" "); inOrder(root.rightChild); } public TreeNode createTree(String str) { // 利用括号表示串创建二叉树。 // 请在这里补充代码，完成本关任务 Stack<TreeNode> st=new Stack<TreeNode>(); //建立一个栈st TreeNode p=null; boolean flag=true; char ch; int i=0; while (i<str.length()) {//循环扫描str中每个字符 ch=str.charAt(i); switch(ch) { // ********** Begin ********* // ********** End ********** } i++; //继续遍历 } return root; } public static class TreeNode { private TreeNode leftChild; private TreeNode rightChild; private char item; public TreeNode(char item) { this(null, null, item); } public TreeNode(TreeNode leftChild, TreeNode rightChild, char item) { this.leftChild = leftChild; this.rightChild = rightChild; this.item = item; } } }

这段代码是一个Java实现的二叉树，其中包含一个内部类TreeNode，表示二叉树的节点，每个节点包含左子树、右子树和一个字符元素。createTree(String str)方法利用括号表示法创建二叉树，具体实现是通过一个栈来实现的。在遍历括号表示串时，如果遇到左括号，则创建一个新节点，并将其压入栈中；如果遇到右括号，则弹出栈顶的两个节点作为当前节点的左右子树，同时将当前节点压入栈中。最终栈中只剩下一个节点，即二叉树的根节点，返回该节点即可。

相关问题

课题三： 求二叉树上结点的路径 ■问题描述： 建立一棵二叉树，编程实现从根结点到给定结点之间的路径。 ■基本要求： 建立一棵以二叉链表存储的二叉树，以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

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

二叉树前序遍历java

以下是Java实现二叉树前序遍历的两种方法：

1. 递归方法：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode(int val) {
        this.val = val;
    }
}

public class BinaryTree {
    public void preorderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        
        System.out.print(root.val + " "); // 先访问根节点
        preorderTraversal(root.left); // 再访问左子树
        preorderTraversal(root.right); // 最后访问右子树
    }
}

// 创建二叉树
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

// 调用前序遍历方法
BinaryTree binaryTree = new BinaryTree();
binaryTree.preorderTraversal(root); // 输出：1 2 4 5 3

2. 栈方法：

import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode(int val) {
        this.val = val;
    }
}

public class BinaryTree {
    public void preorderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            System.out.print(node.val + " "); // 先访问根节点
            
            if (node.right != null) {
                stack.push(node.right); // 右子树入栈
            }
            
            if (node.left != null) {
                stack.push(node.left); // 左子树入栈
            }
        }
    }
}

// 创建二叉树
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

// 调用前序遍历方法
BinaryTree binaryTree = new BinaryTree();
binaryTree.preorderTraversal(root); // 输出：1 2 4 5 3