python

超轻量级php框架startmvc

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

更新时间:2020-06-17 00:06:01 作者:startmvc
本文实例讲述了Python二叉树的遍历操作。分享给大家供大家参考,具体如下:#coding:utf-8"""@e

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


# coding:utf-8
"""
@ encoding: utf-8
@ author: lixiang
@ email: lixiang_cn@foxmail.com
@ 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+1
5 度是二叉树分支树,对于二叉树而言有0,1,2三种取值
不管是前中后序遍历,都是在当前规则下,无路可走时,输出根结点。
"""
class TreeNode(object):
 def __init__(self, x, left=None, right=None):
 self.val = x
 self.left = left
 self.right = right
def 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) + 1
if __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 二叉树 遍历 前序遍历 中序遍历 后序遍历 层序遍历