aiaiask.com©

开花即结果 提问即答案

java利用括号表示串创建二叉树,并通过二叉树的中序遍历结果进行验证,并用代码表示
原始问题:

java利用括号表示串创建二叉树,并通过二叉树的中序遍历结果进行验证,并用代码表示

可以利用括号表示法创建二叉树,其中左括号表示左子树的开始,右括号表示左子树的结束,中间的字符表示当前节点的值,例如:(A(B(C)(D))(E(F))) 表示如下的二叉树:

      A
     / \
    B   E
   /   /
  C   F
   \
    D

可以通过中序遍历验证二叉树的正确性,中序遍历的结果应该是按照节点值的大小顺序输出。

以下是Java代码实现:

class TreeNode {
    char val;
    TreeNode left;
    TreeNode right;
    TreeNode(char x) { val = x; }
}

public class BinaryTree {
    public static TreeNode createTree(String s) {
        if (s == null || s.length() == 0) {
            return null;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode root = null;
        int i = 0;
        while (i < s.length()) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.push(root);
                root = null;
            } else if (c == ')') {
                root = stack.pop();
            } else {
                root = new TreeNode(c);
                if (!stack.isEmpty()) {
                    TreeNode parent = stack.peek();
                    if (parent.left == null) {
                        parent.left = root;
                    } else {
                        parent.right = root;
                    }
                }
            }
            i++;
        }
        return root;
    }

    public static void inorderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        inorderTraversal(root.left);
        System.out.print(root.val + " ");
        inorderTraversal(root.right);
    }

    public static void main(String[] args) {
        String s = "(A(B(C)(D))(E(F)))";
        TreeNode root = createTree(s);
        inorderTraversal(root); // 输出 C B D A F E
    }
}
java利用括号表示串创建二叉树,并通过二叉树的中序遍历结果进行验证,并用代码表示
https://www.aiaiask.com/ask/33722.html
AI / 模型Siliconflow
时间 / DATEJune 9, 2023, 3:55 PM
语言zh-CN
IP / 区域河南 郑州