1、二叉树的基本介绍
定义：二叉树是 n 个结点的有限集合，该集合为空集，或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。下图是一个简单的二叉树：
二叉树.png
2、二叉树的Python实现
本文使用结点和引用的方式实现树。在这种情况下，我们将定义具有根结点，以及左子树和右子树属性的类。以下代码构建了 结点 和 二叉树 两个类，并采用引用的方式实现了上文图中所示的二叉树（可以编写二叉树的创建函数去实现树），具体代码如下：
'''定义树节点'''
'''二叉树节点类'''
class Node():
def __init__(self, item):
self.item = item
self.left = None
self.right = None
def getName(self):
return self.item
'''二叉树类'''
class Tree():
def __init__(self, root):
self.root = root
n0 = Node(0)
n1 = Node(1)
n2 = Node(2)
n0.left = n1
n0.right = n2
n3 = Node(3)
n4 = Node(4)
n1.left = n3
n1.right = n4
n5 = Node(5)
n6 = Node(6)
n2.left = n5
n2.right = n6
n7 = Node(7)
n3.right = n7
3、二叉树的遍历
二叉树常见的遍历方式有前序遍历、中序遍历和后序遍历。
前序遍历：在前序遍历中，我们先访问根节点，然后递归地前序遍历访问左子树，再递归地前序遍历访问右子树。
中序遍历：在中序遍历中，我们递归地中序遍历访问左子树，然后访问根节点，最后再递归地中序遍历访问右子树。
后序遍历：在后序遍历中，我们先递归地后序遍历访问左子树和右子树，最后访问根节点。
三种遍历的遍历顺序如下图所示：
二叉树遍历.png
前序遍历访问结点次序：0-1-3-7-4-2-5-6
中序遍历访问结点次序：3-7-1-4-0-5-2-6
后序遍历访问结点次序：7-3-4-1-5-6-2-0
二叉树上述三种遍历方式的递归实现代码如下：
# 前序遍历递归实现
def pre_traverse_r(root):
if root == None:
return
else:
print(root.getName())
pre_traverse_r(root.left)
pre_traverse_r(root.right)
# 中序遍历递归实现
def in_traverse_r(root):
if root == None:
return
else:
in_traverse_r(root.left)
print(root.getName())
in_traverse_r(root.right)
# 后序遍历递归实现
def post_traverse_r(root):
if root == None:
return
else:
post_traverse_r(root.left)
post_traverse_r(root.right)
print(root.getName())
基于上文构建的二叉树，依次执行三种遍历方式，打印结点：
print('前序遍历：')
pre_traverse_r(n0)
print('中序遍历：')
in_traverse_r(n0)
print('后序遍历：')
post_traverse_r(n0)
打印结点的顺序如下：
前序遍历：
0
1
3
7
4
2
5
6
中序遍历：
3
7
1
4
0
5
2
6
后序遍历：
7
3
4
1
5
6
2
0
