一、树的概念
树是一种数据结构，树由结点及连接结点的边组成，每个树有且只有一个根结点，除了根结点以外，其它每个结点都与其有唯一的父结点相连，其中根结点到其它每个结点也有且只有一条路径。
1、二叉树
若树中每个节点最多有两个子结点，则称为二叉树，即每个结点的子结点不超过两个，由根结点分叉的两个结点中，左边称为左子树，右边称为右子树，如下图：
2、满二叉树
若一个深度为k的树，具有2k-1个结点，则称该树为满二叉树，如下图该树的深度为k=3，其结点数为2k-1=23-1=7个：
而如下图这两个树都不是满二叉树：
3、完全二叉树
若一个深度为k的树，其结点为n个，对树中的结点按从上到下、从左到右的顺序进行编号，当每一个结点都与同样深度为k的满二叉树中的结点一一对应时，则称该树为完全二叉树。
完全二叉树中，从根节点至倒数第二层满足满二叉树，其最后一层的结点可以不完全填满，可以说若一棵二叉树是满二叉树时，则它一定是完全二叉树，如下图这两个树都是完全二叉树，但它们不是满二叉树：
4、完满二叉树
无子结点的结点称为叶子结点，若一个树的非叶子结点的结点数都为2，即都有两个子结点时，则称这个树为完满二叉树，如下图：
二、二叉树的实现
二叉树的python代码实现有两种方法，第一种称作“列表的列表”的形式，也就是列表的反复嵌套，第二种称作“结点与引用”，通过设置一个类。
（一）列表的列表
1、二叉树的结点实现和输出
在Python中，我们可以通过“列表的列表”这种方式来实现树的python代码，即列表的多层嵌套，例如下面这个树的实现python代码：
Tree = ["1", ["2", ["4", [], []], ["5", [], []]], ["3", [], []]]
我们可以通过列表的索引和切片来输出树中的结点，如下代码：
Tree = ["1", ["2", ["4", [], []], ["5", [], []]], ["3", [], []]] print(Tree[0]) # 输出根结点 print(Tree[1]) # 输出该树的左子树 print(Tree[2]) # 输出该树的右子树 print(Tree[1][0]) print(Tree[1][1]) print(Tree[1][1][0]) print(Tree[1][2][0]) print(Tree[1][1][1]) print(Tree[2:])
运行结果如下：
2、二叉树的创建
二叉树的创建通过创建一个列表，由于二叉树由根结点和左子树和右子树组成，一开始将左右子树定义为空列表，即根结点为r，左右子树此时都为[]。
定义一个函数BinaryTree()用于创建一个二叉树，如下代码：
def BinaryTree(r): return [r, [], []] # 返回二叉树
3、左右子树的结点添加
我们要向已经创建好的二叉树中添加左右子树（左右子树中的结点），所以要先获取当前的左或右子树对应的列表（可能为空），然后将新的左或右子树添加进去，从而实现在二叉树的任何位置实现结点添加。
定义两个函数insertLeft()与insertRight()分别用于左右子树的结点添加，如下代码：
def insertLeft(root, newBranch): # 新建一个左子树，将其作为当前结点的左子结点 t = root.pop(1) # pop()函数用于删除列表中指定元素 if len(t) > 1: root.insert(1, [newBranch, t, []]) # insert()函数用于将元素插入到列表的指定位置 else: root.insert(1, [newBranch, [], []]) return root def insertRight(root, newBranch): # 新建一个右子树，将其作为当前结点的右子结点 t = root.pop(2) # pop()函数用于删除列表中指定元素 if len(t) > 1: root.insert(2, [newBranch, [], t]) # insert()函数用于将元素插入到列表的指定位置 else: root.insert(2, [newBranch, [], []]) return root
4、另外定义几个函数用于返回二叉树以及结点存储的对象，getRootVal()函数给出参数root从而返回当前结点存储的对象；setRootVal()函数给出参数root和newVal在当前结点存储参数newVal的对象；getLeftChild()和getRightChild()函数给出参数root用于返回当前结点的左/右结点所对应的子二叉树，如下代码：
def getRootVal(root): # 返回当前结点存储的对象 return root[0] def setRootVal(root, newVal): # 在当前结点中存储参数newVal的对象 root[0] = newVal def getLeftChild(root): # 返回当前结点的左子结点所对应的子二叉树 return root[1] def getRightChild(root): # 返回当前结点的右子结点所对应的子二叉树 return root[2]
（二）结点与引用
另外一种对树的定义方法是通过定义一个类，类中含有根结点以及左右子树的属性，如下图：
1、BinaryTree类的创建
通过创建一个BinaryTree类作为树的初始化，其中包括根结点rootObj，以及空的左右子树，代码如下：
# 创建一个树BinaryTree类 class BinaryTree: # 定义一个构造方法用于创建新的结点，参数rootObj作为此时的根结点 def __init__(self, rootObj): self.key = rootObj # 根结点 self.leftChild = None # 此时左子树为空 self.rightChild = None # 此时右子树为空
2、左右子树的结点添加
左右子树的结点添加要考虑两种情况，一是向无子结点的结点下添加，二是向已有子结点的结点下添加，如下以左结点添加为例：
在类下定义两个方法，insertLeft()和insertRight()分别用于添加左/右结点，都含有一个参数newNode用于接收结点，其代码实现如下：
# 插入左结点 def insertLeft(self, newNode): if self.leftChild is None: # 无左结点时 self.leftChild = BinaryTree(newNode) else: t = BinaryTree(newNode) # 实例化对象，创建新的结点 t.left = self.leftChild self.leftChild = t # 插入右结点 def insertRight(self, newNode): if self.rightChild is None: # 无右结点时 self.rightChild = BinaryTree(newNode) else: t = BinaryTree(newNode) # 实例化对象，创建新的结点 t.left = self.rightChild self.rightChild = t
3、另外定义几个函数用于返回二叉树以及结点存储的对象，getRootVal()函数返回当前结点存储的对象；setRootVal()函数给出参数obj用于在当前结点存储对象；getLeftChild()和getRightChild()函数给出参数用于返回当前结点的左/右结点所对应的子二叉树，如下代码：
def getRightChild(self): return self.rightChild def getLeftChild(self): return self.leftChild def setRootVal(self, obj): self.key = obj def getRootVal(self): return self.key
程序的完整代码如下：
# 创建一个树BinaryTree类 class BinaryTree: # 定义一个构造方法用于创建新的结点，参数rootObj作为此时的根结点 def __init__(self, rootObj): self.key = rootObj # 根结点 self.leftChild = None # 此时左子树为空 self.rightChild = None # 此时右子树为空 # 插入左结点 def insertLeft(self, newNode): if self.leftChild is None: # 无左结点时 self.leftChild = BinaryTree(newNode) else: t = BinaryTree(newNode) # 实例化对象，创建新的结点 t.left = self.leftChild self.leftChild = t # 插入右结点 def insertRight(self, newNode): if self.rightChild is None: # 无右结点时 self.rightChild = BinaryTree(newNode) else: t = BinaryTree(newNode) # 实例化对象，创建新的结点 t.left = self.rightChild self.rightChild = t def getRightChild(self): return self.rightChild def getLeftChild(self): return self.leftChild def setRootVal(self, obj): self.key = obj def getRootVal(self): return self.key
如下是一个二叉树，通过程序实现：
代码如下：
tree = BinaryTree(1) print(tree.getRootVal()) print(tree.getLeftChild()) tree.insertLeft(2) tree.insertRight(3) print(tree.getLeftChild().getRootVal()) print(tree.getRightChild().getRootVal()) tree.insertLeft(4) tree.insertRight(5) print(tree.getLeftChild().getRootVal()) print(tree.getRightChild().getRootVal()) tree.insertLeft(6) print(tree.getLeftChild().getRootVal())
运行结果如下：
三、图的概念
图是一种数据结构，前面所讲的树其实就是一种特殊的图，图的两个顶点之间通过一条边来使其联系，这里的边可以是单向或双向，若一个图中所有的边都为单向，则称整个图为有向图，如下（其中边上的数字代表权重）：
1、图的定义和权重
图定义为G =(V，E)，其中V是一个顶点集合，E是一个边集合，每一条边都是一个二元组（v，w），且v，w∈V，可以向边的二元组中再添加一个元素，用于表示权重，即从图上一个顶点到另一个顶点所需的成本，若一个有向图带有权重，则称为带权有向图。
例如，上图的带权有向图可以通过两个集合来描述该图：
V = {a, b, c, d, e, f} E = {(a, f, 1), (f, e, 2), (e, d, 2), (b, a, 1), (b, c, 3), (c, d, 5), (c, g, 4), (g, a, 2)}
2、路径
路径是由边连接的顶点组成的序列，不带权重的图的路径长度是路径上的边数，带权重的图的路径长度是路径上边的权重之和，例如上图中，从c到a的路径是顶点序列（c，g，a），其相对应的边是{(c, g, 4), (g, a, 2)}，如下：
3、环
环是有向图中的一条起点和终点为同一个顶点的路径，比如下图的路径（a，b，c，d，e，f，a）就是一个环。
若一个图没有环，则称为无环图，没有环的有向图称为有向无环图，也称为DAG，例如前面的这个图就是一个DAG：
四、图的实现
图的实现有两种常用的方法实现，分别是邻接矩阵和邻接表，邻接矩阵适合有很多边的图，而邻接表适合稀疏连接的图。
（一）邻接矩阵
通过邻接矩阵实现图，具体步骤是通过一个二维矩阵表示，其中的数字代表顶点到顶点的权重，如下：
（二）邻接表
具体代码如下：
class Vertex: def __init__(self, key): self.id = key self.connectedTo = {} def addNeighbor(self, nbr, weight=0): self.connectedTo[nbr] = weight def __str__(self): return str(self.id) + ' connectedTo: ' + str([x.id for x in self.connectedTo]) def getConnections(self): return self.connectedTo.keys() def getId(self): return self.id def getWeight(self, nbr): return self.connectedTo[nbr] class Graph: def __init__(self): self.vertList = {} self.numVertices = 0 def addVertex(self, key): self.numVertices = self.numVertices + 1 newVertex = Vertex(key) self.vertList[key] = newVertex return newVertex def getVertex(self, n): if n in self.vertList: return self.vertList[n] else: return None def __contains__(self, n): return n in self.vertList def addEdge(self, f, t, cost=0): if f not in self.vertList: nv = self.addVertex(f) if t not in self.vertList: nv = self.addVertex(t) self.vertList[f].addNeighbor(self.vertList[t], cost) def getVertices(self): return self.vertList.keys() def __iter__(self): return iter(self.vertList.values()) g = Graph() for i in range(7): g.addVertex(i) g.addEdge("a", "f", 1) g.addEdge("f", "e", 2) g.addEdge("e", "d", 2) g.addEdge("b", "a", 1) g.addEdge("b", "c", 3) g.addEdge("c", "d", 5) g.addEdge("c", "g", 4) g.addEdge("g", "a", 2) for v in g: for w in v.getConnections(): print("( %s , %s )" % (v.getId(), w.getId()))
运行结果如下：
