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

Question

public class Tree { 节点根;

// 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);

其次，编写一个函数来从给定值中获取节点(留作练习，考虑一下，提示：递归二叉搜索(。

第三，你需要一个函数来插入一个节点(留给你一个练习(，所以你需要：

1. 找到指向应该插入的节点的节点(如果你解决了第二个点，那应该很容易(
2. 将节点连接到现有节点(简单(

Answer 2

我相信你的错误在这里：

root= new TreeNode(C[0]);

在left不为 0 的情况下，不应使用C[0]。

编辑：

我不知道这些元素是否已插入到 BST 中。

看来你的怀疑是正确的。你永远不会设置TreeNode.left或TreeNode.right任何东西，这对于构建一棵树是必要的。