按顺序遍历输入字符串到二叉树

Question

我正在创建一个程序，它接受二叉树的括号表示法，然后提供各种功能，例如中序遍历。

为了这个例子：输入是 G(Y(u)(5))(2(t)).

遍历树时，我的代码只返回 Y G u ，但它应该返回 u Y 5 G 2 t。

我的主要方法为用户提供了一个GUI来输入二叉树字符串。我有一个单独的类来构造二叉树并包含一个构造每个节点的私有类。

我已经检查了我的代码，但不太清楚问题出在哪里。 我已经查看了 Geeks for Geeks 以及 YouTube 视频，但我在理解这个概念时遇到了问题。

public class BinaryTree {
    Node root;
    Node parent;
    Character c;
    String r;
    String tree;

    public BinaryTree(String tree) { // constructor
        this.tree = tree;
    }

    public Node strToTree(String tree) {
        Queue<String> queue = new LinkedList<>(); 
        Stack<String> stack = new Stack<>(); 
        String[] a = tree.split(""); 
        int i = 0;

        while (i < tree.length()) { // holds string's chars
            queue.add(a[i]);
            i = i + 1;
        }

        while (!queue.isEmpty()) { 
                String b = queue.remove();
            if (!b.equals("(")) {
                stack.push(b); // stores closed brackets, number, & letters
                if (b.equals(")") & !stack.isEmpty()) {
                    stack.pop(); // parenthesis
                    String e = stack.pop(); // character
                    String f = stack.lastElement();
                    c = e.charAt(0);
                    char g = f.charAt(0);
                    root = new Node(c);
                    parent = new Node(g);
                    if (parent.left == null) {
                        parent.left = root;
                        parent = parent.left;
                    } else
                        parent.right = root;
                }
            }
        }

        return root;
    }

    public void inOrderTraverse(String tree) {
        Node root = new Node(tree.charAt(0));
        Node left = new Node(tree.charAt(2));
        Node right = new Node(tree.charAt(4));
        getString(tree);
        root.inOrderTraverse(left);
        root.inOrderTraverse(root);
        root.inOrderTraverse(right);
        root.inOrderTraverse(left.left); // testing case
    }

    static class Node {
        char data;
        Node left;
        Node right;
        Node root;

        private Node(char data) { // constructor
            this.data = data;
            left = null;
            right = null;
        }

        public void inOrderTraverse(Node root) {
            if (root == null)
                return;

            /* first recur on left child */
            inOrderTraverse(root.left);
            // (root.left);

            /* then print the data of node */
            System.out.print(root.data + " ");

            /* now recur on right child */
            inOrderTraverse(root.right);// root.right);
        }
    }
}

Answer 1

strToTree

中的逻辑不正确。一些问题：

• 每次处理“）”时，

  root

  变量都会被新节点覆盖——因此会丢失之前的任何内容。

• 每当遇到“）”时，您都必须创建两个节点是不对的。

• stack.lastElement()

  可以在空栈上执行...

• 通过设置

  parent.right = root;

  你承认

  root

  有一个父母，所以

  return root

  不返回根。

• if (parent.left == null) {

  可能不是检测左孩子必须接收新孩子的正确方法。考虑一个输入可能有

  A()(C)

  来表示“A”没有左孩子，但有一个右孩子 (C)。您需要以某种方式注册

  ()

  是 left 孩子的输入，保留它

  null

  ，而下一个信息将为右孩子服务。

• ...

其他备注：

• Node

  班不应该有

  root

  成员。只有

  BinaryTree

  班应该有那个。

• BinaryTree

  类不应该需要

  parent

  （树没有父母），

  c

  （应该只是一个局部变量），

  r

  （？），甚至不需要

  tree

  （因为那是应立即转换为树本身的字符串输入——没有必要保留它）。所以一棵树唯一需要的属性就是它的

  root

  .

• strToTree

  应该更好地返回一个新的

  BinaryTree

  实例而不是

  Node

  。所以它应该是一个静态方法，或者更好的是，类的构造函数。

• 我不明白你打算用你在

  inOrderTraverse

  课上的

  BinaryTree

  方法做什么。它应该只调用

  Node

  类上的同名方法。

• inOrderTraverse

  类的

  Node

  方法应该是静态的（它不使用current节点

  this

  ）。

• 使用

  Queue

  是矫枉过正。您可以只迭代输入字符串的字符。

• 要跟踪输入字符串中的下一个标记是关于左孩子还是右孩子，您还可以为堆栈中的每个节点堆栈一个布尔值。例如，你可以有一堆成对的，或者只有两个串联操作的堆栈。

这里是你的代码的大修：

public class BinaryTree {
    Node root;

    public BinaryTree(String input) {
        root = null;
        Stack<Node> stack = new Stack<>();
        Stack<Boolean> sidestack = new Stack<>(); 
        for (int i = 0; i < input.length(); i++) {
            char ch = input.charAt(i);
            if (ch == ')') {
                if (input.charAt(i-1) != '(') { // Exclude empty node 
                    stack.pop(); // This node has no more children to add
                    sidestack.pop();
                }
            } else if (ch != '(') {
                Node node = new Node(ch);
                if (stack.isEmpty()) {
                    root = node; 
                } else {
                    boolean side = sidestack.peek();
                    if (side) {
                        stack.peek().right = node;
                    } else {
                        stack.peek().left = node;
                    }
                    sidestack.pop();
                    sidestack.push(!side); // Toggle child
                }
                stack.push(node);
                sidestack.push(false);
            }
        }
    }

    public void inOrderTraverse() {
        Node.inOrderTraverse(root);
    }
    
    static class Node {
        char data;
        Node left;
        Node right;

        private Node(char data) { // constructor
            this.data = data;
            left = null;
            right = null;
        }

        static public void inOrderTraverse(Node root) {
            if (root == null)
                return;
            inOrderTraverse(root.left);
            System.out.print(root.data + " ");
            inOrderTraverse(root.right);
        }
    }

    // Demo
    public static void main(String[] args) {
        String input = "G(Y(u)(5))(2()(t))";
        BinaryTree tree = new BinaryTree(input);
        tree.inOrderTraverse();
    }
    
}