如何创建不平衡的二叉搜索树

Question

// Tree Node 
static class Node { 
    int data; 
    Node left, right; 
    Node(int data) 
    { 
        this.data = data; 
        this.left = null; 
        this.right = null; 
    } 
    @Override public String toString() { 
     return String.valueOf(data); 
     }
} 

// Function to insert nodes in level order 
public Node insertLevelOrder(int[] arr, Node root, 
                                            int i) 
{ 
    // Base case for recursion 
    if (i < arr.length) { 
        Node temp = new Node(arr[i]); 
        root = temp; 

        // insert left child 
        root.left = insertLevelOrder(arr, root.left, 
                                         i + 1); 

        // insert right child 
        //root.right = insertLevelOrder(arr, root.right, 
                                          // 2 * i + 2); 

        //System.out.println(root);  
    } 
    return root; 
} 

// Function to print tree nodes in InOrder fashion 
public void inOrder(Node root) 
{ 
    if (root != null) { 
        inOrder(root.left); 
        System.out.print(root.left + " "); 
        //inOrder(root.right); 
    } 
} 

// Driver program to test above function 
public static void main(String args[]) 
{ 
    Tree t2 = new Tree(); 
    int arr[] = {9,5,0,-3,-10}; 
    t2.root = t2.insertLevelOrder(arr, t2.root, 0); 
    t2.inOrder(t2.root); 
} 
} 

我不知道这些节点是否被插入，但输出结果是正确的。我只想插入节点到左边的孩子，我可以消除那代码吗？root.right=insertLevelOrder（arr,root.right,2*i+2)；

还有为什么这个循环没有“i++”的符号，int i是如何自动增加的？

Answer 1

有很多缺失的东西。我不会为你解决一切（那不是SO的目的），而是会给你暗示。

首先，你需要有一些东西来建立一个树（设置一个节点的左右节点）：

public class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) {
         val=x;
     }
     TreeNode(int v,TreeNode l,TreeNode r) {
         this(x);
         left = l;
         right = l;
     }   
     @Override public String toString() {
         return "(" + (left==null?"*":left) + "," + val + "," + (right==null?"*":right) + ")";
     }
}

因此，您可以创建（并打印）如下所示的树（例如）：

TreeNode n1 = new TreeNode(1);
TreeNode n3 = new TreeNode(3);
TreeNode n2 = new TreeNode(2,n1,n3);
TreeNode n4 = new TreeNode(4,n3,null);
System.out.println(n4);

null