麻烦谁贴一个bug free的BST next node - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

麻烦谁贴一个bug free的BST next node

麻烦谁贴一个bug free的BST next node# JobHunting - 待字闺中

w*x2012-03-08 08:03

1 楼

输入是一个node*, 如果是node*那么不能仅仅根据值来搜索这个节点, 因为不同的节点
可以对应同一个值, 最差还是得搜索n次

w*x2012-03-08 08:03

2 楼

输入是一个node*, 如果是node*那么不能仅仅根据值来搜索这个节点, 因为不同的节点
可以对应同一个值, 最差还是得搜索n次

a*82012-03-08 08:03

3 楼

有parent pointer吗？

z*82012-03-08 08:03

4 楼

考虑duplicate值就太没意思了

【在 w****x 的大作中提到】

: 输入是一个node*, 如果是node*那么不能仅仅根据值来搜索这个节点, 因为不同的节点
: 可以对应同一个值, 最差还是得搜索n次

H*r2012-03-08 08:03

5 楼

search (*node+1) ?

【在 w****x 的大作中提到】

: 输入是一个node*, 如果是node*那么不能仅仅根据值来搜索这个节点, 因为不同的节点
: 可以对应同一个值, 最差还是得搜索n次

m*g2012-03-08 08:03

6 楼

public static Node successorInBST(Node root, int key)
{
Node pos = findInBST(root, key);

if(pos == null)
{
throw new IllegalArgumentException("Cannot find the key in the
BST");
}

if(pos.getRight() != null)
{
return findSmallest(pos.getRight());
}

Node successor = null;

while(root != null)
{
if(key < root.getKey())
{
successor = root;
root = root.getLeft();
}
else if(key > root.getKey())
{
root = root.getRight();
}
else
{
break;
}
}

return successor;
}

private static Node findSmallest(Node root)
{
Validate.notNull(root, "root cannot be null");

while(root.getLeft() != null)
{
root = root.getLeft();
}

return root;
}

private static Node findInBST(Node root, int key)
{
Node p = root;

while(p != null)
{
if(p.getKey() == key)
{
return p;
}
else if(p.getKey() > key)
{
p = p.getLeft();
}
else
{
p = p.getRight();
}
}

return null;
}

m*g2012-03-08 08:03

7 楼

编译过，但是没运行过。
let me know, if you find any bugs.