完全二叉树以及哈夫曼树笔记
2024-08-06 14:29:17
发布于：北京
18阅读
0回复
0点赞
设完全二叉树节点总数为n，那么有如下结论：
n为奇数时，完全二叉树中没有度为1的结点，此时n=n0+n2。
n为偶数时，完全二叉树中只有一个度为1的结点，此时n=n0+1+n2。
性质一
具有n(n>=0)个结点的完全二叉树的深度为|下取整|log2(n)+1。
性质二
若有一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给节点
编号1,2,...,n,则：
1.若结点编号i=1，则结点i为根，无父结点;
2.若i>1，则i的父结点编号为i/2;
3.针对编号为i的结点：
3.1其左孩子编号为2*i(2*i<=n)
3.2其右孩子编号为2*i+1(2*i+1<=n)
在一棵树中，选择一个结点，他与根结点的通路，称为路径。
路径中边的数目称为路径长度，若规定根结点的层数为1，则第L层结点到
根结点的路径长度为L-1 。
若将树中结点赋给一个有着某种意义的数值，则这个数值称为该结点的权。
该结点的路径长度与该结点权的乘积，为结点的带权路径长度。
树的带权路径长度规定为所有叶子结点的带权路径长度之和，计为WPL。
对于给定有各自权值的n个结点，构建哈夫曼树：
1.在n个权值中选出两个最小的权值，对应的两个结点组成一个新的二叉树
的左右孩子;
2. 删除使用过的两个权值，将新的权值加入到权值集合中;
3.重复1和2，直到无法再选出两个权值，这棵树就是哈夫曼树。
有帮助，赞一个