多叉树笔记

1 多叉树定义

多叉树是一种树形结构,它有一个特定的节点被称为“根”节点,而每个节点(除了根节点)恰好有一个前驱节点(父节点)。在有根多叉树中,每个节点可以拥有任意数量的后继节点(子节点)。

struct MultiTree{int val;vector<MultiTree*> children;MultiTree(int v):val(v){}
};

2 多叉树的构造

利用vector<int>parents记录每个节点的父节点
利用vector<MultiTree*>记录读入的每个节点(利用值先创建)
然后用关系 (multi[parents[i]-1]->children).push_back(multi[i]) 把每个节点连接起来。

void BuildMultiTree(vector<MultiTree*>& multi,vector<int> parents,int n){for(int i=1;i<n;i++){(multi[parents[i]-1]->children).push_back(multi[i]);}
}

3 逐层历遍打印多叉树

用队列辅助

void print_Multi(MultiTree* root){queue<MultiTree*> q;q.push(root);while(!q.empty()){MultiTree* temp=q.front();q.pop();//cout<<temp->val<<" ";for(int i=0;i<int(temp->children.size());i++){q.push(temp->children[i]);}}
}

4 多叉树到LC-RS二叉树的转变

LC-RS二叉树:左儿子右兄弟。以这种方式重排多叉树为二叉树。
ps.每个节点的左儿子一定使用它的所有儿子中的编号最小的,右兄弟一定使用比它编号大的兄弟中最小的兄弟的编号。

逻辑:
①先搞定根节点:LC-RS的根节点的值 永远等于 多叉树根节点的值
②左侧递归:左子树为 以多叉树根节点的第一个孩子为根节点的树
③右侧递归:右子树为空,左子树的右子树是 以多叉树根节点的下一个孩子为根节点的树
````````````````````````左子树的右子树的右子树是 以多叉树根节点的再下一个孩子为根节点的树
````直到多叉树的根节点的孩子节点全部安排好。

BiTree* Multi2Bi(MultiTree* root){if(!root) return NULL;BiTree* r=new BiTree(root->val);if(!root->children.empty()){r->lchild=Multi2Bi(root->children[0]);    //左递归BiTree* cur = r->lchild;for(int i=1;i<int(root->children.size());i++){cur->rchild=Multi2Bi(root->children[i]);cur=cur->rchild;                       //右递归}}return r;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/470483.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Chrome使用IE内核

Chrome使用IE内核 1.下载扩展程序IE Tab 2.将下载好的IE Tab扩展程序拖拽到扩展程序界面&#xff0c;之后重启chrome浏览器即可

使用pytest+openpyxl做接口自动化遇到的问题

最近使用pytestopenpyxl做了个接口自动化的小项目&#xff0c;遇到了一些问题。 首先&#xff0c;使用pytest这个框架&#xff0c;主要是使用了pytest.fixture, pytest.mark.parametrize这两个fixture去做参数化&#xff0c;里面注入的数据是用openpyxl来实现的。 接口介绍&a…

IEC60870-5-104 协议源码架构详细分析

IEC60870-5-104 协议源码架构 前言一、资源三、目录层级一二、目录层级二config/lib60870_config.hdependencies/READMEexamplesCMakeLists.txtcs101_master_balancedcs104_client_asyncmulti_client_servertls_clienttls_server说明 make这些文件的作用是否需要导入这些文件&a…

TensorRT基础知识

github:https://github.com/NVIDIA/TensorRT 官网快速入门链接&#xff1a;Quick Start Guide :: NVIDIA Deep Learning TensorRT Documentation 引言&#xff1a; TensorRT 是 NVIDIA 推出的一个高性能深度学习推理库&#xff0c;专门用于优化和加速已经训练好的深度学习模型…

jenkins提交gitee后自动部署

jenkins中安装gitee插件 Gitee Plugin​​​​​​ 配置gitee WebHook 生成giteeHook密码 去gitee中配置webHook 输入jenkins中的url和生成的密码 当我们再提交后就可以自动部署 gitee官方配置

软件测试面试八股文(超详细整理)

请你说一说测试用例的边界 参考回答&#xff1a; 边界值分析法就是对输入或输出的边界值进行测试的一种黑盒测试方法。通常边界值分析法是作为对等价类划分法的补充&#xff0c;这种情况下&#xff0c;其测试用例来自等价类的边界。 常见的边界值 1)对16-bit 的整数而言 32…

【金融风控】特征评估与筛选详解

内容介绍 掌握单特征分析的衡量指标 知道 IV&#xff0c;PSI等指标含义 知道多特征筛选的常用方法 掌握Boruta,VIF,RFE,L1等特征筛选的使用方法 【理解】单特征分析 什么是好特征 从几个角度衡量&#xff1a;覆盖度&#xff0c;区分度&#xff0c;相关性&#xff0c;稳定…

链游系统定制化开发:引领游戏产业的新时代

在数字革命的浪潮中&#xff0c;链游&#xff08;区块链游戏&#xff09;作为一种新兴游戏形式&#xff0c;正重新定义游戏产业的发展方向。链游将区块链技术与传统游戏结合&#xff0c;使游戏体验更加公平透明&#xff0c;并赋予玩家真正的资产所有权。这一领域不仅为玩家带来…

2024 年 8 个最佳 API 设计工具图文介绍

8 个最佳 API 设计工具推荐&#xff0c;包括 Apifox、Postman、Swagger、Insomnia、Stoplight、Hoppscotch、RapidAPI和Paw。 详细介绍&#xff1a;2024 年 8 个最佳 API 设计工具推荐

知识库管理系统:企业数字化转型的加速器

在数字化转型的大潮中&#xff0c;知识库管理系统&#xff08;KBMS&#xff09;已成为企业提升效率和创新能力的关键工具。本文将探讨知识库管理系统的定义、企业建立知识库的必要性&#xff0c;以及如何快速搭建企业知识库。 知识库管理系统是什么&#xff1f; 知识库管理系统…

24/11/12 算法笔记<强化学习> Policy Gradient策略梯度

gradient的核心就是每次更新前要重新收集&#xff0c;每个阶段的actor是不一样的. 策略梯度算法的核心思想&#xff1a; 策略表示&#xff1a;首先&#xff0c;策略梯度方法需要一个策略&#xff0c;该策略能够根据当前的状态选择一个动作。这个策略通常由一个参数化的函数表示…

物理设备命名规则(Linux网络服务器 15)

Linux系统中的一切都是文件&#xff0c;硬件设备也不例外。既然都是文件&#xff0c;就必须有文件名称。系统内核中udev设备管理器会自动把硬件名称规范化起来&#xff0c;目的是让用户通过设备文件的名字可以大致了解设备属性以及分区信息。这对于陌生的设备来说特别方便。另外…

SciPy:Python 科学计算工具包的全面教程

SciPy&#xff1a;Python 科学计算工具包的全面教程 引言 在数据科学和科学计算的领域&#xff0c;Python 已经成为一种流行的编程语言。作为 Python 的核心库之一&#xff0c;SciPy 提供了高效的数值计算功能&#xff0c;是科学计算、工程和数学应用中不可或缺的工具。本文将…

SAP_MM_SD_PP_FICO_视频课程几乎免费送

朋友们&#xff0c;都已经是2024年了&#xff0c;SAP中国区都已经被合并到樱花国的亚太区了&#xff0c;SAP上海研发中心也陆续撤离中*&#xff0c;竟然还有朋友花上万RMB学习SAP&#xff0c;钱花了可以在挣&#xff0c;主要是那个视频课程一个模块下来就得上百个小时&#xff…

如何在Puppeteer中实现表单自动填写与提交:问卷调查

一、介绍 在现代市场研究中&#xff0c;问卷调查是一种重要的工具。企业通过在线问卷调查了解消费者对产品或服务的需求、偏好和满意度&#xff0c;从而为产品开发、市场营销和服务优化提供指导。然而&#xff0c;对于爬虫技术专家来说&#xff0c;批量自动化地填写和提交问卷…

深度学习——权重初始化、评估指标、梯度消失和梯度爆炸

文章目录 &#x1f33a;深度学习面试八股汇总&#x1f33a;权重初始化零初始化 (Zero Initialization)随机初始化 (Random Initialization)Xavier 初始化&#xff08;Glorot 初始化&#xff09;He 初始化正交初始化&#xff08;Orthogonal Initialization&#xff09;预训练模型…

实验一:自建Docker注册中心

基于容器安装运行Registry Docker Registry主要负责镜像仓库的管理 创建并启动一个运行Docker Registry: docker run -d -p 5000:5000 --restartalways --name myregistry -v /opt/data/registry:/var/lib/registry registry -v&#xff1a;将主机的本地/opt/data/registry目…

同三维T610UDP-4K60 4K60 DP或HDMI或手机信号采集卡

1路DP/HDMI/TYPE-C&#xff08;手机/平板等&#xff09;视频信号输入1路MIC1路LINE OUT,带1路HDMI环出&#xff0c;USB免驱&#xff0c;分辨率4K60&#xff0c;可采集3路信号中其中1路&#xff0c;按钮切换&#xff0c;可采集带TYPE-C接口的各品牌手机/平板/笔记本电脑等 同三维…

ReactPress技术揭秘

ReactPress Github项目地址&#xff1a;https://github.com/fecommunity/reactpress 欢迎Star。 一、引言 ReactPress是一个基于React构建的开源发布平台&#xff0c;它不仅可以帮助用户在支持React和MySQL数据库的服务器上快速搭建自己的博客或网站&#xff0c;还能作为一个…

Java 网络编程(一)—— UDP数据报套接字编程

概念 在网络编程中主要的对象有两个&#xff1a;客户端和服务器。客户端是提供请求的&#xff0c;归用户使用&#xff0c;发送的请求会被服务器接收&#xff0c;服务器根据请求做出响应&#xff0c;然后再将响应的数据包返回给客户端。 作为程序员&#xff0c;我们主要关心应…