第五章 树和二叉树
树和二叉树的定义
1、树的定义
一种非线性结构。树是递归结构，在树的定义中又用到了树的概念。
基本术语：
树结点：包含一个数据元素及若干指向子树的分支；
孩子结点：结点的子树的根称为该结点的孩子；
双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲；
兄弟结点：同一双亲的孩子结点；
堂兄结点：同一层上结点；
结点层次：根结点的层定义为1；根的孩子为第二层结点，依此类推；
树的高（深）度：树中最大的结点层
结点的度：结点子树的个数
树的度： 树中最大的结点度。
叶子结点：也叫终端结点，是度为0的结点；
分枝结点：度不为0的结点（非终端结点）；
森林：互不相交的树集合；
有序树：子树有序的树，如：家族树；
无序树：不考虑子树的顺序；
2、树的基本定义
3、二叉树的定义
二叉树
二叉树可以为空。二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。注意区分：二叉树、二叉查找树/二叉排序树/二叉搜索树、二叉平衡(查找)树二叉平衡树肯定是一颗二叉排序树。堆不是一颗二叉平衡树。二叉树与树是不同的，二叉树不等价于分支树最多为二的有序树。当一个结点只包含一个子节点时，对于有序树并无左右孩子之分，而对于二叉树来说依然有左右孩子之分，所以二叉树与树是两种不同的结构。
1、二叉树的性质
性质：
在二叉树的第 i 层上至多有2i-1个结点。
深度为 k 的二叉树上至多含 2k-1 个结点（k≥1）
对任何一棵二叉树，若它含有n0个叶子结点、n2个度为 2 的结点，则必存在关系式：n0= n2+1。
具有 n 个结点的完全二叉树的深度为⎣log2 n⎦+1 。
n个结点的二叉树中，完全二叉树具有最小的路径长度。
如果对一棵有n个结点的完全二叉树的结点按层序编号,则对任一结点i（1<=i<=n),有：
如果i＝1，则结点i无双亲，是二叉树的根；如果i>1，则其双亲的编号是 i/2(整除）。
如果2i>n，无左孩子；否则，其左孩子是结点2i。
如果2i＋1>n，则结点i无右孩子；否则，其右孩子是结点2i＋1。
2、二叉树的存储结构
二叉树的存储结构
顺序存储结构：仅仅适用于满或完全二叉树，结点之间的层次关系由性质5确定。
二叉链表法：每个节点存储左子树和右子树。三叉链表：左子树、右子树、父节点，总的指针是n+2
在有n个结点的二叉链表中，值为非空的链域的个数为n-1。在有N个结点的二叉链表中必定有2N个链域。除根结点外，其余N-1个结点都有一个父结点。所以，一共有N-1个非空链域，其余2N-(N-1)=N+1个为空链域。
二叉链存储法也叫孩子兄弟法，左指针指向左孩子，右指针指向右兄弟。而中序遍历的顺序是左孩子，根，右孩子。这种遍历顺序与存储结构不同，因此需要堆栈保存中间结果。而中序遍历检索二叉树时，由于其存储结构跟遍历顺序相符，因此不需要用堆栈。
遍历二叉树和线索二叉树
1、遍历二叉树
遍历二叉树：使得每一个结点均被访问一次，而且仅被访问一次。非递归的遍历实现要利用栈。
先序遍历DLR：根节点->左子树->右子树
中序遍历LDR：左子树->根节点->右子树。必须要有中序遍历才能得到一棵二叉树的正确顺序
后续遍历LRD：左子树->右子树->根节点。需要栈的支持。
层次遍历：用一维数组存储二叉树时,总是以层次遍历的顺序存储结点。层次遍历应该借助队列。
2、线索二叉树
线索二叉树：对二叉树所有结点做某种处理可在遍历过程中实现；检索（查找）二叉树某个结点，可通过遍历实现；如果能将二叉树线索化，就可以简化遍历算法，提高遍历速度，目的是加快查找结点的前驱或后继的速度。
如何线索化？以中序遍历为例，若能将中序序列中每个结点前趋、后继信息保存起来，以后再遍历二叉树时就可以根据所保存的结点前趋、后继信息对二叉树进行遍历。对于二叉树的线索化，实质上就是遍历一次二叉树，只是在遍历的过程中，检查当前结点左，右指针域是否为空，若为空，将它们改为指向前驱结点或后继结点的线索。前驱就是在这一点之前走过的点，不是下一将要去往的点。
加上结点前趋后继信息（结索）的二叉树称为线索二叉树。n个结点的线索二叉树上每个结点有2个指针域（指向左孩子和右孩子），总共有2n个指针域；一个n个结点的树有n-1条边，那么空指针域= 2n - (n-1) = n + 1，即线索数为n+1。指针域tag为0，存放孩子指针，为1，存放前驱/后继节点指针。
线索树下结点x的前驱与后继查找：设结点x相应的左（右）标志是线索标志，则lchild(rchild)就是前驱(后继），否则：
LDR–前驱：左子树中最靠右边的结点；后继：右子树中最靠左边的结点
LRD–前驱：右子树的根，若无右子树，为左子树跟。后继：x是根，后继是空；x是双亲的右孩子、x是双亲的左孩子，但双亲无右孩子，双亲是后继；x是双亲的左孩子，双亲有右孩子，双亲右子树中最左的叶子是后继
DLR–对称于LRD线索树—将LRD中所有左右互换，前驱与后继互换，得到DLR的方法。
为简化线索链表的遍历算法，仿照线性链表，为线索链表加上一头结点，约定：
头结点的lchild域：存放线索链表的根结点指针；
头结点的rchild域: 中序序列最后一个结点的指针；
中序序列第一结点lchild域指向头结点;
中序序列最后一个结点的rchild域指向头结点;
中序遍历的线索二叉树以及线索二叉树链表示意图
一棵左右子树均不空的二叉树在前序线索化后,其中空的链域的个数是1。前序和后续线索化后空链域个数都是1，中序是2。二叉树在线索化后，仍不能有效求解的问题是前序求前序先驱，后序求后序后继。
中序遍历的顺序为：左、根、右，所以对于每一非空的线索，左子树结点的后继为根结点，右子树结点的前驱为根结点，再递归的执行上面的过程，可得非空线索均指向其祖先结点。在中序线索二叉树中,每一非空的线索均指向其祖先结点。
在二叉树上加上结点前趋、后继线索后，可利用线索对二叉树进行遍历,此时，不需栈，也不需递归。基本步骤：
p=T->lchild; p指向线索链表的根结点；
若线索链表非空，循环：
循环，顺着p左孩子指针找到最左下结点；访问之；
若p所指结点的右孩子域为线索，p的右孩子结点即为后继结点循环： p=p->rchild； 并访问p所指结点；（在此循环中，顺着后继线索访问二叉树中的结点）
一旦线索“中断”，p所指结点的右孩子域为右孩子指针，p=p->rchild，使 p指向右孩子结点；
树和二叉树抽象数据类型定义
树和森林
1、树的存储结构
树的存储结构：
双亲表示法
孩子表示法
利用图表示树
孩子兄弟表示法（二叉树表示法）：链表中每个结点的两指针域分别指向其第一个孩子结点和下一个兄弟结点
将树转化成二叉树：右子树一定为空
加线：在兄弟之间加一连线
抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系
旋转：以树的根结点为轴心，将整树顺时针转45°
2、森林与二叉树的转换
将各棵树分别转换成二叉树
将每棵树的根结点用线相连
以第一棵树根结点为二叉树的根
3、树与森林的遍历
树与转换后的二叉树的关系：转换后的二叉树的先序对应树的先序遍历；转换后的二叉树的中序对应树的后序遍历
哈夫曼树/霍夫曼树及其应用
1、哈夫曼树的基本概念
2、哈夫曼树的构造算法
3、哈夫曼编码
哈弗曼树概念：
路径：从一个祖先结点到子孙结点之间的分支构成这两个结点间的路径；
路径长度：路径上的分支数目称为路径长度；
树的路径长度：从根到每个结点的路径长度之和。
结点的权：根据应用的需要可以给树的结点赋权值；
结点的带权路径长度：从根到该结点的路径长度与该结点权的乘积；
树的带权路径长度=树中所有叶子结点的带权路径之和；通常记作 WPL=∑wi×li
哈夫曼树：假设有n个权值(w1, w2, … , wn)，构造有n个叶子结点的二叉树，每个叶子结点有一个 wi作为它的权值。则带权路径长度最小的二叉树称为哈夫曼树。最优二叉树。
前缀码的定义：在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀。霍夫曼编码就是前缀码，可用于快速判断霍夫曼编码是否正确。霍夫曼树是满二叉树，若有n个节点，则共有(n+1)/2个码子
给定n个权值作为n的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为霍夫曼树(Huffman Tree)。霍夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
假设哈夫曼树是二叉的话，则度为0的结点个数为N，度为2的结点个数为N-1，则结点总数为2N-1。哈夫曼树的结点个数必为奇数。
哈夫曼树不一定是完全二叉树，但一定是最优二叉树。
若度为m的哈夫曼树中,其叶结点个数为n,则非叶结点的个数为[(n-1)/(m-1)]。边的数目等于度。
第六章 图
图的定义和基本术语
1、图的定义——一种非线性结构。树是递归结构，在树的定义中又用到了树的概念。
2、图的基本术语
3、图的类型定义
无向图
回路或环：第一个顶点和最后一个顶点相同的路径。
简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路
连通：顶点v至v’ 之间有路径存在
连通图：无向图图 G 的任意两点之间都是连通的，则称G是连通图。
连通分量：极大连通子图，子图中包含的顶点个数极大
所有顶点度的和必须为偶数
有向图：
回路或环：第一个顶点和最后一个顶点相同的路径。
简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。
连通：顶点v至v’之间有路径存在
强连通图：有向图G的任意两点之间都是连通的，则称G是强连通图。各个顶点间均可达。
强连通分量：极大连通子图
有向图顶点的度是顶点的入度与出度之和。邻接矩阵中第V行中的1的个数是V的出度
生成树：极小连通子图。包含图的所有n个结点，但只含图的n-1条边。在生成树中添加一条边之后，必定会形成回路或环。
完全图：有 n(n-1)/2 条边的无向图。其中n是结点个数。必定是连通图。
有向完全图：有n(n-1)条边的有向图。其中n是结点个数。每两个顶点之间都有两条方向相反的边连接的图。
一个无向图 G=(V,E) 是连通的，那么边的数目大于等于顶点的数目减一：|E|>=|V|-1，而反之不成立。如果 G=(V,E) 是有向图，那么它是强连通图的必要条件是边的数目大于等于顶点的数目：|E|>=|V|，而反之不成立。没有回路的无向图是连通的当且仅当它是树，即等价于：|E|=|V|-1。
图的存储结构
图的存储形式
邻接矩阵和加权邻接矩阵
无权有向图：出度: i行之和；入度: j列之和。
无权无向图：i结点的度: i行或i列之和。
加权邻接矩阵：相连为w，不相连为∞
邻接表
用顶点数组表、边（弧）表表示该有向图或无向图
顶点数组表：用数组存放所有的顶点。数组大小为图顶点数n
边表（边结点表）：每条边用一个结点进行表示。同一个结点的所有的边形成它的边结点单链表。
n个顶点的无向图的邻接表最多有n(n-1)个边表结点。有n个顶点的无向图最多有n*(n-1)/2条边，此时为完全无向图，而在邻接表中每条边存储两次，所以有n*(n-1)个结点
1、邻接矩阵
2、邻接表
3、十字链表
4、邻接多重表
图的遍历
深度优先搜索利用栈，广度优先搜索利用队列
求一条从顶点i到顶点s的简单路径–深搜。求两个顶点之间的一条长度最短的路径–广搜。当各边上的权值均相等时,BFS算法可用来解决单源最短路径问题。
图遍历与回溯
图搜索->形成搜索树
穷举法。
贪心法。多步决策，每步选择使得构成一个问题的可能解，同时满足目标函数。
回溯法。根据题意，选取度量标准，然后将可能的选择方法按度量标准所要求顺序排好，每次处理一个量，得到该意义下的最优解的分解处理。
图
1、深度优先搜索
2、广度优先搜索
图的应用
1、生成树和最小生成树
每次遍历一个连通图将图的边分成遍历所经过的边和没有经过的边两部分，将遍历经过的边同图的顶点构成一个子图，该子图称为生成树。因此有DFS生成树和BFS生成树。
生成树是连通图的极小子图，有n个顶点的连通图的生成树必定有n-1条边,在生成树中任意增加一条边，必定产生回路。若砍去它的一条边，就会把生成树变成非连通子图
最小生成树：生成树中边的权值(代价)之和最小的树。最小生成树问题是构造连通网的最小代价生成树。
Kruskal算法：令最小生成树集合T初始状态为空，在有n个顶点的图中选取代价最小的边并从图中删去。若该边加到T中有回路则丢弃，否则留在T中；依此类推，直至T中有n-1条边为止。
Prim算法、Kruskal算法和Dijkstra算法均属于贪心算法。
Dijkstra算法解决的是带权重的有向图上单源最短路径问题，该算法要求所有边的权重都为非负值。
Dijkstra算法解决了从某个原点到其余各顶点的最短路径问题，由循环嵌套可知该算法的时间复杂度为O(N*N)。若要求任一顶点到其余所有顶点的最短路径，一个比较简单的方法是对每个顶点当做源点运行一次该算法，等于在原有算法的基础上，再来一次循环，此时整个算法的复杂度就变成了O(N*N*N)。
Bellman-Ford算法解决的是一般情况下的单源最短路径问题，在这里，边的权重可以为负值。该算法返回一个布尔值，以表明是否存在一个从源节点可以到达的权重为负值的环路。如果存在这样一个环路，算法将告诉我们不存在解决方案。如果没有这种环路存在，算法将给出最短路径和它们的权重。
2、最短的路径
3、拓扑排序
双连通图和关节点
若从一个连通图中删去任何一个顶点及其相关联的边，它仍为一个连通图的话，则该连通图被称为重（双）连通图。
若连通图中的某个顶点和其相关联的边被删去之后，该连通图被分割成两个或两个以上的连通分量，则称此顶点为关节点。
没有关节点的连通图为双连通图若生成树的根结点，有两个或两个以上的分支，则此顶点(生成树的根)必为关节点；
对生成树上的任意一个非叶“顶点”，若其某棵子树中的所有“顶点”没有和其祖先相通的回边，则该“顶点”必为关节点。
一些定义：
事件的最早发生时间（ve(j)）：从源点到j结点的最长的路径。意味着事件最早能够发生的时间。
事件的最迟发生时间（vl(j)）：不影响工程的如期完工，事件j必须发生的时间。
活动ai由弧
有向无环图及其应用
拓扑排序。在用邻接表表示图时,对有n个顶点和e条弧的有向图而言时间复杂度为O(n+e)。一个有向图能被拓扑排序的充要条件就是它是一个有向无环图。拓扑序列唯一不能唯一确定有向图。
AOV网(Activity On Vertex)：用顶点表示活动，边表示活动的优先关系的有向图称为AOV网。AOV网中不允许有回路，这意味着某项活动以自己为先决条件。
拓扑有序序列：把AOV网络中各顶点按照它们相互之间的优先关系排列一个线性序列的过程。若vi是vj前驱，则vi一定在vj之前；对于没有优先关系的点，顺序任意。
拓扑排序：对AOV网络中顶点构造拓扑有序序列的过程。方法：
在有向图中选一个没有前驱的顶点且输出之
从图中删除该顶点和所有以它为尾的弧
重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止(此时说明图中有环）
采用深度优先搜索或拓扑排序算法可以判断出一个有向图中是否有环(回路).深度优先搜索只要在其中记录下搜索的节点数n，当n大于图中节点数时退出，并可以得出有回路。若有回路，则拓扑排序访问不到图中所有的节点，所以也可以得出回路。广度优先搜索过程中如果访问到一个已经访问过的节点，可能是多个节点指向这个节点，不一定是存在环。
算法描述：
把邻接表中入度为0的顶点依此进栈
若栈不空，则
栈顶元素vj退栈并输出；
在邻接表中查找vj的直接后继vk，把vk的入度减1；若vk的入度为0则进栈
若栈空时输出的顶点个数不是n，则有向图有环；否则，拓扑排序完毕。
AOE网：带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间。在工程上常用来表示工程进度计划。
4、关键路径
Java。大家都知道，我们是学Java全栈的，大家就肯定以为我有全套的Java系统教程。没错，我是有Java全套系统教程，进扣裙【47】974【9726】所示，今天小编就免费送!~
“我们相信人人都可以成为一个程序员，现在开始，找个师兄，带你入门，学习的路上不再迷茫。这里是ja+va修真院，初学者转行到互联网行业的聚集地
网友评论