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