二叉树节点的前驱后继

二叉树的特殊节点

为方便后序讨论，这里继续定义如下的二叉树特殊节点，并给出寻找这些节点的步骤：

1) \(mostLeft(n)\)：其递归定义为“若\(n.left\)非空则返回\(mostLeft(n.left)\)，否则返回\(n\)”。等价于迭代步骤“每轮迭代若\(n.left\)非空则置\(n=n.left\)并继续迭代，否则退出迭代返回\(n\)”。直观上是以\(n\)为树根的子树的最左节点；

2) \(mostRight(n)\)：其递归定义为“若\(n.right\)非空则返回\(mostRight(n.right)\)，否则返回\(n\)”。等价于迭代步骤“每轮迭代若\(n.right\)非空则置\(n=n.right\)并继续迭代，否则退出迭代返回\(n\)”。直观上是以\(n\)为树根的子树的最右节点；

3) \(mostLeftLeaf(n)\)：其递归定义为“若\(n.left\)非空则返回\(mostLeftLeaf(n.left)\)，否则若\(n.right\)非空则返回\(mostLeftLeaf(n.right)\)，否则返回\(n\)”。等价于迭代步骤“每轮迭代若\(n.left\)非空则置\(n=n.left\)并继续迭代，否则若\(n.right\)非空则置\(n=n.right\)并继续迭代，否则退出迭代返回\(n\)”。直观上是以\(n\)为树根的子树的最左叶子节点；

4) \(mostRightLeaf(n)\)：其递归定义为“若\(n.right\)非空则返回\(mostRightLeaf(n.right)\)，否则若\(n.left\)非空则返回\(mostRightLeaf(n.left)\)，否则返回\(n\)”。等价于迭代步骤“每轮迭代若\(n.right\)非空则置\(n=n.right\)并继续迭代，否则若\(n.left\)非空则置\(n=n.left\)并继续迭代，否则退出迭代返回\(n\)”。直观上是以\(n\)为树根的子树的最右叶子节点；

上述四种节点除了有直观的位置特征外，还与前/中/后序遍历有如下的关系：

1) \(mostLeft(n)\)：\(n\)为树根的子树的中序序列首节点。容易用反证法验证；

2) \(mostRight(n)\)：\(n\)为树根的子树的中序序列末节点。容易用反证法验证；

3) \(mostLeftLeaf(n)\)：\(n\)为树根的子树的后序序列首节点。容易用反证法验证；

4) \(mostRightLeaf(n)\)：\(n\)为树根的子树的前序序列末节点。容易用反证法验证；

下面是寻找上述4种节点的程序实现，代价都以二叉树深度\(O(h)\)为上界，最坏时\(O(h)\)等于二叉树节点数\(O(n)\)。

# 最左节点
def mostLeft(root):
    while root.left:
        root = root.left
    return root

# 最右节点
def mostRight(root):
    while root.right:
        root = root.right
    return root

# 最左叶子节点
def mostLeftLeaf(root):
    while root.right or root.left:
        root = root.left if root.left else root.right
    return root

# 最右叶子节点
def mostRightLeaf(root):
    while root.right or root.left:
        root = root.right if root.right else root.left
    return root

# 最左节点

def mostLeft(root):

while root.left:

root = root.left

return root

# 最右节点

def mostRight(root):

while root.right:

root = root.right

return root

# 最左叶子节点

def mostLeftLeaf(root):

while root.right or root.left:

root = root.left if root.left else root.right

return root

# 最右叶子节点

def mostRightLeaf(root):

while root.right or root.left:

root = root.right if root.right else root.left

return root

二叉树节点的前驱后继

二叉树本身不像线性表有前驱后继关系，因为其节点可以有0~2个孩子，不好定义节点的前驱后继，但为了方便人们依然利用二叉树的遍历序列(线性表)定义了节点的前驱后继。比如在某二叉树中序序列中，节点\(A\)是\(B\)的前驱(predecessor)，那么\(B\)是\(A\)的后继(successor)，这时就称\(A\)是\(B\)的中序前驱，\(B\)是\(A\)的中序后继，相应有前序后继、后序前驱等。

