树的前驱和后继中,代码是否有误
Closed this issue · 2 comments
YQYOnTheRoad commented
// 如果x没有左孩子。则x有以下两种可能:
// (01) x是"一个右孩子",则"x的前驱结点"为 "它的父结点"。
// (02) x是"一个左孩子",则查找"x的最低的父结点,并且该父结点要具有右孩子",找到的这个"最低的父结点"就是"x的前驱结点"。
BSTNode y = x.parent;
while ((y!=null) && (x==y.left)) {
x = y;
y = y.parent;
}
上面提到“x的最低的父结点,并且该父结点要具有右孩子”
while ((y!=null) && (x==y.left)) { // y是x的父节点, x是y的左孩子
也就是符合第二点 ,但是好像没有判断该父节点是否具有右孩子。
LRH1993 commented
满足(y!=null) && (x==y.left),再往上追溯,所以其实在寻找右孩子。再仔细看下。
YQYOnTheRoad commented
看懂了,感谢