《大话数据结构》（二）

六、树

A.树的定义

1.树（Tree）是n(n>=0)个结点的有限集。n=0时称为空树。在任意一颗非空树中：(1)有且仅有一个特定的称为根(Root)的结点；(2)当n>1时，其余节点可分为m(m>0)个互不相交的有限集T1、T2……Tm，其中每一个集合本身又是一颗树，并且称为根的子树(SubTree)

2.强调：n>0时根结点是唯一的，不可能存在多个根结点；m>0时，子树的个数没有限制，但它们一定是互不相交的；

3.结点分类：结点拥有的子树数称为结点的度(Degree)。度为0的结点称为叶子节点(Leaf)或终端结点；度不为0的结点称为非终端结点或分支结点。除根结点外，分支结点也称为内部结点。树的度是树内部各结点的度的最大值

4.结点间关系：结点的子树的根称为该结点的孩子(Child)，相应地，该结点称为孩子的双亲(Parent)。同一个双亲的孩子之间称为兄弟(Sibling)。结点的祖先是从根到该结点所经分支上的所有结点。以某结点为根的子树中的任一结点都称为该结点的子孙。

5.结点的层次(Level)从根开始定义，根为第一层，根的孩子为第二层。双亲在同一层的结点互为堂兄弟。树中结点的最大层次称为树的深度(Depth)或高度

6.如果将树中结点的各子树从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树

7.森林(Forest)是m(m>0)棵互不相交的树的集合

B.树的存储结构

1.双亲表示法

• 假设以一组连续空间存储树的结点，同时在每个结点中，附设一个指示器指示其双亲结点到链表中的位置
• 可扩展双亲域、长子域和右兄弟域等
• 存储结构的设计是一个非常灵活的过程。一个存储结构设计得是否合理，取决于基于该存储结构的运算是否合适、是否方便，时间复杂度好不好等

2.孩子表示法

• 每个结点有多个指针域，其中每个指针指向一个子树的根结点，这种方法叫做多重链表表示法
• 方案一：指针域的个数就等于树的度
• 方案二：每个节点指针域的个数就等于该结点的度
• 孩子表示法：把每个结点的孩子结点排列起来，以单链表作存储结构，则n个结点有n个孩子链表，如果是叶子节点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一给数组中
• 双亲孩子表示法：将双亲法和孩子法结合

3.孩子兄弟表示法：任意一颗树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟

C.二叉树