下面讨论寻找二叉树任意节点在前/中/后序序列的前驱后继的算法，显然节点的前/中/后序前驱后继不一定在该节点的左右子树中，这就需要回溯该节点的祖先才能找到前驱后继，为方便处理这种情况，让二叉树节点都额外存储1个指向其父亲的\(parent\)指针，那么二叉树节点的\(parent\)为空当且仅当该节点为树根。需注意后面在分析额外空间时，由于\(parent\)指针是这种二叉树节点本身的一部分，所以不认为\(parent\)指针占用了额外空间，虽然其确实比普通二叉树多占用\(O(n)\)的空间。下面定义前驱后继相关的运算如下，之后会给出前/中/后序遍历这3种意义下的运算的具体实现：

1) \(getFirst(n)\)：寻找树根为\(n\)的子树的遍历序列首节点；

2) \(getLast(n)\)：寻找树根为\(n\)的子树的遍历序列末节点；

3) \(getSuccessor(n)\)：寻找节点\(n\)在整个二叉树的遍历序列后继；

4) \(getPredecessor(n)\)：寻找节点\(n\)在整个二叉树的遍历序列前驱；

上述带\(parent\)指针的二叉树节点的Python程序类如下所示。

class Node:
    def __init__(self):
        self.parent = None
        self.left = None
        self.right = None

class Node:

def __init__(self):

self.parent = None

self.left = None

self.right = None

中序前驱后继

给出中序遍历意义下上述运算的实现：

1) \(getFirst(n)\)：返回\(mostLeft(n)\)；

2) \(getLast(n)\)：返回\(mostRight(n)\)；

3) \(getSuccessor(n)\)：若\(n.right\)非空则返回\(getFirst(n.right)\)。否则开始迭代，每轮迭代中“若\(n.parent\)为空则退出迭代返回空，否则若\(n.parent.left=n\)则退出迭代返回\(n.parent\)，否则置\(n=n.parent\)并继续迭代”；

4) \(getPredecessor(n)\)：若\(n.left\)非空则返回\(getLast(n.left)\)。否则开始迭代，每轮迭代中“若\(n.parent\)为空则退出迭代返回空，否则若\(n.parent.right=n\)则退出迭代返回\(n.parent\)，否则置\(n=n.parent\)并继续迭代”；

分析\(getSuccessor\)中迭代的意义，计迭代开始时的\(n\)为\(x\)，迭代退出返回的节点为\(p\)(也是\(x\)的中序后继)，那么\(p\)是\(x\)所有祖先中距离\(x\)最近的满足\(x\)位于\(p\)左子树的节点，\(p\)为空说明\(x\)没有这样的祖先，也就没无中序后继。\(getPredecessor\)与之同理，可发现中序序列末节点和首节点对称，中序前驱和后继对称。下面是程序实现，代价都以子树深度为上界。

#找root树的中序序列首节点
def getFirst(root):
    while root.left:
        root = root.left
    return root

#找root树的中序序列末节点
def getLast(root):
    while root.right:
        root = root.right
    return root

#找node的中序后继
def getSuccessor(node):
    if node.right:
        return getFirst(node.right)
    while node.parent:
        if node.parent.left is node:
            return node.parent
        node = node.parent
    return None

#找node的中序前驱
def getPredecessor(node):
    if node.left:
        return getLast(node.left)
    while node.parent:
        if node.parent.right is node:
            return node.parent
        node = node.parent
    return None

#找root树的中序序列首节点

def getFirst(root):

while root.left:

root = root.left

return root

#找root树的中序序列末节点

def getLast(root):

while root.right:

root = root.right

return root

#找node的中序后继

def getSuccessor(node):

if node.right:

return getFirst(node.right)

while node.parent:

if node.parent.left is node:

return node.parent

node = node.parent

return None

#找node的中序前驱

def getPredecessor(node):

if node.left:

return getLast(node.left)

while node.parent:

if node.parent.right is node:

return node.parent

node = node.parent

return None

前序前驱后继

给出前序遍历意义下上述运算的实现：

1) \(getFirst(n)\)：返回\(n\)；

2) \(getLast(n)\)：返回\(mostRightLeaf(n)\)；

3) \(getSuccessor(n)\)：若\(n.left\)非空则返回\(n.left\)。否则若\(n.right\)非空则返回\(n.right\)。否则开始迭代，每轮迭代中“若\(n.parent\)为空则退出迭代返回空，否则若\(n.parent.left=n\)且\(n.parent.right\)非空则退出迭代返回\(n.parent.right\)，否则置\(n=n.parent\)并继续迭代”；

