Распечатать все узлы, включая узлы java

Question

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

Is it Можно распечатать все узлы, в том числе в ноль, как показано ниже? input = {23, 5, 2, 89, 56, 43} output = {23, 5, 89, 2, null, 56, null, null, null, null, null, null, 43, null}

public class Node {
    int value;
    Node right,left;
    Node(){
        value = 0;
        left = null;
        right = null;  
    }

    Node(int i) {
        value = i;
        left = null;
        right = null;
    }
    public void setLeft(Node newValue){
        this.left = newValue;
    }
    public void setRight(Node newValue){
        this.right = newValue;
    }
    public int getValue(){
        return value;
    }
    public String getValueStr(){
        return Integer.toString(value);
    }
    public void printAll(){
        System.out.println("Value: "+ this.value
                +"\nLeft: "+ this.left
                +"\nRight: "+ this.right);
    }
    public void addChildToArr(ArrayList<String> arr){
        arr.add(right.getValueStr());
        arr.add(this.left.getValueStr());
    }
    public String getChildRightStr(){
        if(right == null)
            return "null";
        else
            return this.right.getValueStr();
    }
    public String getChildLeftStr(){
        if(left == null)
            return "null";
        else
            return this.left.getValueStr();
    }
}

public class BST {
    private static Node root;
    ArrayList<Node> nodes = new ArrayList<>();
    public BST(){
        root = null;
    }
     public void insert(int data)
     {
         root = insert(root, data);
     }
     /* Function to insert data recursively */
     private Node insert(Node node, int data)
     {
         if (node == null)
             node = new Node(data);
         else
         {
             if (data <= node.getValue()){
                 node.left = insert(node.left, data);
                 //nodes.add(node.left);
             }
             else{
                 node.right = insert(node.right, data);
                 //nodes.add(node.left);
             }
         }
         if(!(nodes.contains(node)))
             nodes.add(node);
         return node;
     }

    public void printNodes(){
        for(int i = 0; i < nodes.size();i++){
            System.out.print(nodes.get(i).getChildLeftStr()+" ,"+nodes.get(i).getChildRightStr()+", ");
        }
        System.out.println("");
    }
    public void printNodeObj(){
        for(int i = 0; i < nodes.size();i++){
            System.out.println(nodes.get(i));
        }
    }
    public int countNodes()
     {
         return countNodes(root);
     }
     /* Function to count number of nodes recursively */
     private int countNodes(Node r)
     {
         if (r == null)
             return 0;
         else
         {
             int l = 1;
             l += countNodes(r.getLeft());
             l += countNodes(r.getRight());
             return l;
         }
     }
    public static void main(String[] args) {
        BST bst = new BST();
        int[] arr = {23,5,2,89,56,43,38,10,65,72};
        System.out.print("["+arr[0]+", ");
        for(int i = 0; i< arr.length;i++)
            bst.insert(arr[i]);
        bst.printNodes();
    }
}

Спасибо за помощь.

Answer 1

Прежде всего вы делаете BST, используя значения

23, 5, 2, 89, 56, 43

, вы не получите результат как

23, 5, 89, 2, ноль, 56, нуль, ноль, ноль, ноль, ноль, ноль, 43, нуль

, так как структура будет похожа следующий.

         23
        /  \
      5     89
     / \    / \
    2   n  56  n
   / \     / \
  n  n    43  n
         / \
         n  n

Примечание: n обозначает ноль [пустые узлы]

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

23, 5, 89, 2, ноль, 56, ноль, ноль, ноль, 43, ноль, ноль, ноль

Если вы подтвердите это, вы можете сделать Чтобы распечатать узел, если он имеет значение или даже если он не имеет значения, выполните следующие действия.

1. поставьте root в очередь и обработайте его.
2. опросите первый вставленный элемент из очереди.
3. если опрашиваемый элемент оставил дочерний элемент, обработайте его и поместите этот элемент в очередь, иначе выведите 'null'
4. , если опрашиваемый элемент имеет правый дочерний элемент, обработайте и поместите этот элемент в очередь, иначе выведите «null»
5. и переходите к шагу 2, пока очередь не станет пустой.

код:

private static void print(Node root) {
    Queue<Node> queue = new LinkedList<Node>();
    queue.add(root);

    /* step 1 */
    System.out.print(root.val+" "); 
    while(!queue.isEmpty()) {
         /* step 2 */
        BST temp = queue.poll();

        /* step 3 */
        if(temp.left != null) { 
            System.out.print(temp.left.val+" ");
            queue.add(temp.left);
        }else {
            System.out.print(temp.left+" ");
        }

        /* step 4 */
        if(temp.right != null) {
            System.out.print(temp.right.val+" ");
            queue.add(temp.right);
        }else {
            System.out.print(temp.right+" ");
        }
    }
}

Примечание: прокомментируйте, если вы не получаете что-то.