1.二叉树(Binary Tree) 是n(n>0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成

2.特点：

• 每个结点最多有两棵子树，所以不存在度大于2的结点
• 左子树与右子树是有顺序的，次序不能任意颠倒
• 即使树中某一结点只有一棵子树，也要区分它是左子树还是右子树

3.基本形态：空二叉树、只有一个根结点、根结点只有左子树、根结点只有右子树、根结点既有左子树也有右子树

4.特殊二叉树：

• 斜树：所有的结点都只有左结点的二叉树叫做左斜树。所有结点都只有右结子树的二叉树叫做右斜树。两者统称为斜树。
• 满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。特点：叶子只能出现在最下一层；非叶子结点的度一定是2；同样尝试的二叉树，满二叉树的结点个数最多，叶子最多
• 完全二叉树：对一棵具有n个结点的二叉树按层序编号，如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。
• 完全二叉树的特点：叶子结点只能出现在最下两层；最下层的叶子一定集中在左部连续位置；倒数二层，若有子结点，一定都在右部连续位置；如果节点为为1，则该结点只有左孩子；同样结点数的二叉树，完全二叉数深度小。

D.二叉树的的性质

1.在二叉树的第i层上至多有2i-1个结点(i>=1)

2.尝试为k的二叉树至多有2k-1个结点(k>=1)

3.对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1

4.具有n个结点的完全二叉树的深度为[log2n]+1([x]表示不大于x的最大整数)

5.如果对一棵有n个结点的完全二叉树（其深度为[log2n]+1）的结点按层序编号（从第1层到第[log2n]+1层，每层从左到右），对任一结点i（1<=i<=n）有：

• 如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点[i/2]；
• 如果2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i；
• 如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1；

E.二叉树的存储结构

1.顺序存储结构一般只用于完全二叉树

2.二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域，这种链表称为二叉链表

F.二叉树的遍历

1.二叉树的遍历（traversing binary tree）是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点疲访问一次且仅被访问一次

2.遍历方法：

• 前序遍历：规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。
• 中序遍历：规则是若二叉树为空，则空操作返回，否则从根节点开始（注意不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。
• 后序遍历：规则是若二叉树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。
• 层序遍历：规则是若二叉树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。
• 性质：已知前序和中序，可以确定二叉树；已知中序和后序，可以确定二叉树；已知前序和后序，无法确定二叉树；

G.线索二叉树

1.我们把指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索列表，相应的二叉树就称为线索二叉树（Threaded Binary Tree）

2.其实就是把一棵二叉树转成了一个双向链表，对二叉树以某种次序遍历使其变为线索二叉树的过程就称做是线索化。线索化的过程就是在遍历的过程中修改指针的过程。

3.如果使用的二叉树需要经常遍历或查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构就是非常不错的选择。时间复杂度为O(n)。

H.树、森林与二叉树的转换

1.树转换为二叉树：

• 加线。在所有兄弟结点之间增加一条连线。
• 去线。对树中的每个结点，只保留它与第一个孩子结点之间的连线，删除它与其他孩子结点之间的连线。
• 层次调整。以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之层次分明。注意第一个孩子是二叉树结点的左孩子，兄弟转换过来的孩子是结点的右孩子。

2.森林转换为二叉树

• 把每个树转换为二叉树
• 第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线连接起来。当所有的二叉树连接起来后就得到了由森林转换来的二叉树

3.二叉树转为树

• 加线。若某结点的左孩子结点存在，则将这个左孩子的右孩子结点、右孩子的左孩子结点、右孩子的右孩子的右孩子的……，就是左孩子的右孩子N个右孩子结点都作为此结点的孩子。将该结点与这些中孩子结点用线连接起来。
• 去线。删除原二叉树中所有结点与其右孩子结点的连线。
• 层次调整。使之结构层次分明。

4.二叉树转换为森林：判断根结点有没有右孩子

• 从根结点开始，若右孩子存在，则把与右孩子结点的边线删除，再查看分离后的二叉树，若右孩子存在，则边线删除……，直到所有右孩子连线都删除为止，得到分享的二叉树。
• 再将每棵分离后的二叉树转换为树即可。

5.树的遍历

• 先根遍历树，先访问树的根结点，然后依次先根遍历根的每棵子树
• 后根遍历树，即先依次后根遍历每棵子树，然后再访问根结点。

6.森林的遍历

• 前序遍历，先访问森林中第一棵树的根结点，然后再依次先根遍历根的每棵子树，再依次用同样方式遍历除去第一棵树的剩余树构成的森林
• 后序遍历，先访问森林中第一棵树，后根遍历的方式遍历每棵子树，然后再访问根结点，再依次同样方式遍历除去第一棵树的剩余树构成的森林

I.赫夫曼树及其应用

1.从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称为路径长度。树的路径长度就是从树根到每一结点的路径长度之和。

2.赫夫曼算法描述

• 根据给定的n个权值{w1,w2,w3……wn}构成n棵二叉树的集合F={T1,T2,……Tn}，其中每棵二叉树Ti中只有一个带权为wi根结点，其左右子树均为空
• 在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和
• 在F中删除这两棵树，同时将新得到的二叉树加入F中
• 重复步骤2和3，直到F只含一棵树为止。这棵树便是赫夫曼树。

3.若要设计长短不等的编码，则必须是任一字符的编码都不是另一个字符编码的前缀，这种编码称为前缀编码。

4.赫夫曼编码：设需要编码的字符集为{d1,d2……dn}，各个字符在电文中出现的次数或频率集合为{w1,w2……wn}，以d1,d2……dn作为叶子节点，以w1,w2,……wn作为相应叶子结点的权值来构造一棵赫夫曼树。规定赫夫曼树的左分支代表0，右分支代表1，则从根结点到叶子节点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码，就是就赫夫曼编码

https://github.com/zhangyue0503/cproject/blob/master/shujujiegou/6.c

七、图

A.图的定义

1.图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

2.注意：

• 图中元素称为顶点（Vertex）
• 线性表中可以没有元素称为空表，树中可以没有结点叫做空树，图结构中不允许没有顶点
• 图中任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示

3.各种图定义

• 无向边：若顶点vi到vj之间的边没有方向，则称这条边为元向边（Edge），用无向序偶对（vi,vj）来表示。如果图中任意两个顶点之间的边都是无向边，则称该图为无向图（Undirected grpahs）
• 有向边：若从顶点vi到vj的边有方向，则称这条边为有向边，也称为弧（Arc）。用有序偶<vi,vj>来表示，vi称为弧尾（Tail），vj称为弧头（Head）。如果图中任意两个顶点之间的边都是有向边，则该图称为有向图（Directed grpahs）
• *无向边用小括号表示，有向边用尖括号表示
• 在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图
• 在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。含有n个顶点的无向完全图有n*(n-1)/2条边。
• 在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。含有n个顶点的有向完全图有n*(n-1)条边
• 有很少条边或弧的图称为稀疏图，反之称为稠密图
• 有些图的边或弧具有与它相关的数字，这种与图的边或者弧相关的数叫做权（Weight）。这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图统称为网（Network）。
• 假设有两上图G=(V,{E})和G’=(V’,{E’})，如果V’包含于V且E’包含于E,则称G’为G的子图（Subgraph）

4.图的顶点与边间关系

• 对于无向图G=(V,{E})，如果边(vi,vj)属于E，则称顶点v和v’互为邻接点(Adjacent)，即v和v’相邻接。边(vi,vj)依附(incident)于顶点v和v’，或者说(v,v’)与顶点v和v’相关联。顶点v的度（Degree）是和v相关联的边的数目
• 对于有向图G=(V,{E})，如果弧<vi,vj>属于E，则称顶点v连接到顶点v。弧<v,v’>和顶点v,v’相关联。以顶点v为头的弧的数目称为v的入度（InDegree），记为ID（v）；以v为尾的弧的数目称为v的出度（OutDegree），记为OD(v)；顶点v的度为TD(v)=ID(v)+OD(v)
• 无向图G=(V,{E})中从顶点v到顶点v’的路径（path）是一个顶点序列（v=vi,0，vi,1，……，vi,m），其中vi,j-1属于E，1<=j<=m
• 路径的长度是路径上边或弧的数目
• 第一个顶点到最后一个顶点相同的路径称为回路或环（Cycle）。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路，称为简单回路或简单环。

5.连通图相关术语

• 在无向图G中，如果从顶点v到顶点v’有路径，则称v和v’是连通的。如果对于图中任意两个顶点vi,vj属于E，vi和vj都是连通的，则称G是连通图（Connected Graph）
• 无向图中的极大连通子图称为连通分量，强调：要是子图；子图要是连通的；连通子图含有极大顶点数；具有极大顶点数的连通子图包含依附于这些顶点的所有边
• 在有向图G中，如果对于每一对vi,vj属性V，vi!=vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。有向图中的极大强连通子图称做有向图的强连通分量
• 一个连通图的生成树是一个极小的连通子图，它含有图中全部的n个顶点，但只有足以构成一棵树的n-1条边
• 如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一棵有向树。一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧

B.图的存储结构

1.邻接矩阵：图的邻接矩阵（Adjacency Matrix）存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。

2.邻接表：将结点存入数组，并对结点的孩子进行存储，这种数组与链表相结合的存储方法称为邻接链表。

• 图中顶点用一个一维数组存储，每个数据元素还要存储指向第一个邻接点的指针
• 图中每个顶点vi的所有邻接点构成一个线性表，使用单链表存储，无向图称为顶点vi的边表，有向图则称为顶点vi作为弧尾的出边表
• 对于有向图，可以建立一个有向图的逆邻接表，即对每个顶点vi都建立一个链接为vi为弧头的表
• 对于带权值的网图，可以在边界结点定义中再增加一个weight的数据域，存储仅值信息

3.十字链表：将邻接表和逆邻接表结合在一起使用，在有向图的应用中，是非常好的数据结构模型

4.邻接多重表：与邻接表的差别，仅仅是在于同一条边在邻接表中用两个结点表示

5.边靠数组：由两个一维数组构成。一个是存储顶点的信息；另一个是存储边的信息，这个边数组每个数据元素由一条边的起点下标、终点下标和权组成

C.图的遍历

1.图的遍历和树的遍历类似，从图中某一顶点出发访遍图中其余观点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历（Traversing Graph）

2.尝试优先遍历（Depth_First_Search），也称为尝试优先搜索，简称GFS。

• 从图中的某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径想通的顶点都被访问到。
• 若图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起始点，重复上述过程，直至图中所有访问点都被访问到为止。
• 例如从顶点开始一路访问右结点，递归遍历右结点完成后访问左结点，类似树的遍历

3.广度优先遍历（Breadth_First_Search）：又称广度优先搜索，又称BFS。类似于树的层序遍历。

• 与深度优先遍历在时间复杂度上是一样的
• 深度优先更适合目标比较明确 ，以找到目标为主要目的的情况，而广度优先更适合在不断扩大遍历范围时找到相对最优解的情况

D.最小生成树

1.把构造连通网的最小代价生成树称为最小生成树（Minimum Cost Spanning Tree）

2.普里姆（Prim）算法

• 假设N=(P,{E})是连通网，TE是N上最小生成树中边的集合。算法从U={u0}(u0∈V)，TE={}开始。重复执行下述 操作：在所有u∈U,v∈V-U的边(u,v)∈E中找一条代价最小的边(u0,v0)并入集合TE，同时v0并入U，直至U=V为止。此时TE中必有n-1条边，则T=(V,{TE})为N的最小生成树

3.克鲁斯卡尔（Kruskal）算法

• 假设N=(V,{E})是连通网，则令最小生成树的初始状态为只有n个顶点而无边的非连通图T={V,{}}，图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通仅是上，则将此边加入到T中，否则会去此边而选择下一条代价最小的边。依次类推，直至T中所有顶点都在同一连通分量上为止

4.克鲁斯卡尔算法主要是针对边来展开，边数少时效率会非常高，所以对于稀疏图有很大的优势；而普里姆算法对于稠密图，即边数非常多的情况会更好一些

E.最短路径

1.对于网图来说，最短路径，是指两顶点之间经过的边上权值之和最少的路径，并且我们称路径上的第一个顶点是源点，最后一个顶点是终点

2.迪杰斯特拉（Dijkstra）算法

并不是一下就求出v1到vn的最短路径，而是一步步求出它们之间顶点的最短路径，过程中都是基于已经求出的最短路径的基础上，求得最远顶点的最短路径，最终得到结果

解决了从某个源点到其余各顶点的最短路径问题，时间复杂度为O(n^3)

3.费洛伊德（Floyd）算法

公式：D0[v][w]=min{D-1[v][w],D-1[v][0]+D-1[0][w]}

代码简洁，一个二重循环初始化加一个三重循环权值修正，时间复杂度也是O(n^3)，如果面临需要求所有顶点至所有顶点的最短路径问题时，弗洛伊德（Floyd）算法应该是不错的选择

F.拓扑排序

1.在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称为AOC网（Activity On Vertex Network）

2.设G=(V,E)是一个具有n个顶点的有向图，V中的顶点序列v1……vn，满足若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在顶点vj之前。则我们称这样的顶点序列为一个拓扑序列

3.所谓拓扑排序，其实就是对一个有向图构造拓扑序列的过程

4.基本思路：从AOV网中选择一个入度为0的顶点输出，然后删去此顶点，并删除以此顶点为尾的弧，继续重复此步骤，走到输出全部顶点或者AOV网中不存在入度为0的顶点为止

5.整个算法的时间复杂度为O(n+e)

G.关键路径

1.在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网，我们称之为AOE网（Activity On Edge Network）

2.路径上各个活动所持续的时间之和称为路径长度，从源点到汇点具有最大长度的路径叫关键路径，在关键路径上的活动叫关键活动

3.算法原理：只需要找到所有活动的最早开始时间和最晚开始时间，并且比较它们 ，如果相等就意味着此活动是关键活动，活动间的路径为关键路径，几个参数：

事件的最早发生时间etv（earliest time of vertex）：即顶点vk的最早发生时间

事件的最晚发生暖意ltv（latest time of vertex）：即顶点vk的最晚发生时间，也就是每个顶点对应的事件最晚需要开始的时间，超出此时间将会延误整个工期

活动的最早开工时间ete（earliest time of edge）：即弧ak的最早发生时间

活动的最晚开工时间lte（latest time of edge）：即弧ak的最晚发生时间，也就是不推迟工期的最晚开工时间

https://github.com/zhangyue0503/cproject/blob/master/shujujiegou/7.c

八、查找

A.查找概论

1.查找表（Search Table）是由同一类型的数据元素（或记录）构成的集合

2.关键字（Key）是数据元素中某个数据项的值，用它可以标识一个数据元素。也可以标识一个记录的某个数据项（字段），我们称为关键码。若此关键字可以唯一地标识一个记录，则称此关键字为为主关键字（Primary Key）。对于那些可以识别多个数据元素（或记录）的关键字，称为次关键字（Secondary Key）

3.查找（Searching）就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。

4.静态查找表（Static Search Table）：只查找操作的查找表。操作有：

• 查询某个“特定的”数据元素是否在查找表中
• 检索某个“特定的”数据元素和各种属性

5.动态查找表（Dynamic Search Table）：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。操作有：

• 查找时插入数据元素
• 查找时删除数据元素

B.顺序表查找

1.顺序查找（Sequential Search）又叫线性查找，是最基本的查找技术，它的查找过程是：从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果直到最后一个（或第一个）记录，其关键字和给定值比较都不相等时，则表中没有所查的记录，查找不成功

2. 时间复杂度：O(n)

C.有序表查找

1.折半查找（Binary Search）技术，又称为二分查找。它的前提是线性表中的记录必须是关键码有序（通常从小到大有序），线性表必须采用顺序存储。折半查找的基本思想是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。时间复杂度O(logn)

2.插值查找（Interpolation Search）是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法，其核心就在于插值的计算公式key-a[low]/a[high]-a[low]。

3.斐波那契查找：如果要查找的记录在左侧，则左侧的数据都不用再判断了，不断反复进行下去，对处于当中的大部分数据，其工作效率要高一些，折半查找是进行加法与除法运算，插值查找 进行按照那样的四则运算，而斐波那契查找只是最简单加减法运算。核心在于：

• 当key=a[mid]时，查找就成功
• 当k<a[mid]时，新范围是low个到第mid-1个，此时范围个数为F[k-1]-1个
• 当key<a[mid]时，新范围是m+1个到第high个，此时范围个数为F[k-2]-1

D.线性索引查找

1.索引就是把一个关键字与它对应的记录相关联的过程。所谓线性索引就是将索引项集合组织为线性结构，也称为索引表。

2.稠密索引：是指在线性索引中，将数据集中的每个记录对应一个索引项。对于稠密索引这个索引用来说，索引项一定是按照关键码有序的排列

3.分块索引：

• 分块有序，是把数据集的记录分成了若干块，并且这些块需要满足两个条件：块内无序，即每一块内的记录不要求有序；块间有序；
• 定义的分块索引的索引项结构分三个数据项：最大关键码；块中的记录个数；用于指向块首数据元素的指针；
• 分块索引表中查找分两步：在分块索引表中查找要查关键字所在的块；根据块首指针找到相应的块，并在块中顺序查找关键码。

4.倒排索引：

• 索引项的通用结构是：次关键码；记录号表；
• 其中记录号表存储具有相同次关键字的所有记录的记录号（可以是指向记录的指针或者是该记录的主关键字）。这样的索引方法就是倒排索引（inverted index）。

E.二叉排序树

1.二叉排序树（Binary Sort Tree），又称为二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树。

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结构的值；
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 它的左、右子树也分别为二叉排序树

F.平衡二叉树（AVL树）

1.平衡二叉树（Self-Balancing Binary Search Tree或Height-Balanced Binary Search Tree），是一种二叉排序树，其中每一个节点的左子树和左子树的高度差至多等于1.

2.我们将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF（Balance Factor），平衡二叉树上所有结点的平衡因子只可能是-1，0和1.

3.距离插入结点最近的，且平衡因子的绝对值大于1的结点为根的子树，我们称为最小不平衡子树

4.实现原理：在构建二叉排序树的过程中，每当插入一个结点时，先检查是否因插入而破坏了树的平衡性，若是，则找出最小不平衡子树。在保持二叉排序树特性的前提下，调整最不不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。当最小不平衡子树根结点的平衡因子BF是大于1时，就右旋，小于-1时就左旋。插入结点后，最小不平衡子树的BF与它的子树的BF符号相反时，就需要对结点先进行一次旋转以使得符号相同后，再反向旋转一次才能够完成平衡操作。

G.多路查找树（B树）

1.多路查找 树（muitl-ray search tree），其每一个结点的孩子数可以多于两个，且每一个结点处可以存储多个元素

2.2-3树：其中的每一个结点都具有两个孩子（我们称它为2结点）或三个孩子（我们称它为3结点）

• 一个2结点包含一个元素和两个孩子（或没有孩子），且与二叉排序树类似，但这2结点要么没孩子，要么就有2个
• 一个3结点包含一小一大两个元素和三个孩子（或没有孩子）

3.2-3-4树：其实就是2-3树的概念扩展，包括了4结点的使用。一个4结点包含小中磊三个元素和四个孩子（或没有孩子），一个4结点要么没孩子，要么有4个孩子

4.B树（B-tree）：是一种平衡的多路查找树。2-3树和2-3-4树都是B树的特例。结点最大的孩子数目称为B树的阶（order）。一个m阶的B树具有如下属性：

• 如果要结点不是叶结点，则至少有两棵子树
• 每一个非根的分支结点都有k-1个元素和k个孩子，其中[m/2]<=k<=m。每一个叶子结点n都有k-1个元素，其中[m/2]<=k<=m
• 所有叶子结点都位于同一层次
• 所有分支结点包含下列信息数据（n,A0,K1,A1,K2,A2……Kn,An），其中：Ki(i=1,2……,n)为关键字，且Ki<Ki+1(i=1,2……,n);Ai(i=0,2,……,n)为指向子树根结点的指针，且指针Ai-1所指子树中所有结点的关键字均小于Ki，An所指子树中所有结点的关键字均大于Kn，n([m/2]-1<=n<=m-1)为关键字的个数（或n+1为子树的个数）

5.B+树，在B树中，每一个元素在该树中只出现一次，有可能在叶子结点上，也有可能在分支结点上。而在B+树中，出现在分支结点中的元素会被当作它们在该分支结点位置的中序后继者（叶子结点）中再次列出。另外，每一个叶子结点都会保存一个指向后一路子结点的指针。一棵m阶的B+树和m阶的B树的差异在于：

• 有n棵子树的结点中包含有n个关键字
• 所有的叶子结点包含全部关键字的信息，及指向含这些关键字记录的指针，叶子结点本身依关键字的大小自小而大顺序链接
• 所有分支结点可以看成是索引，结点中仅含有其子树中的最大（或最小）关键字

H.散列表查找（哈希表）概述

1.散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key)，f称为散列函数，又称为哈希（Hash）函数。采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表（Hash table）

