Построение бинарного дерева с заданным предзаказом

Question

Я пытаюсь построить бинарное дерево с только при preorder.

Мой подход - пройти массив и проверить каждый элемент. Если элемент является оператором (+, -, *, /), тогда я устанавливаю текущий элемент как root и устанавливаю 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 

Объяснение:

• Понять, что операнды (переменные) всегда будет листовыми узлами .Корневой узел дерева также может быть листовым узлом (возникает, когда во всем выражении присутствует только 1 операнд).

• Теперь, так как вы упомянули preorder traversalБТ, мы следуем подходу слева направо и используем стек для создания нашего двоичного дерева.

• Всякий раз, когда мывидим операнд (+, -, *, /), мы создаем новый узел (очевидно) и помещаем его в стек.Причина, по которой мы его выдвигаем, заключается в том, что для того, чтобы все выражение имело смысл, нам все еще нужно собрать его правильное поддерево (которое появится в будущих значениях массива).

• По подход слева направо Я имею в виду, что мы выбираем родителя текущего узла из стека (если он не пустой) и проверяем, оставлен ли он в подпрограммедерево равно нулю, если да, назначьте там ребенка, иначе назначьте его справа.Мы делаем это, поскольку данный вам обход равен предзаказ .

• Мы снова помещаем это new_node, если это operator в стек для размещения будущих переменныхкак это листовые узлы.Например, {"-,"-","x","y"}.Таким образом, дерево для него будет выглядеть так:

      -
     /  
    -
   / \
  x   y
  

• В приведенном выше выражении y присвоено его родительскому элементу -, а затем мы удалим самый последний - из стека, так как он нам больше не нужен.

• Теперь в стеке остается просто -, который является корневым узлом.Затем мы переходим к дальнейшим значениям в массиве и определяем их, как описано выше.