中序遍历找下一个结点

Lthero

中序遍历找下一个结点




分为三个情况：

1、当前结点的下一结点是右子树的最左结点

循环找右子结点的左结点，直到某个结点无左子结点

当前结点“11“的右结点是”14“，14有左子结点13；13有左子结点12；12无左子结点；

12就是要找的下一个结点

2、当前结点无右子树，并且当前结点是其父结点的左结点，其父结点就是下一个结点

当前结点“9“的是父结点10的左子结点

10就是要找的下一个结点

3、当前结点无右子树，但当前结点是其父结点的右结点

一直向上找，直到满足”当前结点是其父结点的左结点“

当前结点“15“的父结点是14，14是其父结点11的右子结点；

当前结点”14“的父结点是11，11是其父结点17的左子结点；

17就是要找的下一个结点

[Python] 纯文本查看 复制代码

class node():
    def __init__(self, value=0, left=None, right=None, pre=None):
        self.value = value
        self.left = left
        self.right = right
        self.pre = pre

def find_next(the_node):
    if the_node is None:
        return
    if the_node.right is not None:
        p = the_node.right
        while p.left is not None:
            p=p.left
        return p
    elif the_node.pre is not None:
        current=the_node
        parent = the_node.pre
        while parent is not None and current.value== parent.right:
            current=parent
            parent=parent.pre
        return parent