Python树的前序、中序、后序遍历

#Python树的前序、中序、后序遍历

树的基础遍历分为三种：前序遍历、中序遍历、后序遍历

前序遍历：根节点->左子树->右子树
中序遍历：左子树->根节点->右子树
后序遍历：左子树->右子树->根节点

首先自定义树模型

class Node(object):def __init__(self,val,left=None,right=None):self.val = valself.left = leftself.right = rightnode = Node("A",Node("B",Node("D"),Node("E")),Node("C",Node("F"),Node("G")))

代码中为了更直观地观察遍历顺序，采用直接打印node.val的方式输出遍历结果
代码实现：

# 前序遍历
def PreTraverse(root):if root == None:returnprint(root.val,end=" ")PreTraverse(root.left)PreTraverse(root.right)# 中序遍历
def MidTraverse(root):if root == None:returnMidTraverse(root.left)print(root.val,end=" ")MidTraverse(root.right)# 后序遍历
def AfterTraverse(root):if root == None:returnAfterTraverse(root.left)AfterTraverse(root.right)print(root.val,end=" ")print("前序遍历",end="")
PreTraverse(node)
print("")
print("中序遍历",end="")
MidTraverse(node)
print("")
print("后序遍历",end="")
AfterTraverse(node)

输出结果：

前序遍历 A B D E C F G 
中序遍历 D B E A F C G 
后序遍历 D E B F G C A 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！