4) \(getPredecessor(n)\)：若\(n.parent\)为空则返回空。否则若\(n.parent.left=n\)则返回\(n.parent\)。否则若\(n.parent.left\)为空则返回\(n.parent\)。否则返回\(getLast(n.parent.left)\)；

分析\(getSuccessor\)中迭代的意义，计迭代开始时的\(n\)为\(x\)，迭代退出返回的节点为\(y\)(也是\(x\)的前序后继)。设\(p\)是\(x\)所有祖先中距离\(x\)最近的满足\(x\)位于\(p\)左子树且\(p.right\)非空的节点，若这样的\(p\)存在则\(y=p.right\)，\(y\)为空则\(x\)无前序后继。对比后文可发现，前序序列首节点和后序序列末节点对称，前序后继和后序前驱对称。下面是程序实现，代价都以子树深度为上界。

#找root树的前序序列首节点
def getFirst(root):
    return root

#找root树的前序序列末节点
def getLast(root):
    while root.right or root.left:
        root = root.right if root.right else root.left
    return root

#找node的前序后继
def getSuccessor(node):
    if node.left:
        return node.left
    if node.right:
        return node.right
    while node.parent:
        if node.parent.left is node and node.parent.right:
            return node.parent.right
        node = node.parent
    return None

#找node的前序前驱
def getPredecessor(node):
    if not node.parent:
        return None
    elif node.parent.left is node:
        return node.parent
    elif not node.parent.left:
        return node.parent
    return getLast(node.parent.left)

#找root树的前序序列首节点

def getFirst(root):

return root

#找root树的前序序列末节点

def getLast(root):

while root.right or root.left:

root = root.right if root.right else root.left

return root

#找node的前序后继

def getSuccessor(node):

if node.left:

return node.left

if node.right:

return node.right

while node.parent:

if node.parent.left is node and node.parent.right:

return node.parent.right

node = node.parent

return None

#找node的前序前驱

def getPredecessor(node):

if not node.parent:

return None

elif node.parent.left is node:

return node.parent

elif not node.parent.left:

return node.parent

return getLast(node.parent.left)

后序前驱后继

给出后序遍历意义下上述运算的实现：

1) \(getFirst(n)\)：返回\(mostLeftLeaf(n)\)；

2) \(getLast(n)\)：返回\(n\)；

3) \(getSuccessor(n)\)：若\(n.parent\)为空则返回空。否则若\(n.parent.right=n\)则返回\(n.parent\)。否则若\(n.parent.right\)为空则返回\(n.parent\)。否则返回\(getFirst(n.parent.right)\)；

4) \(getPredecessor(n)\)：若\(n.right\)非空则返回\(n.right\)。否则若\(n.left\)非空则返回\(n.left\)。否则开始迭代，每轮迭代中“若\(n.parent\)为空则退出迭代返回空，否则若\(n.parent.right=n\)且\(n.parent.left\)非空则退出迭代返回\(n.parent.left\)，否则置\(n=n.parent\)并继续迭代”；

上述\(getPredecessor\)的迭代步骤的意义和求前序后继的\(getSuccessor(n)\)的意义类似，这里不展开讨论，对比前文可发现，后序序列首节点和前序序列末节点对称，后序后继和前序前驱对称。下面是程序实现，代价都以子树深度为上界。

#找root树的后序序列首节点
def getFirst(root):
    while root.left or root.right:
        root = root.left if root.left else root.right
    return root

#找root树的后序序列末节点
def getLast(root):
    return root

#找node的后序后继
def getSuccessor(node):
    if not node.parent:
        return None
    elif node.parent.right is node:
        return node.parent
    elif not node.parent.right:
        return node.parent
    return getFirst(node.parent.right)

#找node的后序前驱
def getPredecessor(node):
    if node.right:
        return node.right
    if node.left:
        return node.left
    while node.parent:
        if node.parent.right is node and node.parent.left:
            return node.parent.left
        node = node.parent
    return None

#找root树的后序序列首节点

def getFirst(root):

while root.left or root.right:

root = root.left if root.left else root.right

return root

#找root树的后序序列末节点

def getLast(root):

return root

#找node的后序后继

def getSuccessor(node):

if not node.parent:

return None

elif node.parent.right is node:

return node.parent

elif not node.parent.right:

return node.parent

return getFirst(node.parent.right)

