本文实例讲述了Python二叉树的遍历操作。分享给大家供大家参考，具体如下：
|
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
|
# 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+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程序设计有所帮助。
原文链接：https://blog.csdn.net/vitaminc4/article/details/80964955
