数据结构——森林和最优二叉树_数据逻辑中森林一定要连上吗-程序员宅基地

森林的逻辑结构

森林是m（m≥0）棵互不相交的树的集合。
森林的前序遍历：前序遍历森林中的每一棵数。
森林的后序遍历：后序遍历森林中的每一棵树。
森林通常有这两种方式。

树、森林与二叉树的转换

1.树转换为二叉树
①加线——树中所有相邻兄弟结点之间加一条线。
在这里插入图片描述
②去线——对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其他孩子结点之间的连线。

③层次调整——按照二叉树结点之间的关系进行层次调整。

2.森林转换为二叉树
①将森林中的每棵树转换成二叉树。
②从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子。
③按照二叉树结点之间的关系进行层次调整。
3.二叉树转换为树或森林
在这里插入图片描述
①加线——若某结点x是其双亲y的左孩子，则把结点x的右孩子、右孩子的右孩子、……，都与结点y用线连起来。

②去线——删去原二叉树中所有的双亲结点与右孩子结点的连线。

③层次调整——整理①、②两步所得到的树或森林，使之层次分明。
在这里插入图片描述

最优二叉树

一、哈夫曼算法

哈夫曼树：给定一组具有确定权值的叶子结点，带权路径长度最小的二叉树。
特点：
1.权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。
2.只有度为0（叶子结点）和度为2（分支结点）的结点，没有度为1的结点。
哈夫曼算法基本思想：
算法：HuffmanTree
输入：n个权值{w1，w2，w3，···，wn}
输出：哈夫曼树
　　1.初始化：由给定的n个权值{w1，w2，…，wn}构造n棵只有一个根结点的二叉树，从而得到一个二叉树集合F＝{T1，T2，…，Tn}；
　　2.重复下述操作，直到集合F中只剩下一颗二叉树
　　　2.1选取与合并：在F中选取根结点的权值最小的两棵二叉树分别作为左、右子树构造一棵新的二叉树，这棵新二叉树的根结点的权值为其左、右子树根结点的权值之和。
　　　2.2删除与加入：在F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到F中。
哈夫曼算法的伪代码：

算法：HuffmanTree 
输入：n个权值w[n]
输出：哈夫曼树huffmanTree[2n-1]
    1.数组huffTree初始化，所有元素结点的双亲、左右孩子都置为-1。
    2. 数组huffTree的前n个元素的权值置给定值w[n]。
3. 循环变量k从n~n-2进行n-1次合并：
    3.1 选取两个权值最小的根结点，其下标分别为i1, i2。
    3.2 将二叉树i1、i2合并为一棵新的二叉树k(初值为n，依次递增)。

代码：

/*
weight：权值域，保存该结点的权值；
lchild：指针域，结点的左孩子结点在数组中的下标；
rchild：指针域，结点的右孩子结点在数组中的下标；
parent：指针域，该结点的双亲结点在数组中的下标。
*/
struct element
{
         int weight;
      int lchild, rchild, parent;
};
void HuffmanTree(element huffTree[], int w[],int n){
    
    for (i=0; i<2*n-1; i++){
    
       huffTree [i].parent= -1;
       huffTree [i].lchild= -1;
       huffTree [i].rchild= -1;   
    }
    for (i=0; i<n; i++) 
       huffTree [i].weight=w[i];
    for (k=n; k<2*n-1; k++) {
    
        Select(huffTree, &i1, &i2); 
        huffTree[k].weight=huffTree[i1].weight+huffTree[i2].weight;
        huffTree[i1].parent=k;     
        huffTree[i2].parent=k; 
        huffTree[k].lchild=i1;    
        huffTree[k].rchild=i2;
    }
}

本文链接：https://blog.csdn.net/qq_43627106/article/details/103355277

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

c# 调用c++ lib静态库_c#调用lib-程序员宅基地

