LRH1993/android_interview

树的前驱和后继中,代码是否有误

Closed this issue · 2 comments

// 如果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的左孩子
也就是符合第二点 ,但是好像没有判断该父节点是否具有右孩子。

满足(y!=null) && (x==y.left),再往上追溯,所以其实在寻找右孩子。再仔细看下。

看懂了,感谢