BST 中序遍历是 从小到大排序的
1.查找后继(找第一个比他大的数)
根据BST的 左小右大性质
1.若该节点有右孩子,则找 该右子数的最下值
2.如该节点无右孩子, 不断寻找祖先P1 如果P1的父节点G1 且G1.letfChild =P1 则找到了第一个比他大的数 若无则为空
代码:
@Override public K successor(K x) { BSTNode<K, V> xNode = lookupNode(x); if (xNode==null) return null; if (xNode.right!=null){//1.有右孩子 找右字数中的最小值 return minNode(xNode.right).key; } //2.无右孩子 斜线的拐角 也就是是第一个比当前节点大的节点 BSTNode<K, V> fNode = xNode.parent; while (fNode!=null&&xNode==fNode.right){ xNode=fNode; fNode=fNode.parent; } //找到根 或者找到了 右斜线的拐角 也就是是第一个比当前节点key大的节点 return fNode==null?null:fNode.key; }
2.查找前驱 (找一个第一个比他小的)
1.有左孩子 则在左子树中找一个最大值
2.无左孩子 不断寻找祖先P1 如果P1的父节点G1 且G1.letfChild =P1 则找到了第一个比他大的数 若无则为空
代码:
//找一个比它小的
@Override
public K predecessor(K x) {
BSTNode<K, V> xNode = lookupNode(x);
if (xNode==null) return null;
if (xNode.left!=null){ //有左孩子 找到该节点左子树的最大节点值
return maxNode(xNode.left).key;
}
BSTNode<K,V> fNode =xNode.parent;
// 做斜线找到第一个左拐角
while (fNode!=null &&fNode.left==xNode){
xNode=fNode;
fNode=fNode.parent;
}
return fNode==null?null:fNode.key;
}
原文：https://www.cnblogs.com/Dr-d/p/12487583.html