1. 二叉树简介
首先按如下概念层级说明二叉树：数据结构 > 树 > 二叉树。
1.1 数据结构
数据结构是一种组织和存储数据的方式，它定义了一组数据元素和它们之间的关系，以及一组操作这些数据元素的规则（例如遍历、增加元素等）。数据结构可以分为线性结构（例如数组、链表等）和非线性结构（例如树、图等）。
1.2 树
树是一种非常常用的非线性数据结构，在计算机科学中被广泛应用。树是由节点和边组成的数据结构，每个节点可以连接到其他节点，最顶层的节点被称为根节点，每个节点可以没有或有若干个子节点，但是每个节点（除了根节点）都只能有一个父节点，这就形成了一个层次结构。
树的基本概念
- 节点的度：一个节点含有的子树的个数称为该节点的度；
- 树的度：一棵树中，最大的节点的度称为树的度；
- 叶节点或终端节点：度为零的节点；
- 父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
- 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
- 兄弟节点：具有相同父节点的节点互称为兄弟节点；
- 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
- 树的高度或深度：树中节点的最大层次；
- 堂兄弟节点：父节点在同一层的节点互为堂兄弟；
- 节点的祖先：从根到该节点所经分支上的所有节点；
- 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
- 森林：由m(m≥0)棵互不相交的树的集合称为森林；
1.3 二叉树
二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树(left subtree)和”右子树(right subtree)。二叉树的遍历方式可以是深度优先或广度优先。
二叉树的性质
- 性质1：在二叉树的第i层上至多有 2 i − 1 2^{i-1} 2i−1个结点；
- 性质2：深度为k的二叉树至多有 2 k − 1 2^k-1 2k−1个结点；
- 性质3：对于任意一棵二叉树，如果其叶结点数为 N 0 N_0 N0，而度数为2的结点总数为 N 2 N_2 N2，則 N 0 = N 2 + 1 N_0=N_2+1 N0=N2+1；
- 性质4：具有n个结点的完全二叉树的深度必为 l o g 2 ( n + 1 ) log_2^{(n+1)} log2(n+1)
- 性质5：对于完全二叉树，若从上至下、从左至右编号，则编号为i的结点，其左孩子编号必为2i，其右孩子编号必为2i+1，其双亲的编号必为i/2（向下取整）。
2.基于Python实现二叉树（以广度优先为例）
我们以基于Python构建下面这个二叉树为例进行代码讲解：
代码主要由以下三个类组成：
2.1 队列class queue()
class queue(): def __init__(self): self.list = [] def enqueue(self, item): self.list.append(item) def dequeue(self): return self.list.pop(0) def is_empty(self): return self.list def travel(self): #测试用 return self.list
其主要功能为给队列增加节点(enqueue)，删减节点(dequeue)，判断节点是否为空(is_empty)。
2.2 节点class Node()
class Node: #制作节点的类 def __init__(self, item): self.item = item self.right_child = None #对左右子节点进行初始化 self.left_child = None
其中self.item为该节点存储的元素，self.right_child为右子节点，self.left_child为左子节点。
注意：上面class queue()中的item是节点Node，而class Node()中的item是真正要存储的数据。
2.3 树class tree()
class Tree: #制作树的类 def __init__(self): self.root = None #初始化树根节点的值 self.queue = queue() #对queque进行实例化 def add_node(self, item): node = Node(item) if self.root == None: self.root = node else: self.queue.enqueue(self.root) cur_node = self.root while 1: if cur_node.left_child == None: cur_node.left_child = node return else: self.queue.enqueue(cur_node.left_child) if cur_node.right_child == None: cur_node.right_child = node return else: self.queue.enqueue(cur_node.right_child) cur_node = self.queue.dequeue() #通过出队列的方式进行遍历,这里是广度优先遍历
这段代码的核心是add_node方法，其构建思路是：①首先判断根节点self.root是否为空，如果为空则把要加的节点加到根节点，如果不为空则②把根节点作为当前节点cur_node，继续③判断如果当前节点的左子节点cur_node.left_child为空，则把要加的节点加到当前节点的左子节点，如果当前节点的左子节点cur_node.left_child不为空，则④把当前节点的左子节点cur_node.left_child加入队列self.queue，⑤右节点方法同③到④过程。最后进行出列（出栈），⑥把队列self.queue的第一个元素取出，作为当前节点cur_node，继续③到⑥整个过程，直到找到空节点用于存储要加的节点。
3. 完整代码
class queue(): def __init__(self): self.list = [] def enqueue(self, item): self.list.append(item) def dequeue(self): return self.list.pop(0) def is_empty(self): return self.list def travel(self): #测试用 return self.list class Node: #制作节点的类 def __init__(self, item): self.item = item self.right_child = None #对左右子节点进行初始化 self.left_child = None class Tree: #制作树的类 def __init__(self): self.root = None #初始化树根节点的值 self.queue = queue() #对queque进行实例化 def add_node(self, item): node = Node(item) if self.root == None: self.root = node else: # self.queue.enqueue(self.root) cur_node = self.root while 1: if cur_node.left_child == None: cur_node.left_child = node return else: self.queue.enqueue(cur_node.left_child) if cur_node.right_child == None: cur_node.right_child = node return else: self.queue.enqueue(cur_node.right_child) cur_node = self.queue.dequeue() #通过出队列的方式进行遍历,这里是广度优先遍历 # 构造一个这种树 # 1 # 2.1 2.2 # 3.1 3.2 3.3 tree_construction = Tree() tree_construction.add_node(1) tree_construction.add_node(2.1) tree_construction.add_node(2.2) tree_construction.add_node(3.1) tree_construction.add_node(3.2) tree_construction.add_node(3.3) # tree_construction.add_node(3.4) # print(tree_construction.queue.list[3].item)
