二叉树的特殊节点
为方便后序讨论,这里继续定义如下的二叉树特殊节点,并给出寻找这些节点的步骤:
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)\)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | # 最左节点 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程序类如下所示。
1 2 3 4 5 | 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\)与之同理,可发现中序序列末节点和首节点对称,中序前驱和后继对称。下面是程序实现,代价都以子树深度为上界。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | #找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\)无前序后继。对比后文可发现,前序序列首节点和后序序列末节点对称,前序后继和后序前驱对称。下面是程序实现,代价都以子树深度为上界。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | #找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)\)的意义类似,这里不展开讨论,对比前文可发现,后序序列首节点和前序序列末节点对称,后序后继和前序前驱对称。下面是程序实现,代价都以子树深度为上界。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | #找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种方式实现其用到的函数,就能得到前/中/后序遍历的迭代算法。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | # 正序遍历 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) |