#找node的后序前驱

def getPredecessor(node):

if node.right:

return node.right

if node.left:

return node.left

while node.parent:

if node.parent.right is node and node.parent.left:

return node.parent.left

node = node.parent

return None

利用前驱后继实现二叉树遍历

利用上述算法可立即构造出迭代的前/中/后序遍历算法，且3种遍历结构相同，可按相同步骤实现：

1) \(traverse\)：遍历二叉树。步骤是若树根\(root\)为空则直接返回，否则执行\(head=getFirst(root)\)，然后“访问”\(head\)，然后开始迭代，每轮迭代执行\(head=getSuccessor(head)\)，执行完后若\(head\)非空则“访问”\(head\)，否则返回；

2) \(reverseTraverse\)：逆序遍历二叉树。步骤是若树根\(root\)为空则直接返回，否则执行\(tail=getLast(root)\)，然后“访问”\(tail\)，然后开始迭代，每轮迭代执行\(tail=getPredecessor(tail)\)，执行完后若\(tail\)非空则“访问”\(tail\)，否则返回；

上述前/中/后序遍历由多个函数组成，整体上是嵌套循环结构，其中\(traverse\)是外层循环，外层循环轮数是遍历的“访问”次数，但由于存在内存循环，所以不好直接确定算法整体代价，若直接用\(getFirst,getSuccessor\)等函数的代价上界\(O(h)\)来计算整体代价，会得到不够准确的上界，所以下面用其他方式来计算3种遍历的精确代价上界：

1) 中序遍历：只分析正序遍历，逆序遍历与之对称。先把代价分2部分，第1部分是“所有\(getFirst\)调用的总代价”，第2部分是“所有\(getSuccessor\)调用的总代价减第1部分”。遍历每次调用\(getFirst(x)\)都途径\(x\),\(x.left\),\(x.left.left\),\(x.left.left.left\)……并返回最后一个。所以任意的2次\(getFirst\)调用都必然不途径同个节点，否则这2次调用会返回同个节点，由于返回的节点是某轮遍历“访问”的节点，所以会导致错误，引发矛盾，所以所有\(getFirst\)调用共至多途径\(n\)个节点，所以第1部分的代价有上界\(O(n)\)。第2部分代价是所有\(getSuccessor(n)\)调用中除\(getFirst\)以外的代价，其同阶于“置\(x=x.parent\)的总次数”，对于任意的2次\(getSuccessor\)调用，都不会有同个节点\(y\)在2次调用中都执行了“置\(y=y.parent\)”，否则这2次调用一定返回同个节点或都返回空，返回的结果要么作为某次遍历“访问”的节点，要么用来停止遍历，会导致遍历流程错误，出现矛盾。所以所有“置\(x=x.parent\)”至多在\(n\)个不同节点上执行\(n\)次，第2部分代价也有上界\(O(n)\)。故总代价有上界\(O(n)\)；

2) 前序遍历：只分析正序遍历，因为逆序遍历和后序正序遍历对称。观察可知其总代价即中序遍历的“第2部分代价”，同样由于“置\(x=x.parent\)的总次数”不能超过总节点数\(O(n)\)，故代价上界是\(O(n)\)；

3) 后序遍历：只分析正序遍历，因为逆序遍历和前序正序遍历对称。观察可知其总代价即中序遍历的“第1部分代价”，同样由于“所有\(getFirst\)途径的节点数”不能超过总节点数\(O(n)\)，故代价上界是\(O(n)\)；

下面是遍历和逆序遍历的程序实现，只要按上述3种方式实现其用到的函数，就能得到前/中/后序遍历的迭代算法。

# 正序遍历
def traverse(root):
    if not root:
        return
    head = getFirst(root)
    while head:
        print(head) # 遍历位置
        head = getSuccessor(head)
    
# 逆序遍历
def reverseTraverse(root):
    if not root:
        return
    tail = getLast(root)
    while tail:
        print(tail) # 遍历位置
        tail = getPredecessor(tail)

# 正序遍历

def traverse(root):

if not root:

return

head = getFirst(root)

while head:

print(head) # 遍历位置

head = getSuccessor(head)

# 逆序遍历

def reverseTraverse(root):

if not root:

return

tail = getLast(root)

while tail:

print(tail) # 遍历位置

tail = getPredecessor(tail)

发表评论 取消回复

发表评论取消回复