二叉树

概念

二叉树是一种非常重要的数据结构，非常多其他数据结构都是基于二叉树的基础演变而来的。对于二叉树，有深度遍历和广度遍历，深度遍历有前序、中序以及后序三种遍历方法，广度遍历即我们寻常所说的层次遍历。由于树的定义本身就是递归定义，因此採用递归的方法去实现树的三种遍历不仅easy理解并且代码非常简洁，而对于广度遍历来说，须要其他数据结构的支撑。比方堆了。所以。对于一段代码来说，可读性有时候要比代码本身的效率要重要的多。

把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
(01) 每个节点有零个或多个子节点；
(02) 没有父节点的节点称为根节点；
(03) 每一个非根节点有且只有一个父节点；
(04) 除了根节点外，每个子节点可以分为多个不相交的子树。

四种基本的遍历思想

前序遍历：根结点 —> 左子树 —> 右子树
中序遍历：左子树—> 根结点 —> 右子树
后序遍历：左子树 —> 右子树 —> 根结点
层次遍历：仅仅需按层次遍历就可以
比如。求以下二叉树的各种遍历

前序遍历：1 2 4 5 7 8 3 6
中序遍历：4 2 7 5 8 1 3 6
后序遍历：4 7 8 5 2 6 3 1
层次遍历：1 2 3 4 5 6 7 8

树的基本术语

若一个结点有子树，那么该结点称为子树根的"双亲"，子树的根是该结点的"孩子"。有相同双亲的结点互为"兄弟"。一个结点的所有子树上的任何结点都是该结点的后裔。从根结点到某个结点的路径上的所有结点都是该结点的祖先。

结点的度：结点拥有的子树的数目。
叶子：度为零的结点。
分支结点：度不为零的结点。
树的度：树中结点的最大的度。

层次：根结点的层次为1，其余结点的层次等于该结点的双亲结点的层次加1。树的高度：树中结点的最大层次。
无序树：如果树中结点的各子树之间的次序是不重要的，可以交换位置。有序树：如果树中结点的各子树之间的次序是重要的, 不可以交换位置。森林：0个或多个不相交的树组成。对森林加上一个根，森林即成为树；删去根，树即成为森林。

二叉树的五种基本形态：

二叉树的性质

二叉树有以下几个性质：TODO(上标和下标)
性质1：二叉树第i层上的结点数目最多为 2{i-1} (i≥1)。
性质2：深度为k的二叉树至多有2{k}-1个结点(k≥1)。
性质3：包含n个结点的二叉树的高度至少为log2 (n+1)。
性质4：在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1。

二叉树实现

from graphviz import Digraph
import uuid
from random import sample