2.散列技术既是一种存储方法，也是一种查找方法。最适合的求解问题是查找与给定值相等的记录。

3.散列技术不适合多同样关键字或范围查找

4.两个关键字key1!=key2，但是却有f(key1)==f(key2)，这种现象称为冲突（collision），并把key1和key2称为这个散列函数的同义词（synonym）

I.散列函数的构造方法

1.好的散列函数：计算简单、散列地址分布均匀

2.直接定址法：f(key)=a*key+b（a,b为常数），适合查找表较小且连续的情况

3.数字分析法：制取使用关键字的一部分来计算散列存储位置的方法，适合处理关键字位数比较大的情况，且事先知道关键字的分布且关键字的若干位分布较均匀

4.平方取中法：适合不知道关键字的分布，而位数又不是很大的情况

5.折叠法：将关键字从左到右分割成位数相等的几部分（注意最后一部分位数不够时可以短些），然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。事先不需要知道关键字的分布，适合关键字位数较多的情况。

6.除留余数法：f(key) = key mod p(p<=m)，最常用的，若散列表表长为m，通常p为小于或等于表长（最好接近m）的最小质数或不包含小于20质因子的合数

7.随机数法：f(key) = random(key)

J.处理散列冲突的方法

1.开放定址法：就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。fi(key) = (f(key)+di) MOD m (di=1,2,3……,m-1)

