转上一节：
http://t.csdnimg.cn/rDYno
http://t.csdnimg.cn/rDYno
5.3：树
考点1:二叉树的存储与特性
1：树与二叉树的概念
结点(圆形)
分支(结点下面的线)
结点的度:该结点的子树数目
树的度:各结点度的最大值
叶子结点:度为0的结点-无分支
分支结点(非终端结点) :度不为0的结点-有分支
内部结点:除根以外的分支结点
层次:根为第1层，以此类推
树的高度: -棵树的最大层次数-总层数
父结点子结点兄弟结点
2．二叉树的定义
二叉树是n(n≥0）个结点的有限集合，它或者是空树（n=0)，或者是由1个根结点及两棵不相交的
且分别称为左、右子树的二叉树所构成。可见，二叉树同样具有递归性质。
空树：没有结点的树。
单结点树：就只有一个顶点结点。
二叉树：所有结点的度不大于2的树。
满二叉树：任意结点，度为0或2 (除最后-层以外， 所有结点的度都为2)
3.二叉树的存储
顺序存储
错误示例：
方式一：采用大小为8的数组。
缺点：没有存位置信息，无法还原，摒弃。
正确示例:
方式二：采用大小为15的数组，
特点：可以还原，有大量空间浪费。
链式存储
4.二叉树的特性
在二叉树的第i层上最多有个结点(i>=1) ;
深度为k的二叉树最多有个结点(k>=1) ;
如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到Llog2n+1」层，每层从左到
右），则对任一结点i(1<=i<=n)，有：
如果i=1，则结点i无父结点，是二叉树的根；
如果i>1，则父结点是Li/2」;
如果2i>n，则结点i为叶子结点，无左子结点；否则，其左子结点是结点2i;
如果2i+1>n，则结点i无右子结点，否则，其右子结点是结点2i+1。
思考：下图中各个结点的编号为多少？
对任何-棵=叉树，如果其叶子结点数为n0,度为2的结点数为n2，则no=n2+1。
假设:
( i无内容可翻译
度为0的结点数，记作；
度为1的结点数，记作；
度为2的结点数，记作;
......
度为k的结点数，记作；
(1) 一棵树，从根向叶子伸展
根据度的定义：度为K的结点个数记为nk,则每个结点会伸展出k个枝丫。
(2) 一棵树，从叶子向根回溯。
根据父子关系:每个结点都会通过1根枝丫与其父结点连接，除了根结点。
原理:分支数=结点总数-1
由(1) 可得枝丫数为:
由(2) 可得枝丫数为:结点总数-1=
=
二叉树：,化简后
具有N个结点的二叉树形态数：
原理：拿出1个结点做根，剩余结点分成2组，在左右两侧分布排列。
(1) 0个结点的二叉树形态
1种：空树
(2) 1个结点的二叉树形态
1种：单结点树
(3) 2个结点的二叉树形态
2种：
(4) 3个结点的二叉树形态
1*2+1*1+2*1=5种
(5) 4个结点、5个结点....个结点
考点2:二叉树的遍历
1.二叉树遍历
(1)层次遍历(行遍历) (从上至下，从左至右)
(2)前序遍历(根左右) (根结点、左树、右树)
注意:来到子树后，还要按照“根左右“遍历。
(3)中序遍历(左根右) (左树、根结点右树)
(4)后序遍历(左右根) (左树、右树、根结点)
图中层次遍历结果是: 1, 2, 3, 4, 5, 6, 7, 8。
图中前序遍历结果是: 1, 2, 4, 5, 7,8，3, 6。
图中中序遍历结果是: 4, 2, 7, 8, 5，1, 3, 6。
图中后序遍历结果是: 4, 8, 7, 5, 2, 6, 3, 1.
2：反向构造二叉树
由前序序列为ABHFDECG,中序序列为HBEDFAGC构造二叉树。
技巧:前序确定根结点，中序区分左右子树。
反向构造二叉树结果如下：
考点3:特殊的二叉树
1：查找二叉树/二叉排序树
左孩子小于根
右孩子大于根
左孩子<根<右孩子
特点：
(1)二叉查找树的中序遍历序例为从小到大排列的序列。
(2)值最小的结点无左子树，值最大的结点无右子树。
(3)每一层从左到右进行遍历的序列为从小到大排列的序列。
插入结点:从顶部开始找，找到合适位置放置即可
(1)若该键值结点已存在，则不再插入，如: 48;
(2)若查找二叉树为空树，则以新结点为查找二叉树;
(3)要插入结点键值与插入后父结点键值比较，就能确定新结点是父结点的左子结点还是右子结
点。
思考:
例1：{89, 48, 112, 20, 56, 51}构造排序二叉树
序列2：{112, 89，56, 51, 48，20}构造排序二叉树
注意：同样的数据，但是顺序不同，最终组成的二叉排序树可能不-样。
删除结点：删除结点后，要保证剩下的结点还是二叉排序树。
(1）若待删除结点是叶子结点，则直接删除；
(2）若待删除结点只有一个子结点，则将这个子结点与待删除结点的父结点直接连接，如：56
(3）若待删除的结点p有两个子结点，则在其左子树上，用中序遍历寻找关键值最大的结点s，用结
点s的值代替结点p的值，然后删除结点s，结点s必属于上述(1)、(2）情况之一，如89。
思考:先序中序后序例列，哪种遍历结果是有的?
2.最优二叉树(哈夫曼树)
需要了解的基本概念：
叶子结点的路径长度：结点到根的分支线数量
树的路径长度：所有叶子结点路径长度之和
权：叶子结点的数值
叶子结点的带权路径长度：权重*路径
树的带权路径长度(树的代价) ：所有叶子结点带权路径之和
思考：下面这2棵树的代价分别是多少?
我们发现，在叶子结点的数量和权重一样的情况下，
高权重叶子结点离根结点的距离越近(路径长度越短)，整体的带权路径长度就越小。
我们把优化叶子结点后得到的最小带权路径长度的树就叫作最优二叉树，也叫哈夫曼树。
哈夫曼树只有度为0或度为2的结点，没有度为1的结点。
例:假设有一组权值5,29.78.14,23.3,11, 请尝试构造哈夫曼树。
1：找出两个最小权值，构造新结点
加入新结点，去掉老结点。
2：在最新的集合中找两个最小的，继续构造。
加入新结点，去掉老结点。
3：以此类推。
注意:建议养成习惯，左小右大。
5.4：图
考点1：图的定义与存储
1：基本概念
完全图
在无向图中，若每对顶点之间都有一条边相连 ，则称该图为完全图(complete graph)。
在有向图中，若每对顶点之间都有二条有向边相互连接，则称该图为完全图。
连通图
连通图:指任意两个顶点之间都有一个路径相连。(点点都能通)
2：图的存储-邻接矩阵
用一个n阶方阵R来存放图中各结点的关联信息，其矩阵元素Rij定义为：
3：图的存储-邻接表
首先把每个顶点的邻接顶点用链表示出来,然后用- -个维数组来顺序存储上面每个链的头指针。
考点2：图的遍历
考点3:拓扑排序
在有向图中，若顶点表示活动，用有向边表示活动之间的优先关系(先后关系)， 则称这样的有向图
为活动图， 简称AOV网。
按照箭头方向把有向图的结点连起来就会形成一个序列。
如果该序列没有违反途中结点的先后顺序，就叫作lop序列，也就是先后序列。
上图的拓扑序列有: 02143567, 01243657, 02143657, 01243567。
考点4：最小生成树与最短路径问题
最小生成树问题
克鲁斯-卡尔算法:找最短的边，直到把所有点连起来。注意:不能形成闭环。
普里姆算法:从某个研始，找现有点集合中最短的边。注意:不能形成闭环。
最短路径问题
迪杰斯特拉算法：每次只考虑从上一层结点到当前结点的最短路径。
思考：迪杰斯特拉算法采用的算法设计策略是?上图A-E最短路径为多少?
