树
一、 基本概念
树：是一种递归定义的数据结构。树(Tree)是树结构的简称，它是一种重要的非线性数据结构。树或者是一个空树，即不含有任何的结点(元素)，或者是一个非空树，即至少含有一个结点。
根：在一棵非空树中，它有且仅有一个根节点。
子树：在一棵非空树中，除根外其余所有结点分属于 m 个(m≥0)不相交的集合。每个集合又构成一棵树，称为根结点的子树。
结点(node)：表示树中的元素，包括数据项及若干指向其子树的分支。
结点的度(degree)：树中的一个结点拥有的子树数称为该结点的度 (Degree)。
叶子(leaf)：度为 0 的结点。
孩子(child)：结点子树的根称为该结点的孩子。
双亲(parents)：孩子结点的上层结点叫该结点的。
兄弟(sibling)：同一双亲的孩子。
树的度：一棵树中最大的结点度数。
结点的层次(level)：从根结点算起，根为第一层，它的孩子为第二层……。
深度(depth)：树中结点的最大层次数。
有序树：子树的位置自左向右有次序关系的称为有序树，顺序决定了大小，孩子的次序不能改变。
无序树：子树的位置自左向右无次序关系的称为无序树。
森林(Forest)：是 m(m≥0) 棵互不相交的树的集合。树和森林的概念相近。删去一棵树的根，就得到一个森林；反之，加上一个结点作树根，森林就变为一棵树。
路径：若树中存在一个结点序列 k1 ， k2 ， … ， ki ，使得 ki 是 ki+1 的双亲 (1≤i<j) ，则称该结点序列是从 k1 到 kj 的一条路径 (Path) 或道路。
路径的长度：指路径所经过的边 ( 即连接两个结点的线段 ) 的数目，等于 j-1 。
祖先：若树中结点 k 到 ks 存在一条路径，则称 k 是 ks 的 祖先 (Ancestor) ， ks 是 k 的 子孙 (Descendant) 。结点 k 的祖先和子孙不包含结点 k 本身。
结点的层数：(Level)从根起算，根的层数为1，其余结点的层数等于其双亲结点的层数加1。双亲在同一层的结点互为堂兄弟。树中结点的最大层数称为树的高度(Height)或深度(Depth)。很多文献中将树根的层数定义为 0 。
二、树的其他特性
1.数的递归定义：
树(Tree)是 n(n≥0) 个结点的有限集 T ， T 为空时称为空树，否则它满足如下两个条件：
(1) 有且仅有一个特定的称为根 (Root) 的结点；
(2) 其余的结点可分为 m(m≥0) 个互不相交的子集 Tl,T2,…,Tm ，其中每个子集本身又是一棵树，并称其为根的子树(Subree) 。
注意：树的递归定义刻画了树的固有特性：一棵非空树是由若干棵子树构成的，而子树又可由若干棵更小的子树构成。
2.树的表示：
树形图表示是树结构的主要表示方法。其他还有广义表、集合图、凹入图三种表示形式。
3.线性结构和树型结构之间的区别：
|
|
线性结构
|
树型结构
|
|
起点
|
第一个数据元素
(
无前驱
)
|
根结点
(
无前驱
)
|
|
终点
|
最后一个数据元素
(
无后继
)
|
多个叶子结点
(
无后继
)
|
|
中间
|
其它数据元素(一个前驱、一个后继)
|
其它数据元素(一个前驱、多个后继)
|
4.树形结构的逻辑特征：
树形结构的逻辑特征可用树中结点之间的父子关系来描述：
(1) 树中任一结点都可以有零个或多个直接后继 (即孩子) 结点，但至多只能有一个直接前趋 (即双亲) 结点。
(2) 树中只有根结点无前趋，它是开始结点；叶结点无后继，它们是终端结点。
(3) 祖先与子孙的关系是对父子关系的延拓，它定义了树中结点之间的纵向次序。
(4) 有序树中，同一组兄弟结点从左到右有长幼之分。
对这一关系加以延拓，规定若 k1 和 k2 是兄弟，且 k1 在 k2 的左边，则 k1 的任一子孙都在 k2 的任一子孙的左边，那么就定义了树中结点之间的横向次序。
三、二叉树的概念
二叉树：指度为 2 的有序树。是最简单的一种树结构，在计算机领域有着广泛的应用。
二叉树的递归定义：二叉树或者是一棵空树，或者是一棵由一个根结点和两棵互不相交的分别称根的左子树和右子树所组成的非空树，左子树和右子树又同样都是一棵二叉树。
二叉树的孩子：二叉树中，每个结点的左子树的根结点被称为该结点的 左孩子 (left child) , 右子树的根结点被称为 右孩子(left child)。
满二叉树：深度为 K 且含有 2K -1 个结点的二叉树，当树中的每一层都满时成为漫二叉树。
完全二叉树：在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者在最右边缺少连续若干个结点，则称此树为完全二叉树。
小根堆： 是具有如下特征的一棵完全二叉树。
(1)若树根接点存在左孩子，则根接点的值(或某个域的值)小于等于左孩子节点的值(或某个域的值)；
(2)若树根接点存在右孩子，则根接点的值(或某个域的值)小于等于右孩子接点的值(或某个域的值)；
(3)以左、右孩子未跟的子树又各是一个堆。
大根堆：定义与上述类似，只要把小于等于改为大于等于就可。
二叉排序树(Binary Sort Tree)：又称二叉查找(搜索)树(Binary Search Tree)。
其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树：
(1)若它的左子树非空，则左子树上所有结点的值均小于根结点的值；
(2)若它的右子树非空，则右子树上所有结点的值均大于根结点的值；
(2)左、右子树本身又各是一棵二叉排序树。
注：以上的数据结构均比较容易理解，不再画图举例。
四、一些有关树的计算题
1、一个具有767个结点的完全二叉树，其叶子结点的个数为多少个？
因为是完全二叉树，所以只可能有0个或1个度为1的结点，其余叶子结点度为0，其他结点度为2。
又因为结点总数为奇数，所以不存在度为1的结点(除根外都是成对出现)。
设叶子结点有n0个，其余结点n2个，则n=n0+n2
又根据树的边数定义，总共有n-1条边，则n2*2=n-1
所以n2=(n-1)/2=383
n0=767-383=384
2、一棵哈夫曼树共有9个顶点，则其叶子结点的个数为多少个？
哈夫曼树一定不存在度为1的结点，所以设叶子结点有n0个，其余结点n2个
则n=n0+n2
又根据树的边数定义，总共有n-1条边，则n2*2=n-1
所以n2=(n-1)/2=4
n0=9-4=5
3、在一棵度为3的树中，有2个度为3的结点，有1个度为2的结点，则有几个度为0的结点？
设有n1个度为1的结点，n0个度为0的结点，则：
点数公式：n=2+1+n1+n0
边数公式：n-1=2*3+1*2+n1*1
则下式减上式得到n0=6
***************************************************************************************************
图
一、图的基本定义
图：是一种复杂的非线性数据结构。
图的二元组定义：
图 G 由两个集合 V 和 E 组成，记为：
G=(V,E)
其中：
V 是顶点的有穷非空集合，
E 是 V 中顶点偶对(称为边)的有穷集。
通常，也将图 G 的顶点集和边集分别记为 V(G) 和 E(G) 。 E(G) 可以是空集。若 E(G) 为空，则图 G 只有顶点而没有边。
有向图：若图 G 中的每条边都是有方向的，则称 G 为有向图 (Digraph)。
无向图：若图 G 中的每条边都是没有方向的，则称 G 为无向图 (Undigraph)。
混合图：既有有向边，也有无向边的图
完全图：若无向图中的每个顶点之间存在着一条边，有向图中的每两个定点之间都存在着方向相反的两条边，则称此图为完全图。
注：无向完全图n个顶点会有n(n-1)/2个顶点。
稠密图：当一个图接近完全图时，则称它为稠密图。
稀疏图：当一个图含有较少的边数，即 e << n(n-1)时，则称它为稀疏图。
二、其他图的定义
平凡图：仅有一个结点的图。
零图：边集为空集的图，即仅有结点的图。
自回路(环)：关联于同一个结点的边。
无向平行边：联结相同两个结点的多于1条的无向边。
有向平行边：联结两个结点之间的多于1条且方向相同的有向边。
简单图：不含平行边和自回路的图。
度：
1. 在无向图G＝<V,E>中，与结点v关联的边数，即为结点度数deg(v)或d(v)。
2. 在有向图中，结点v的出度和入度之和为度数。
3. 在有向图D＝<V,E>中，以v为起点的边之条数为出度deg+(v)；以v为终点的边之条数为入度deg-(v)。
路径长度：是指路径上边或弧的数目。
回路：若路径的第一个顶点和最后一个顶点相同，则这条路径是一条回路。
简单路径：若路径中顶点没有重复出现，则称这条路径为简单路径。
连通图：在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。如果图中任意两个顶点之间都连通，则称该图为连通图，否则，将其中的极大连通子图称为连通分量。在有向图中，如果对于每一对顶点vi和vj，从vi到vj和从vj到vi都有路径，则称该图为强连通图；否则，将其中的极大连通子图称为强连通分量。
欧拉通路(回路)：通过图G的每条边一次且仅一次，而且走遍每个结点的通路(回路)，就是欧拉通路(回路)。
欧拉图：存在欧拉回路的图就是欧拉图。欧拉回路要求边不能重复，结点可以重复。笔不离开纸，不重复地走完所有的边且走过所有结点，就是所谓的一笔画。
哈密尔顿轨：含有图中所有顶点的轨称作哈密尔顿轨。
哈密尔顿环：闭合的哈密尔顿轨称作哈密尔顿环。
哈密尔顿图：含有哈密尔顿环的图称作哈密尔顿图。即周游世界问题。
三、图与树的关系
图的生成树：对于一个拥有n个顶点的无向连通图，它的边数一定多余n-1条。若从中选择n-1条边，使得无向图仍然连通，则由n个顶点及这 n-1条边(弧)组成的图被称为原无向图的生成树。显示了一个无向连通图的生成树，双线圈表示的顶点为生成树的根结点。
森林：对于一个图G，可以将其所有边和顶点划分成若干个树，则称此图为一个森林。(自己写的...)
最小生成树：在一个图中，每条边或弧可以拥有一个与之相关的数值，我们将它称为权。这些权可以具有一定的含义，比如，表示一个顶点到达另一个顶点的距离、所花费的时间、线路的造价等等。这种带权的图通常被称作网。通常我们将权值总和最小的生成树称为最小生成树。
注：图或网的生成树不是唯一的，从不同的顶点出发可以生成不同的生成树，但n个结点的生成树一定有n-1条边
例：若一个具有n个结点、k条边的非联通无向图是一个森林(n>k)，则该森林中必有 n
-k 棵树.
原因是假设有s棵树，则每棵树的边和顶点对应关系分别是ki=ni-1
所以 k=k1+k2+...+ks=(n1-1
)+(n2-1)+...+(ns-1)=n-s
所以 s = n-k
三、图的简单判断
(b)是非简单图，(a)是完全图，(a)和(b)都是哈密尔顿图，其中(a)又是欧拉图，(d)是树。
***************************************************************************************************
-The End-