Python带你了解数据结构【二】
上次我们介绍了线性的数据结构，数组，链表，栈，队列，这次我们来看看非线性的数据结构。
非线性的数据结构主要是：树（Tree），图（Graph），堆（Heap），散列表（Hash）
树（Tree）
谈到树，先给大家看幅图：
上图就是一个简单的家谱图，这就是一个简单的树。在数据结构中，树的定义是：它是由n（n>0）个有限节点组成一个具有层次关系的集合。
就像上图一样，家谱中的每个人都是一个节点，每个节点又可以再生出其他节点。作为树，应该包含下面几个特点：
1、家谱中都有应该最原始的祖先，也就是这个家中的第一人（即每个树都有固定的根节点）
2、家谱中的每个人都可以有自己的孩子或者不生孩子（即每个节点都只有有限个子节点或者没有子节点）
3、每个人在家谱中都只有唯一的父母（非根结点只有唯一的一个父节点）
4、家谱中的每个人都可以组成自己的家庭，他们都是自己家庭里最有辈分的那个人（树中的每个非根节点，都可以有自己的子树，例如上图中的女儿和外孙女就可以构成一个子树）
5、家谱里的人不可以近亲结婚或者乱伦（树里面没有环路）
以上便是数据结构中树的介绍，但是在常用的数据结构中，我们会经常使用一个特别的树————二叉树。二叉树是什么意思呢？就是树中的每个节点最多只能有两个孩子节点（换个说法就是在家谱里，你最多只能生个二胎，不能再生更多了！）
如上图，每个根节点最多只能有两个孩子节点，这就是二叉树，二叉树也有两个很特别的形式，一个叫满二叉树，也就是上图，每个节点都有两个孩子。另外一个叫完全二叉树，完全二叉树是什么意思呢?将所有节点按照上图进行编号，1-15,如果有新的树按照上面这样的形式编号，并且每个节点的编号都和上图的编号一样，这就是完全二叉树，（例如上图，我把L和M节点去掉，K以及之前的的编号都不变，N和O的编号变成了12，13，那N，O和之前的编号不一样了，所以他们就不是完全二叉树，如果把N和O节点去掉，我们发现因为他们是末尾的节点，根本不需要改变前面节点的编号，所以还是原来的编号，这就是完全二叉树）说白了就是，要么就全满，如果缺了，那后面就都不能再有了。
关于二叉树，我们可以使用什么物理结构来存储呢？链表和数组都是可以实现的。
下面我们来使用python代码来构建一个二叉树：
# 二叉树类
class BTree(object):
# 初始化
def __init__(self, data=None, left=None, right=None):
self.data = data # 数据域
self.left = left # 左子树
self.right = right # 右子树
# 二叉树的高度
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.left is not None and self.right is 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()这样我们也就初步构建好了一个二叉树，下面我们来聊聊，二叉树常见的几种遍历方式。遍历（遍历的意思就是沿着某条搜索路线，依次对节点进行访问）主要有两种方式，深度优先遍历和广度优先遍历。
深度优先遍历一共有三种，分别是前序、中序、后序遍历。
前序遍历：先输出根节点，再输出左子树，最后输出右子树。
对应上图的顺序是：ABDECFG
# 前序遍历
def preorder(self):
if self.data is not None:
print(self.data, end=' ')
if self.left is not None:
self.left.preorder()
if self.right is not None:
self.right.preorder()中序遍历：先输出左子树，在输出根节点，最后输出右子树。
对应上图的顺序是：DBEAFCG
# 中序遍历
def inorder(self):
if self.left is not None:
self.left.inorder()
if self.data is not None:
print(self.data, end=' ')
if self.right is not None:
self.right.inorder()后序遍历：先输出左子树，再输出右子树，最后输出根节点。
对应上图的顺序是：DEBFGCA
# 后序遍历
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=' ')除了深度优先遍历，还有广度优先遍历，层序遍历就是属于广度优先遍历。
层序遍历：比较简单，一层一层的遍历即可。当层遍历结束进入下一层
对应上图的顺序是：ABCDEFG
# 层序遍历
def levelorder(self):
# 返回某个节点的左孩子
def Left_Child_Of_Node(node):
return node.left if node.left is not None else None
# 返回某个节点的右孩子
def Right_Child_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 Left_Child_Of_Node(node):
level.append(Left_Child_Of_Node(node))
# 如果右孩子非空，则添加右孩子
if Right_Child_Of_Node(node):
level.append(Right_Child_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堆（Heap）
堆的存储方式就是上面我们介绍的完全二叉树。堆主要分为最大堆和最小堆，这个很好区分，最大值都放在堆顶，且任何一个子节点的值都必须小于或者等于父节点的值，这就是最大堆。最小堆正好相反。（堆的根节点我们叫做堆顶）
堆的两个特性：
1、堆中某个节点的值总是不大于或不小于其父节点的值
2、堆总是一棵完全二叉树
堆里面也有特别的————二叉堆，二叉堆是一种特殊的堆，是一棵完全二叉树或者是近似完全二叉树，并且同时还满足堆的特性：父节点的键值总是保持固定的序关系于任何一个子节点的键值，且每个节点的左子树和右子树都是一个二叉堆。
如何去构建一个堆呢？我们看下图，用一个数组作为例子：
首先我们需要将数组构建成一个完全二叉树，之后我们将完全二叉树做成一个最大堆：
接下来呢，我们需要将无序的完全二叉树构建成有序的最大堆，操作的主要内容就是让所有的非叶子节点往下走，一直走到适合自己的位置。
下面我们使用Python代码来构建一个堆：
class BinHeap:
def __init__(self):
self.heapList = [0]
self.currentSize = 0
def up_adjust(self, i): # 二叉堆上浮操作
while i // 2 > 0:
if self.heapList[i] <= self.heapList[i // 2]:
self.heapList[i], self.heapList[i // 2] = self.heapList[i // 2], self.heapList[i]
i = i // 2
def insert_value(self, k):
self.heapList.append(k)
self.currentSize = self.currentSize + 1
self.up_adjust(self.currentSize)
def down_adjust(self, i): # 二叉堆下沉操作
while (i * 2) <= self.currentSize:
mc = self.get_min_child(i)
if self.heapList[i] > self.heapList[mc]:
tmp = self.heapList[i]
self.heapList[i] = self.heapList[mc]
self.heapList[mc] = tmp
i = mc
def get_min_child(self, i):# 获取最小值
if i * 2 > self.currentSize:
return i * 2
else:
if self.heapList[i * 2] < self.heapList[i * 2 + 1]:
return i * 2
else:
return i * 2 + 1
def del_min(self):# 删除最小值
retval = self.heapList[1]
self.heapList[1] = self.heapList[self.currentSize]
self.currentSize = self.currentSize - 1
self.heapList.pop()
self.down_adjust(1)
return retval
def build_heap(self, array):# 构建堆
i = len(array) // 2
self.currentSize = len(array)
self.heapList = [0] + array[:]
while i > 0:
self.down_adjust(i)
i = i - 1为节点类，要具备一些常用的方法，获取节点数据，获取下个节点，更新节点的数据，更新下个节点，这些都可以定义在node类里面。堆的主要用途就是实现堆排序和优先队列。
图（Graph）
图，也是一种非线性的数据结构，是数据结构中最强大的结构之一，树就属于图的一种。
在图的结构中，任意两个结点之间都可能相关，即结点之间的邻接关系是任意的。而在树形结构中，结点之间具有层次关系，每一层结点只能和上一层中的至多一个结点相关，但可能和下一层的多个结点相关。图的结构可以描述多种复杂的数据对象，应用较为广泛。图的结构非常多，例如：邻接矩阵、邻接表、十字链表和邻接多重表等。
在生活中，图的应用也是十分广泛的，下面两个例子就是最常用的图的思想：
图对我们来说，其实主要是一种思想，了解了图的思想之后，再选择对应的物理存储结构去解决问题。
# 图的一种：邻接矩阵
class Graph:
def __init__(self, n_vertices):
self._n_vertices = n_vertices
self._adj = [[] for _ in range(n_vertices)]
def add_edge(self, s, t):
self._adj[s].append(t)散列表（Hash）
散列表，又叫哈希表。它在python里面存在的主要形式就是字典了，根据key来查找对应value的值。通过计算key的函数，将需要查询的值映射到一个固定的位置。这个映射就是散列表。最常见的用途就是哈希函数，例如MD5，SHA1等。
哈希表的本质其实也是一个数组，和数组不同的是我们需要通过一些中间函数进行转换，转换过后取到对应的值。而这个中间函数就是哈希函数。
哈希表的更新，删除，取值对应的python种字典的对应操作：
谈到哈希表，我们有个问题就不得不说一下，那就是哈希冲突。
什么是哈希冲突呢？我们来看下图：
我们要在五个箱子内放六个球，每个箱子只能放入一个球。但我们发现，如果真的想把球都放进去，就必须要有一个箱子里面装两个，这就冲突了。那对于哈希表而言，也可能会出现这样的情况，当存储区域小于需要存储数据的时候，就会发生哈希冲突。
如何解决哈希冲突呢？我们右两种办法：链表法和开放寻址法。
链表法：哈希表的每个元素不仅是对象，也是一个链表的头节点，每个对象通过next指针指向下个对象节点，当新的元素进来产生冲突时，只需要将其插入到对应的链表中就OK了。
开放寻址法：当某个哈希值已经被占用的情况下，继续寻找下一个空着的位置。以此类推。直到找到空的为止。python里面的字典就是采用的该方法。