• 二次探测法，增加平方运算为了不让关键字都聚集在某一块区域：fi(key) = (f(key)+di) MOD m (di=1^1,-1^1,2^2,-2^2……,q^1,-q^q,q<=m/2)
• 随机探测法：fi(key) = (f(key)+di) MOD m (di是一个随机数列)

2.再散列函数法：fi(key) = RHi(key) (I=1,2,……,k)

3.链地址法：将所有关键字为同义词的记录存储在一个单链表中，称这种表为同义词子表，在散列表中只存储所有同义词子表的头指针。

4.公共溢出区法：为所有冲突的关键字建立一个公共的溢出区来存放

K.散列表查找实现

1.散列查找的平均查找长度取决于：

• 散列防水涂料旭否均匀
• 处理冲突的方法
• 散列表的装填因子

https://github.com/zhangyue0503/cproject/blob/master/shujujiegou/8.c

九、排序

A.排序的基本概念与分类

1.假设含有n个记录的序列为{r1,r2……,rn}，其相应的关键字分别为{k1,k2,……,kn}，需确定1，2，……，n的一种排列p1,p2,……,pn，使其相应的关键字满足kp1<=kp2<=……<=kpn（非递减或非递增）关系，即使得序列成为一个按关键字有序的序列{rp1,rp2,……,rpn}，这样的操作就称为排序

