网站的建设背景图片,小程序code,html考试界面设计,网站提供的服务目录 1、基本概念
2、二叉树Binary Tree
3、树、森林与二叉树的转换
4、赫夫曼树Huffman Tree与赫夫曼编码Huffman Coding 1、基本概念
#xff08;1#xff09;树#xff08;Tree#xff09;是 n#xff08;n ≥\geq 1#xff09;个节点的有限集#xff0c;n 0时称…
目录 1、基本概念
2、二叉树Binary Tree
3、树、森林与二叉树的转换
4、赫夫曼树Huffman Tree与赫夫曼编码Huffman Coding 1、基本概念
1树Tree是 nn ≥\geq 1个节点的有限集n 0时称为空树。
2非空树唯一拥有一个根Root结点Noden 1时其余结点可分为mm 0个互不相交的有限集并各自成根的子树Sub Tree。
3结点拥有的子树数目称为结点的度Degree度为 0 的结点称为叶结点Leaf树的度是树各结点的度的最大值。 4结点之间的关系兄弟Sibling——孩子Child——双亲Parent 5结点的层次Level从根算起根为第一层根的孩子为第二层一直往下最大层次为深度Depth。 6如果将树中结点的各子树看成从左至右呈有次序的不能互换的则称该树为有序树,否则称为无序树。
7森林Forest是 mm ≥\geq 0棵互不相交的树的集合。对树中每个结点而言其子树的集合即为森林。
8树的双亲表示法如下data数据域存储结点的数据信息parent指针域存储该结点双亲在数组中的下标根结点的parent定义为 -1 即不存在该结点。 2、二叉树Binary Tree
1每个结点的度 ≤\leq 2左右有次序之分的树称为二叉树。
2二叉树的五种基本形态空二叉树、只有一个根结点、根结点只有左子树、根结点只有右子树、根结点既有左子树又有右子树。
3斜树包含左斜树所有结点都只有左子树的二叉树和右斜树所有结点都只有右子树的二叉树每一层都只有一个结点结点个数即二叉斜树的深度同线性表结构。
4满二叉树叶结点仅在最下层非叶非根的结点度数均为 2 的二叉树。 满二叉树
5完全二叉树按层序从上到下从左到右编号结点的位置与满二叉树相同的二叉树特点有叶结点仅在最下两层最下层叶子集中在左部连续位置同结点数的二叉树深度最小。 完全二叉树
6二叉树的数学性质有
(i) 第 i 层至多 2i−12^{i-1} 个结点i ≥\geq 1
(ii) 深度为k时至多有 2k2^{k} -1个结点k ≥\geq1
(iii) 所有节点的度数之和等于节点总数-1若叶子结点数为 n0n_{0} 度为2的结点数为n1n_{1} 则n0n_{0} n1n_{1} 1 二叉树除了叶结点就是度为1或2的结点
(iv) 具有n个结点的完全二叉树的深度为[logn]1
7顺序存储结构一般只用于完全二叉树。
8二叉链表一个数据域两个指针域。
9遍历二叉树从根节点出发按某种次序依次唯一地访问每个结点。
(i) 前序遍历若二叉树为空则空操作返回否则先访问根结点然后遍历左子树, 再遍历右子树。
(i) 中序遍历若二叉树为空则空操作返回否则先遍历左子树然后访问根结点再遍历右子树。
(i) 后序遍历若二叉树为空则空操作返回否则从左到右先叶子后结点遍历访问左右子树最后根结点。 (i) 层序遍历若二叉树为空则空操作返回否则从第一层根结点开始往下从左到右对结点逐个访问。
已知前 中序 / 中 后序遍历序列都可以唯一确定一棵二叉树。
3、树、森林与二叉树的转换
1树转换为二叉树
(i) 加线在所有兄弟结点之间加一条连线。
(ii) 去线每个结点只保留它与第一个孩子结点的连线删除它与其他孩子结点之间的连线。
(iii) 层次调整以树的根结点为轴心将整棵树顺时针旋转一定角度使其结构层次分明。 2森林转二叉树
(i) 将每棵树转换为二叉树。
(ii) 第一棵二叉树不动从第二棵开始依次把后一棵二叉树的根结点作为前一棵根结点的右孩子连线。 3二叉树转换成树
(i) 加线左孩子的n个右孩子结点都作为此结点的孩子。将该结点与这些右孩子结点用线连接起来。
(ii) 去线删除原二叉树中所有结点与其右孩子结点的连线。 4二叉树转森林
(i) 从根结点开始若存在右孩子则删除与右孩子的连线。
(ii) 再查看分离后的二叉树若存在右孩子则连线删除直到所有右孩子连线删除为止。
(iii) 再将分离的二叉树都转换为树即可。 4、赫夫曼树Huffman Tree与赫夫曼编码Huffman Coding
从树一个结点到另一个结点的之间的分支构成两个结点之间的路径路径分支数目称为路径长度。树的路径长度即从树根到每一结点的路径长度之和结点间连线相关数称为权Weight。树的带权路径长度为树中所有叶子结点的带权路径长度之和带权路径长度WPL最小的二叉树称为赫夫曼树。 二叉树a的路径长度为1122334420WPL 5×\times1 15×\times2 40×\times3 30×\times4 10×\times4 315
二叉树b的路径长度为1233212216WPL 5×\times3 15×\times3 40×\times2 30×\times2 10×\times4 220
我们可以得出构造赫夫曼树的算法描述
1根据给定的n个权值{ w1w_{1},w2w_{2},w3w_{3}……,wnw_{n}}构成 n 棵二叉树的集合F T1T_{1},T2T_{2},T3T_{3}……,TnT_{n}}其中每棵二叉树T中只有一个带权为w的根结点其左右子树均为空。
2在 F 中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树并置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
3在 F 中删除这两棵树同时将新得到的二叉树加入F中。
4重复步骤2和3直到F只含一棵树为止这棵树便是赫夫曼树。
赫夫曼编码规定赫夫曼树的左分支代表0右分支代表1则从根结点到叶子结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码即赫夫曼编码它在信息存储与传输过程中对信息高效压缩。
假设六个字母的频率为A 27B 8C 15D 15E 30F 5合起来正好是100赫夫曼树构造如下
