中序遍历找下一个结点
本帖最后由 Lthero 于 2021-4-25 15:56 编辑中序遍历找下一个结点
分为三个情况：
1、当前结点的下一结点是右子树的最左结点
循环找右子结点的左结点，直到某个结点无左子结点
当前结点“11“的右结点是”14“，14有左子结点13；13有左子结点12；12无左子结点；
12就是要找的下一个结点
2、当前结点无右子树，并且当前结点是其父结点的左结点，其父结点就是下一个结点
当前结点“9“的是父结点10的左子结点
10就是要找的下一个结点
3、当前结点无右子树，但当前结点是其父结点的右结点
一直向上找，直到满足”当前结点是其父结点的左结点“
当前结点“15“的父结点是14，14是其父结点11的右子结点；
当前结点”14“的父结点是11，11是其父结点17的左子结点；
17就是要找的下一个结点
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
页:
[1]