Python二叉树的遍历操作示例【前序遍历,中序遍历,后序遍历,层序遍历】

Python  /  管理员 发布于 7年前   195

本文实例讲述了Python二叉树的遍历操作。分享给大家供大家参考，具体如下：

# coding:utf-8"""@ encoding: utf-8@ author: lixiang@ email: [email protected]@ python_version: 2@ time: 2018/4/11 0:09@ more_info:二叉树是有限个元素的集合，该集合或者为空、或者有一个称为根节点（root）的元素及两个互不相交的、分别被称为左子树和右子树的二叉树组成。1 二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。2 二叉树的第i层至多有2^{i-1}个结点3 深度为k的二叉树至多有2^k-1个结点；4 对任何一棵二叉树T，如果其终端结点数为N0，度为2的结点数为N2，则N0=N2+15 度是二叉树分支树，对于二叉树而言有0，1，2三种取值不管是前中后序遍历，都是在当前规则下，无路可走时，输出根结点。"""class TreeNode(object):  def __init__(self, x, left=None, right=None):    self.val = x    self.left = left    self.right = rightdef pre_traverse(root):  """  根左右  :param root:  :return:  """  if not root:    return  print root.val,  pre_traverse(root.left)  pre_traverse(root.right)def mid_travese(root):  """  左根右  :param root:  :return:  """  if not root:    return  mid_travese(root.left)  print root.val,  mid_travese(root.right)def after_travese(root):  """  左右根  :param root:  :return:  """  if not root:    return  after_travese(root.left)  after_travese(root.right)  print root.val,def level_travese(root):  if not root:    return  queue = []  queue.append(root)  while queue:    cur = queue.pop(0)    print cur.val,    if cur.left:      queue.append(cur.left)    if cur.right:      queue.append(cur.right)def depth(root):  if not root:    return 0  left = depth(root.left)  right = depth(root.right)  return max(left, right) + 1if __name__ == '__main__':  """  tree是一个表示树根节点的对象  前序遍历 1 2 4 5 8 9 11 3 6 7 10  中序遍历 4 2 8 5 11 9 1 6 3 10 7  后序遍历 4 8 11 9 5 2 6 10 7 3 1  层序遍历 1 2 3 4 5 6 7 8 9 10 11  深度 5  """  tree = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5, TreeNode(8), TreeNode(9, left=TreeNode(11)))), TreeNode(3, TreeNode(6), TreeNode(7, left=TreeNode(10))))  print("\n前序遍历")  pre_traverse(tree)  print("\n中序遍历")  mid_travese(tree)  print("\n后序遍历")  after_travese(tree)  print("\n层序遍历")  level_travese(tree)  print("\n深度")  print(depth(tree))

运行结果：

前序遍历
1 2 4 5 8 9 11 3 6 7 10
中序遍历
4 2 8 5 11 9 1 6 3 10 7
后序遍历
4 8 11 9 5 2 6 10 7 3 1
层序遍历
1 2 3 4 5 6 7 8 9 10 11
深度
5

更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》

希望本文所述对大家Python程序设计有所帮助。