文章浏览阅读2w次，点赞7次，收藏51次。四个步骤1.创建C++ Win32项目动态库dll 2.在Win32项目动态库中添加外部依赖项 lib头文件和lib库3.导出C接口4.c#调用c++动态库开始你的表演...①创建一个空白的解决方案，在解决方案中添加 Visual C++ , Win32 项目空白解决方案的创建：添加Visual C++ , Win32 项目这......_c#调用lib

deepin/ubuntu安装苹方字体-程序员宅基地

文章浏览阅读4.6k次。苹方字体是苹果系统上的黑体，挺好看的。注重颜值的网站都会使用，例如知乎：font-family: -apple-system, BlinkMacSystemFont, Helvetica Neue, PingFang SC, Microsoft YaHei, Source Han Sans SC, Noto Sans CJK SC, W..._ubuntu pingfang

html表单常见操作汇总_html表单的处理程序有那些-程序员宅基地

文章浏览阅读159次。表单表单概述表单标签表单域按钮控件demo表单标签表单标签基本语法结构<form action="处理数据程序的url地址“ method=”get|post“ name="表单名称”></form><!--method将表单中的数据传送给服务器处理，get方式直接显示在url地址中，数据可以被缓存，且长度有限制；而post方式数据隐藏传输，_html表单的处理程序有那些

PHP设置谷歌验证器（Google Authenticator）实现操作二步验证_php otp 验证器-程序员宅基地

文章浏览阅读1.2k次。使用说明:开启Google的登陆二步验证（即Google Authenticator服务）后用户登陆时需要输入额外由手机客户端生成的一次性密码。实现Google Authenticator功能需要服务器端和客户端的支持。服务器端负责密钥的生成、验证一次性密码是否正确。客户端记录密钥后生成一次性密码。下载谷歌验证类库文件放到项目合适位置(我这边放在项目Vender下面)https://github.com/PHPGangsta/GoogleAuthenticatorPHP代码示例://引入谷_php otp 验证器

【Python】matplotlib.plot画图横坐标混乱及间隔处理_matplotlib更改横轴间距-程序员宅基地

文章浏览阅读4.3k次，点赞5次，收藏11次。matplotlib.plot画图横坐标混乱及间隔处理_matplotlib更改横轴间距

docker — 容器存储_docker 保存容器-程序员宅基地

文章浏览阅读2.2k次。①Storage driver 处理各镜像层及容器层的处理细节，实现了多层数据的堆叠，为用户提供了多层数据合并后的统一视图②所有 Storage driver 都使用可堆叠图像层和写时复制（CoW）策略③docker info 命令可查看当系统上的 storage driver主要用于测试目的，不建议用于生成环境。_docker 保存容器

随便推点

网络拓扑结构_网络拓扑csdn-程序员宅基地

文章浏览阅读834次，点赞27次，收藏13次。网络拓扑结构是指计算机网络中各组件（如计算机、服务器、打印机、路由器、交换机等设备）及其连接线路在物理布局或逻辑构型上的排列形式。这种布局不仅描述了设备间的实际物理连接方式，也决定了数据在网络中流动的路径和方式。不同的网络拓扑结构影响着网络的性能、可靠性、可扩展性及管理维护的难易程度。_网络拓扑csdn

JS重写Date函数，兼容IOS系统_date.prototype 将所有 ios-程序员宅基地

文章浏览阅读1.8k次，点赞5次，收藏8次。IOS系统Date的坑要创建一个指定时间的new Date对象时，通常的做法是：new Date("2020-09-21 11:11:00")这行代码在 PC 端和安卓端都是正常的，而在 iOS 端则会提示 Invalid Date 无效日期。在IOS年月日中间的横岗许换成斜杠，也就是new Date("2020/09/21 11:11:00")通常为了兼容IOS的这个坑，需要做一些额外的特殊处理，笔者在开发的时候经常会忘了兼容IOS系统。所以就想试着重写Date函数，一劳永逸，避免每次ne_date.prototype 将所有 ios