如何在不排序的情况下构建二进制树,I.E
如果我有一个输入5 4 9 8 1 2 7,你怎么能把它插入到一个基于引用的二进制树中呢。我知道使用Array可以很容易地实现这一点,但使用参考库是否可能?
Tree buildTree(int[] array, int index) {
if(index > array.length) { return null; }
return new Tree(
array[index],
buildTree(array, 2 * index + 1),
buildTree(array, 2 * index + 2));
}
大部分工作都在递归和索引中,但也不算太糟。
一个简单的规则是始终插入到左边的子树中,然后切换子树。右边的子树总是比左边的子树大0-1个元素,所以你总是可以插入左边的子树。现在,左子树比右子树大0-1个元素,因此需要切换子树以保持不变。在伪代码中:
insert(t,v) {
if (t == null) {
return new TreeNode(v,null,null)
} else {
left = insert(t.left,v)
right = t.right
t.left = right
t.right = left
return t
}
}