2.排序的稳定性：假设ki=kj（1<=i<=n,1<=j<=n,i!=j），且在排序前的序列中ri领先于rj（即i<j）。如果排序后ri仍依靠于rj，则称所用的排序方法是稳定的；反之，若可能使得排序后的序列中rj领先ri，则称所用的排序方法是不稳定的。

3.外排序：是由于排序的记录个数太多，不能同时放置在内存，整个排序过程需要在内外存之间多次交换数据才能进行。

4.内排序：是在排序整个过程中，待排序的所有记录全部被放置在内存中。

• 性能受三方面影响：时间性能、辅助空间、算法的复杂性
• 内排序分为：插入排序、交换排序、选择排序和归并排序
• 按算法复杂度：简单算法（冒泡排序、简单选择排序、直接插入排序）、改进算法（希尔排序、堆排序、归并排序、快速排序）

B.冒泡排序

1.冒泡排序（Bubble Sort）一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。

C.简单选择排序

1.简单选择排序法（Simple Selection Sort）就是通过n-i关键字间的比较，从n-i+1个记录中先出关键字最小的记录，并和第i（1<=i<=n）个记录交换之

D.直接插入排序算法

1.直接插入排序（Straight Insertion Sort）的基本操作是将一个记录插入到已经排好的有序列表中，从而得到一个新的、记录数增1的有序表

E.希尔排序

1.将大量记录数的记录进行分组。分割成若干个子序列，在这些子序列内分别进行直接插入排序，当整个序列基本有序时，注意只是基本有序时，再对全体记录进行一次直接插入排序

2.所谓基本有序，就是小的关键字基本在前面，大的基本在后面，不大不小的基本在中间

3.跳跃分割：将相距某个“增量”的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序

F.堆排序

1.堆是具有下列性质的完全二叉树：每个结点都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆

2.堆排序（Heap Sort）将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次小值。如此反复执行，便能得到一个有序序列。

G.归并排序

1.归并排序（Merging Sort）假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到[n/2]（[x]表示不小于x的最小整数）个长度为2或1的有序子序列；两款两两归并，……，如此重复，直至得到一个长度为n的有序序列为止，这种排序方法称为2路归并排序

H.快速排序

1.快速排序（Quick Sort）的基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的

https://github.com/zhangyue0503/cproject/blob/master/shujujiegou/9.c