# 二叉树类
class BTree(object):

    # 初始化
	def __init__(self, data=None, left=None, right=None):
		self.data = data    # 数据域
        	self.left = left    # 左子树
        	self.right = right  # 右子树
        	self.dot = Digraph(comment='Binary Tree'）
    
    # 前序遍历	
	def preorder(self):
		if self.data is not None:
			print(self.data,end=' ')
		if self.left is not None:
			print(self.left,end=' ')
        	if self.right is not None:
            self.right.preorder()
    
   	# 中序遍历
   	def inorder(self):
   		if self.left is not None:
   			print(self.left,end=' ')
   		if self.data is not None:
   			print(self.data,end=' ')
   		if self.right is not None:
            	self.right.inorder()
    	# 后序遍历
    	def postorder(self):
       	if self.left is not None:
            	self.left.postorder()
       	if self.right is not None:
            	self.right.postorder()
        	if self.data is not None:
            	print(self.data, end=' ')      
     
     # 层序遍历
   	def levelorder(self):
        	# 返回某个节点的左子树
        	def LChild_Of_Node(node):
            	return node.left if node.left is not None else None
        	# 返回某个节点的右子树
        	def RChild_Of_Node(node):
            	return node.right if node.right is not None else None
     
		# 层序遍历列表
		level_order = []
		# 是否添加根节点的数据
		if self.data is not None:
			level_order.append([self])
		
		#二叉树的高度
		height = self.height()
		if height >= 1:
			# 对第二层及其以后的层数进行操作, 在level_order中添加节点而不是数据
	     	for _ in range(2, height + 1):
              		level = []  # 该层的节点
              		for node in level_order[-1]:
                   		# 如果左孩子非空，则添加左孩子
              			if LChild_Of_Node(node):
                    		level.append(LChild_Of_Node(node))
                   		# 如果右孩子非空，则添加右孩子
                   		if RChild_Of_Node(node):
                        level.append(RChild_Of_Node(node))
              		# 如果该层非空，则添加该层
              		if level:
                   		level_order.append(level)
               	for i in range(0, height):  # 层数
               		for index in range(len(level_order[i])):
               			level_order[i][index] = level_order[i][index].data
               			
		return level_order
                
	#二叉树高度
	def height(self):
     	# 空的树高度为0, 只有root节点的树高度为1
		if self.data is None:
			return 0
		elif self.left is None and self.right is None:
			return 1
		# 根节点下只有一个分支
		elif self.left is None and self.right is not None:
			return 1+self.right.height()
		elif self.right is None and self.left is not None:
			return 1+self.left.height()
		else:
			return 1+max(self.left.height(),self.right.height())
	
	# 二叉树的叶子节点
    	def leaves(self):

	if self.data is None:
		return None
	elif self.left is None and self.right is None:
        	print(self.data, end=' ')
    	elif self.left is None and self.right is not None:
		self.right.leaves()
  	elif self.right is None and self.left is not None:
		self.left.leaves()
	else:
		self.left.leaves()
		self.right.leaves() 
		
	#二叉树可视化
	def print_tree(self, save_path='./Binary_Tree.gv', label=False):
     #略
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

上述实现的功能：
1.初始化方法：该树存放的数据为data,左子树，右子树为left和right，默认均为None;
2.preorder()方法：递归实现二叉树的先序遍历；
3.inorder()方法：递归实现二叉树的中序遍历；
4.postorder()方法：递归实现二叉树的后序遍历；
5.levelorder()方法：递归实现二叉树的层序遍历；
6.height()方法：计算二叉树的高度；
7.leaves()方法：计算二叉树的叶子结点；

实例二叉树

若我们需要实现图3的示例二叉树，完整的Python代码如下：

from Binary_Tree import BTree

# 构造二叉树, BOTTOM-UP METHOD
right_tree = BTree(6)
right_tree.left = BTree(2)
right_tree.right = BTree(4)

left_tree = BTree(5)
left_tree.left = BTree(1)
left_tree.right = BTree(3)

tree = BTree(11)
tree.left = left_tree
tree.right = right_tree

left_tree = BTree(7)
left_tree.left = BTree(3)
left_tree.right = BTree(4)

right_tree = tree # 增加新的变量
tree = BTree(18)
tree.left = left_tree
tree.right = right_tree

print('先序遍历为:')
tree.preorder()
print()

print('中序遍历为:')
tree.inorder()
print()

print('后序遍历为:')
tree.postorder()
print()

print('层序遍历为:')
level_order = tree.levelorder()
print(level_order)
print()

height = tree.height()
print('树的高度为%s.' % height)

print('叶子节点为：')
tree.leaves()
print()

# 利用Graphviz进行二叉树的可视化
tree.print_tree(save_path='E://BTree.gv', label=True)
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

输出结果如下

先序遍历为:
18 7 3 4 11 5 1 3 6 2 4 
中序遍历为:
3 7 4 18 1 5 3 11 2 6 4 
后序遍历为:
3 4 7 1 3 5 2 4 6 11 18 
层序遍历为:
[[18], [7, 11], [3, 4, 5, 6], [1, 3, 2, 4]]

树的高度为4.
叶子节点为：
3 4 1 3 2 4 
1
2
3
4
5
6
7
8
9
10
11

可视结果

总结
二叉树是很多重要算法及模型的基础，比如二叉搜索树（BST），哈夫曼树(Huffman Tree)，CART决策树等。
在Python中，已有别人实现好的二叉树的模块，它是binarytree模块，其官方文档的网址为：https://pypi.org/project/binarytree/。其使用的例子如下：