就在我坐下来为 morris 中序遍历编写代码之前,我尝试了这个示例,但对于它在这种特殊情况下的工作方式有点困惑:
80
/ \
60 100
\ /
70 90
/
65
/
63
\
64
步骤1:
60
\
70
/ \
65 80
/ \
63 100
\ /
64 90
据我了解,下一步70的算法将成为65的右孩子,那么60会发生什么?我很确定我错过了一些微不足道的东西,但不幸的是无法将其放在首位。
public void MorrisInorder() {
BSTNode<T> p = root, tmp;
while (p != null)
if (p.left == null) {
visit(p);
p = p.right;
}
else {
tmp = p.left;
while (tmp.right != null && // go to the rightmost node of
tmp.right != p) // the left subtree or
tmp = tmp.right; // to the temporary parent of p;
if (tmp.right == null) {// if 'true' rightmost node was
tmp.right = p; // reached, make it a temporary
p = p.left; // parent of the current root,
}
else { // else a temporary parent has been
visit(p); // found; visit node p and then cut
tmp.right = null; // the right pointer of the current
p = p.right; // parent, whereby it ceases to be
} // a parent;
}
}
我正在遵循 morris 中序遍历的代码。