java - 打印所有节点，包括节点java

Question

我想创建一个二叉搜索树工具，在其中输出所有节点，包括空节点在我当前的代码中，它仅在输入数组中创建节点，包括其左侧和子节点，然后打印

是否可以打印包括 null 在内的所有节点，如下所示？输入 = {23, 5, 2, 89, 56, 43}输出 = {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, null, 56, null, null, null ,null ,null, null, 43, null

因为结构如下所示。

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

注意:n 表示 null [空节点]

相反，如果您进行级别顺序遍历(正如您在评论部分中提到的)，您将得到以下结果:

23, 5, 89, 2, null, 56, null, null, null, 43, null, null, null

如果您清楚这一点，则可以执行以下操作来打印节点(如果它具有值或即使没有值)。

1. 将根放入队列并处理它。
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+" ");
        }
    }
}

注意:如果你没有得到什么，请发表评论。