树的概念
树（英语：tree）是一种抽象数据类型（ADT）或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点： 1. 每个节点有 零个或多个子节点；2. 没有父节点的节点称为根节点；3.每一个非根节点有且只有一个父节点；4.除了根节点外，每个子节点可以分为多个不相交的子树；
二叉树
每个节点最多含有两个子树的树称为二叉树，下面直接上代码：
|
01
02
03
04
05
06
07
08
09
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
93
94
95
96
97
98
|
class Node(object): """节点类""" def __init__(self, item): self.item = item self.lChild = None self.rChild = Noneclass Tree(object): """二叉树""" def __init__(self): #记录根节点 self.root = None def add(self, item): # 添加节点 # 完全二叉树，从上到下，从左往右 node = Node(item) if self.root is None: self.root = node else: # 从上到下，从左往右 使用队列 queue = [] queue.append(self.root) while queue: child = queue.pop(0) if child.lChild is None: child.lChild = node return if child.rChild is None: child.rChild = node return queue.append(child.lChild) queue.append(child.rChild) # 广度优先遍历，层次遍历 def breath_travel(self): if self.root is None: return queue = [] queue.append(self.root) while queue: node = queue.pop(0) print(node.item, end=" ") if node.lChild is not None: queue.append(node.lChild) if node.rChild is not None: queue.append(node.rChild) # 深度优先遍历 def depth_travel(self): self.post_order(self.root) print() # 先序 自己 左子树 右子树 def pre_order(self, node): if node is None: return print(node.item, end=" ") self.pre_order(node.lChild) self.pre_order(node.rChild) # 中序 左子树 自己 右子树 def in_order(self, node): if node is None: return self.in_order(node.lChild) print(node.item, end=" ") self.in_order(node.rChild) # 后序 左子树 右子树 自己 def post_order(self, node): if node is None: return self.post_order(node.lChild) self.post_order(node.rChild) print(node.item, end=" ")if __name__ == ‘__main__‘: tree = Tree() tree.add(0) tree.add(1) tree.add(2) tree.add(3) tree.add(4) tree.add(5) tree.add(6) tree.add(7) tree.add(8) tree.add(9) # tree.breath_travel() tree.depth_travel()
|
原文：https://www.cnblogs.com/heimaguangzhou/p/11590734.html