BST insertion - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

BST insertion

BST insertion# JobHunting - 待字闺中

r*r2011-04-06 07:04

1 楼

这个版本的 insert 为什么不正确？谁能帮忙看看
public void insert1(T value){
if( root == null ){
root = new BSTNode(value);
}else
insertHelper(value, root);

}
private void insertHelper(T value, BSTNode node){
if( value.compareTo(node.value_) < 0 ){
if( node.left == null )
node.left = new BSTNode(node.value_);
else
insertHelper(value, node.left);
}else if( value.compareTo(node.value_) > 0 ){
if( node.right == null )
node.right = new BSTNode(node.value_);
else
insertHelper(value, node.right);
}else{
throw new RuntimeException("Duplicate Node : " + value.
toString());
}

d*12011-04-06 07:04

2 楼

逻辑上没什么不对吧。只不过可以不用recursive solution, 提高点效率

r*r2011-04-06 07:04

3 楼

写的另一个 iterative 的，就没有问题。这个调试了很久，就是不 work. 每次只是插
入重复插入第一个值。这是把 insert 定义在 BST class 里面。下面另一个
recursive 的，把 insert 定义在 node 里面，也没问题。贴出我的 node 定义。
谁再看看，上面那个的问题在哪里（注意，那个 insert 定义在 BST class 里面）？
private static class BSTNode>{
private T value_;
BSTNode left;
BSTNode right;

public BSTNode(T value){
value_ = value;
left = null;
right = null;
}

public void insert(T value){
if( value.compareTo(value_) < 0 ){
if( left == null)
left = new BSTNode(value);
else
left.insert(value);
}else if( value.compareTo(value_) > 0 ){
if( right == null )
right = new BSTNode(value);
else
right.insert(value);
}
}
}

【在 d**********1 的大作中提到】

: 逻辑上没什么不对吧。只不过可以不用recursive solution, 提高点效率

b*n2011-04-06 07:04

4 楼

should be value, not node.value_
same here

【在 r******r 的大作中提到】

: 这个版本的 insert 为什么不正确？谁能帮忙看看
: public void insert1(T value){
: if( root == null ){
: root = new BSTNode(value);
: }else
: insertHelper(value, root);
:
: }
: private void insertHelper(T value, BSTNode node){
: if( value.compareTo(node.value_) < 0 ){

d*l2011-04-06 07:04

5 楼

这问题还是挺明显的啊，就是4楼说的那样。新建左右子树的时候都是用的根节点的值
而非value，所以才会出现重复插入第一个值的情况

【在 r******r 的大作中提到】

: 写的另一个 iterative 的，就没有问题。这个调试了很久，就是不 work. 每次只是插
: 入重复插入第一个值。这是把 insert 定义在 BST class 里面。下面另一个
: recursive 的，把 insert 定义在 node 里面，也没问题。贴出我的 node 定义。
: 谁再看看，上面那个的问题在哪里（注意，那个 insert 定义在 BST class 里面）？
: private static class BSTNode>{
: private T value_;
: BSTNode left;
: BSTNode right;
:
: public BSTNode(T value){