w****x
发帖数: 2483 | 1 输入是一个node*, 如果是node*那么不能仅仅根据值来搜索这个节点, 因为不同的节点
可以对应同一个值, 最差还是得搜索n次 | w****x
发帖数: 2483 | 2 输入是一个node*, 如果是node*那么不能仅仅根据值来搜索这个节点, 因为不同的节点
可以对应同一个值, 最差还是得搜索n次 | a*******8
发帖数: 110 | | z*********8
发帖数: 2070 | 4 考虑duplicate值就太没意思了
【在 w****x 的大作中提到】
: 输入是一个node*, 如果是node*那么不能仅仅根据值来搜索这个节点, 因为不同的节点
: 可以对应同一个值, 最差还是得搜索n次
| H****r
发帖数: 2801 | 5 search (*node+1) ?
【在 w****x 的大作中提到】
: 输入是一个node*, 如果是node*那么不能仅仅根据值来搜索这个节点, 因为不同的节点
: 可以对应同一个值, 最差还是得搜索n次
| m********g
发帖数: 272 | 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********g
发帖数: 272 | 7 编译过，但是没运行过。
let me know, if you find any bugs. |
|
