树和二叉树

谁借莪１个温暖的怀抱￠ 2023-10-05 14:41 33阅读 0赞

### 树和二叉树 ###

*  一、基本术语
 *  二、性质
 *  三、前/中/后序遍历
 *  四、霍夫曼树（满二叉树）
 *  五、图的遍历

# 一、基本术语 #

1.  树结点：包含一个数据元素及若干指向子树的分支；
2.  孩子结点：结点的子树的根称为该结点的孩子；
3.  双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲；
4.  兄弟结点：同一双亲的孩子结点；
5.  堂兄结点：同一层上结点；
6.  结点层次：根结点的层定义为1；根的孩子为第二层结点，依此类推；
7.  树的高（深）度：树中最大的结点层
8.  结点的度：结点子树的个数
9.  树的度： 树中最大的结点度。
10. 叶子结点：也叫终端结点，是度为0的结点；
11. 分枝结点：度不为0的结点（非终端结点）；
12. 森林：互不相交的树集合；
13. 有序树：子树有序的树，如：家族树；
14. 无序树：不考虑子树的顺序；
15. 二叉树二叉树可以为空。
16. 二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。

==注意区分：==二叉树、二叉查找树/二叉排序树/二叉搜索树、二叉平衡(查找)树二叉平衡树肯定是一颗二叉排序树。堆不是一颗二叉平衡树。二叉树与树是不同的，二叉树不等价于分支树最多为二的有序树。树和二叉树都是一种非线性结构，树是递归结构，在树的定义中又用到了树的概念。当一个结点只包含一个子节点时，对于有序树并无左右孩子之分，而对于二叉树来说依然有左右孩子之分，所以二叉树与树是在结构上有所区别结构。

# 二、性质 #

1.  在二叉树的第 i 层上至多有2i-1个结点。
2.  深度为 k 的二叉树上至多含 2k-1 个结点（k≥1）
3.  对任何一棵二叉树，若它含有n0个叶子结点、n2个度为 2 的结点，则必存在关系式：n0= n2+1。
4.  具有 n 个结点的完全二叉树的深度为⎣log2 n⎦+1 。
5.  n个结点的二叉树中，完全二叉树具有最小的路径长度。
6.  如果对一棵有n个结点的完全二叉树的结点按层序编号,则对任一结点i（1<=i<=n),有： 如果i＝1，则结点i无双亲，是二叉树的根；如果i>1，则其双亲的编号是 i/2(整除）。
7.  如果2i>n，无左孩子；否则，其左孩子是结点2i。
8.  如果2i＋1>n，则结点i无右孩子；否则，其右孩子是结点2i＋1。

二叉树的存储结构顺序存储结构：仅仅适用于满或完全二叉树，结点之间的层次关系由性质5确定。  
二叉链表法：每个节点存储左子树和右子树。三叉链表：左子树、右子树、父节点，总的指针是n+2 在有n个结点的二叉链表中，值为非空的链域的个数为n-1。在有N个结点的二叉链表中必定有2N个链域。除根结点外，其余N-1个结点都有一个父结点。所以，一共有N-1个非空链域，其余2N-(N-1)=N+1个为空链域。

二叉链存储法也叫孩子兄弟法，左指针指向左孩子，右指针指向右兄弟。而中序遍历的顺序是左孩子，根，右孩子。这种遍历顺序与存储结构不同，因此需要堆栈保存中间结果。而中序遍历检索二叉树时，由于其存储结构跟遍历顺序相符，因此不需要用堆栈。遍历二叉树和线索二叉树遍历二叉树：使得每一个结点均被访问一次，而且仅被访问一次。

# 三、前/中/后序遍历 #

前序遍历DLR：根节点->左子树->右子树 。非递归的遍历实现要利用栈。  
中序遍历LDR：左子树->根节点->右子树。必须要有中序遍历才能得到一棵二叉树的正确顺序  
后序遍历LRD：左子树->右子树->根节点。需要栈的支持。

层次遍历：用一维数组存储二叉树时,总是以层次遍历的顺序存储结点。层次遍历应该借助队列。  
线索二叉树：对二叉树所有结点做某种处理可在遍历过程中实现；检索（查找）二叉树某个结点，可通过遍历实现；如果能将二叉树线索化，就可以简化遍历算法，提高遍历速度，目的是加快查找结点的前驱或后继的速度。

如何线索化？以中序遍历为例，若能将中序序列中每个结点前趋、后继信息保存起来，以后再遍历二叉树时就可以根据所保存的结点前趋、后继信息对二叉树进行遍历。对于二叉树的线索化，实质上就是遍历一次二叉树，只是在遍历的过程中，检查当前结点左，右指针域是否为空，若为空，将它们改为指向前驱结点或后继结点的线索。

前驱就是在这一点之前走过的点，不是下一将要去往的点。加上结点前趋后继信息（结索）的二叉树称为线索二叉树。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指向右孩子结点；  
树和森林树的存储结构：双亲表示法 孩子表示法 利用图表示树 孩子兄弟表示法（二叉树表示法）：链表中每个结点的两指针域分别指向其第一个孩子结点和下一个兄弟结点将树转化成二叉树：右子树一定为空加线：在兄弟之间加一连线

抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系 旋转：以树的根结点为轴心，将整树顺时针转45°森林转换成二叉树：将各棵树分别转换成二叉树 将每棵树的根结点用线相连 以第一棵树根结点为二叉树的根树与转换后的二叉树的关系：转换后的二叉树的先序对应树的先序遍历；转换后的二叉树的中序对应树的后序遍历哈弗曼树/霍夫曼树一些概念路径：从一个祖先结点到子孙结点之间的分支构成这两个结点间的路径； 路径长度：路径上的分支数目称为路径长度； 树的路径长度：从根到每个结点的路径长度之和。

结点的权：根据应用的需要可以给树的结点赋权值； 结点的带权路径长度：从根到该结点的路径长度与该结点权的乘积； 树的带权路径长度=树中所有叶子结点的带权路径之和；通常记作 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)\]。边的数目等于度。图遍历与回溯图搜索->形成搜索树穷举法。

贪心法。多步决策，每步选择使得构成一个问题的可能解，同时满足目标函数。

回溯法。根据题意，选取度量标准，然后将可能的选择方法按度量标准所要求顺序排好，每次处理一个量，得到该意义下的最优解的分解处理。图无向图回路或环：第一个顶点和最后一个顶点相同的路径。

简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路 连通：顶点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)个结点

# 五、图的遍历 #

深度优先搜索利用栈，广度优先搜索利用队列求一条从顶点i到顶点s的简单路径–深搜。求两个顶点之间的一条长度最短的路径–广搜。当各边上的权值均相等时,BFS算法可用来解决单源最短路径问题。

生成树和最小生成树  
每次遍历一个连通图将图的边分成遍历所经过的边和没有经过的边两部分，将遍历经过的边同图的顶点构成一个子图，该子图称为生成树。因此有DFS生成树和BFS生成树。  
生成树是连通图的极小子图，有n个顶点的连通图的生成树必定有n-1条边,在生成树中任意增加一条边，必定产生回路。若砍去它的一条边，就会把生成树变成非连通子图。

最小生成树：生成树中边的权值(代价)之和最小的树。最小生成树问题是构造连通网的最小代价生成树。