java - 构造具有给定预序的二叉树

Question

我正在尝试构造一棵二叉树，仅给定一个预序。

我的方法是遍历数组并检查每个元素。如果元素是运算符 (+, -, *,/)，那么我将当前元素设置为根并设置 root.left 和 root.right 分别为 array[i + 1] 和 array[i + 2]。

如果当前元素不是运算符，我会打印出该元素。

我想如果我递归地这样做，我将能够构建一个二叉树。但是，我遇到了一些错误，我不确定我是否朝着正确的方向前进。

到目前为止，这是我的代码:

class Node {
    Object data;
    Node left, right;

    Node(Object item) {
        data = item;
        left = right = null;
    }
}

public class MyTree {
    Node root;

    public MyTree() {
        root = null;
    }

    private static String[] array;
    private static MyTree01 tree = new MyTree();

    static void createBT(Node node) {

        if (array == null) return;

        for (int i = 0; i < array.length; i++) {
            if (array[i] == "-" || array[i] == "+" || array[i] == "*" || array[i] == "/") {
                tree.root = new Node(array[i]);
                tree.root.left = new Node(array[i + 1]);
                tree.root.right = new Node(array[i + 2]);

                createBT(tree.root.left);
                createBT(tree.root.right);

            } else {
                System.out.println(node.data + " ");
            }
        }
    }

    void createBT() {
        createBT(root);
    }

    public static void main(String[] args) {
        array = new String[] {"-", "-", "x", "y", "*", "+", "s", "t", "/", "x", "s"};
        createBT(tree.root);
    }
}

同样，我不确定我是否正朝着正确的方向前进。我需要一些指导，如果我的方法完全错误，请告诉我!

Answer 1

import java.util.*;
class Node {
    String data;
    Node left, right;

    Node(String item) {
        data = item;
        left = right = null;
    }
}
public class Algo{   
    public Node createBT(String[] arr){
       Node root = null;
       if(arr == null || arr.length == 0) return root;// to handle edge case of empty lists.
       Stack<Node> st = new Stack<>();

       for(int i=0;i<arr.length;++i){
            Node new_node = new Node(arr[i]);
            attachChildToParent(st,new_node);// attach child to it's parent(which will be most recent/top in the stack)
            if(root == null) root = new_node;
            if(isOperator(arr[i])){                                                  
                st.push(new_node); // only push operators to stack as operands will always be leaf nodes
            }
       }

       return root;
    }    

    private boolean isOperator(String s){
        return s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/");
    }

    private void attachChildToParent(Stack<Node> st,Node child_node){
        if(st.isEmpty()) return;
        Node parent_node = st.peek();
        if(parent_node.left == null){
            parent_node.left = child_node;
        }else{
            parent_node.right = child_node;
            st.pop(); // no need to keep parent in the stack anymore since we assigned nodes on both ends(left and right) 
        }
    }

    private void preorder(Node root,List<String> nodes){
        if(root == null) return;
        nodes.add(root.data);
        preorder(root.left,nodes);
        preorder(root.right,nodes);        
    }

    public static void main(String[] args) {
        String[][] test_cases = new String[][]{
            {"-", "-", "x", "y", "*", "+", "s", "t", "/", "x", "s"},
            {"/","-", "-", "x", "y", "*", "+", "s", "t", "/", "x", "s","t"},
            {"y"}
        };        
        Algo obj = new Algo();
        for(int i=0;i<test_cases.length;++i){
            Node root = obj.createBT(test_cases[i]);
            List<String> preorder_result = new ArrayList<>();
            obj.preorder(root,preorder_result);
            boolean expected_success = true;
            for(int j=0;j<test_cases[i].length;++j){
                if(!test_cases[i][j].equals(preorder_result.get(j))){
                    expected_success = false;
                    break;
                }                
            }
            System.out.println("Test Case: " + Arrays.toString(test_cases[i]));
            if(expected_success){
                System.out.println("Result: ok");
            }else{
                System.out.println("Result: not ok");
            }
        }

    }
}

输出:

Test Case: [-, -, x, y, *, +, s, t, /, x, s]
Result: ok
Test Case: [/, -, -, x, y, *, +, s, t, /, x, s, t]
Result: ok
Test Case: [y]
Result: ok 

解释:

• 理解操作数(变量)永远是叶节点。树的根节点也可以是叶节点(当整个表达式中只有一个操作数时出现)。

• 现在，由于您提到了 BT 的前序遍历，我们遵循左优先方法并使用堆栈 创建我们的二叉树。

• 每当我们看到一个操作数(+、-、*、/)时，我们都会创建一个新节点(显然)并将其压入堆栈。我们推送它的原因是因为为了使整个表达式有意义，我们仍然需要收集它的正确子树(它将出现在数组的 future 值中)。

• 通过左优先方法 我的意思是，我们从堆栈中获取当前节点的父节点(如果它不为空)并检查它的左子树是否为空，如果是的，将 child 分配到那里，否则将其分配到右边。我们这样做是因为提供给您的遍历是预序。

• 如果 new_node 是一个 operator，我们再次将它插入堆栈以容纳 future 的变量，因为它是叶节点。例如，{"-,"-","x","y"}。所以，它的树看起来像，

      -
     /  
    -
   / \
  x   y
  

• 在上面的表达式中，y 被分配给它的父 - 然后我们从堆栈中删除最近的 -因为我们不再需要它。

• 现在，堆栈中剩下的只是-，它是根节点。然后我们继续处理数组中的其他值，并如上所述为它们做出决定。