【二叉树遍历算法应用】------补录
0.二叉树结点的链式存储结构
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>typedef char TElemType;//树中元素基本类型为char类型//二叉树结点链式存储结构(二叉链表)
typedef struct BiNode
{TElemType data;//数据域struct BiNode* lchild, * rchild;//左,右孩子指针
}BiNode,*BiTree;
//BiNode:用来定义结点类型
//BiTree:用来定义树类型
1.复制二叉树
int CopyBiTree(BiTree b,BiTree* newb)
注意:原本存在的树只是会遍历,不会被修改,故传入一级指针
但要复制成的新树,应传入结点指针的地址,即二级指针,因为要修改结点指针的值(指向新开辟的结点空间)
1.1算法步骤:
(1)返回条件:当前根结点为空,注意复制完空结点之后再返回
(2)当前结点非空,申请新结点空间并复制根结点
(3)递归复制左子树(注意传入New树待修改指针的地址)
(4)递归复制右子树(注意传入New树待修改指针的地址)
//1.先序复制二叉树 (万变不离其宗,就是先序遍历算法的变种)
//注意:原本存在的树只是会遍历,不会被修改,故传入一级指针
//但要复制成的新树,应传入结点指针的地址,即二级指针,因为要修改结点指针的值(指向新开辟的结点空间)
int CopyBiTree(BiTree b,BiTree* newb)
{//[1]返回条件:当前根结点为空,注意复制完空结点之后再返回if (b == NULL){(*newb) = NULL;//易错1:忘记复制空结点return 0;}//[2]当前结点非空,申请新结点空间,复制根结点(*newb) = (BiNode*)malloc(sizeof(BiNode));if (!(*newb)){printf("内存分配失败!\n");exit(-1);}(*newb)->data = b->data;//[3]递归复制左子树CopyBiTree(b->lchild, &((*newb)->lchild));//注意传入New树待修改指针的地址//[4]递归复制右子树CopyBiTree(b->rchild, &((*newb)->rchild));
}
2.计算二叉树的深度
- 深度回顾:指从头结点开始到最远的叶子结点,路径上的结点数【注意:包括头结点】
int DepthBiTree(BiTree b)
注意:只进行遍历,不会修改树的结构,故传入一级指针
2.1算法步骤:
(1)返回条件:当前根结点为空,返回0
(2)递归计算左子树的深度记为m
(3)递归计算右子树的深度记为n
(4)返回子树的深度:即m和n中的较大值,并加1
加1是因为子树根结点要算上;
返回较大值是因为深度 应该是最远路径上的结点总数,
//2.计算二叉树深度 (树的深度:指从头结点开始到最远的叶子结点,路径上的结点数【注意:包括头结点】)
//注意:只进行遍历,不会修改树的结构,故传入一级指针
int DepthBiTree(BiTree b)
{//[1]返回条件:当前根结点为空,返回0if (b == NULL){return 0;}//[2]递归计算左子树的深度记为mint m = DepthBiTree(b->lchild);//[3]递归计算右子树的深度记为nint n = DepthBiTree(b->rchild);//[4]返回子树的深度:即m和n中的较大值,并加1//加1是因为子树根结点要算上return (m > n) ? m + 1 : n + 1;
}
3.计算二叉树中结点总数
int NodeCount(BiTree b)
3.1算法步骤:
(1)返回条件:当前根结点为空,返回0
(2)递归计算左子树的结点总数记为m
(3)递归计算右子树的结点总数记为n
(4)返回子树的结点总数:即m和n之和,并加1
加1是因为子树根结点要算上
//3.计算二叉树中结点总数
int NodeCount(BiTree b)
{//[1]返回条件:当前根结点为空,返回0if (b == NULL){return 0;}//[2]递归计算左子树的结点总数记为mint m = NodeCount(b->lchild);//[3]递归计算右子树的结点总数记为nint n = NodeCount(b->rchild);//[4]返回子树的结点总数:即m和n之和,并加1//加1是因为子树根结点要算上return m + n + 1;
}
4.计算二叉树中叶子结点总数
- 回顾叶子结点:左子树和右子树均为空的结点,一般在完全二叉树的最下面
int LeadCountBiTree(BiTree b)
4.1算法步骤
(1)返回条件1:当前根结点为空,返回0
(2)返回条件2:当前结点为叶子结点,返回1
两个返回条件缺一不可
(3)递归计算左子树和右子树的叶子结点总数记为m和n
(4)返回子树的叶子结点总数:即m和n之和
//4.计算二叉树中叶子结点总数(叶子结点:左子树和右子树均为空的结点,一般在完全二叉树的最下面)
int LeadCountBiTree(BiTree b)
{//[1]返回条件1:当前根结点为空,返回0if (b == NULL){return 0;}//[2]返回条件2:当前结点为叶子结点,返回1if (b->rchild == NULL && b->lchild == NULL){return 1;}//[3]递归计算左子树和右子树的叶子结点总数记为m和nint m = LeadCountBiTree(b->lchild);int n = LeadCountBiTree(b->rchild);//[4]返回子树的叶子结点总数:即m和n之和return m+n;
}
5.整体代码实现
- 样例树:应输入序列
abc##de###fg#h### - 复制后新树的先序序列为:
abcdefgh - 深度:4
- 结点总数:8
- 叶子结点总数:3

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>typedef char TElemType;typedef struct BiNode
{TElemType data;struct BiNode* lchild, * rchild;
}BiNode,*BiTree;//.先序遍历
bool PreOrderTraverse(BiTree b)
{if (b == NULL){return true;}printf("%c", b->data);//根PreOrderTraverse(b->lchild); //左PreOrderTraverse(b->rchild); //右}//先序建立整树
bool CreateBiTree(BiTree * b)
{//[0]TElemType ch;scanf_s("%c", &ch);if (ch == '#'){(*b) = NULL;}else{(*b) = (BiNode*)malloc(sizeof(BiNode));if (!(*b)){printf("内存分配失败!\n");exit(-1);}(*b)->data = ch;//根CreateBiTree(&((*b)->lchild)); //左CreateBiTree(&((*b)->rchild));//右}return true;
}//1.先序复制二叉树 (万变不离其宗,就是先序遍历算法的变种)
//注意:原本存在的树只是会遍历,不会被修改,故传入一级指针
//但要复制成的新树,应传入结点指针的地址,即二级指针,因为要修改结点指针的值(指向新开辟的结点空间)
int CopyBiTree(BiTree b,BiTree* newb)
{//[1]返回条件:当前根结点为空,注意复制完空结点之后再返回if (b == NULL){(*newb) = NULL;//易错1:忘记复制空结点return 0;}//[2]当前结点非空,申请新结点空间,复制根结点(*newb) = (BiNode*)malloc(sizeof(BiNode));if (!(*newb)){printf("内存分配失败!\n");exit(-1);}(*newb)->data = b->data;//[3]递归复制左子树CopyBiTree(b->lchild, &((*newb)->lchild));//注意传入New树待修改指针的地址//[4]递归复制右子树CopyBiTree(b->rchild, &((*newb)->rchild));
}//2.计算二叉树深度 (树的深度:指从头结点开始到最远的叶子结点,路径上的结点数【注意:包括头结点】)
//注意:只进行遍历,不会修改树的结构,故传入一级指针
int DepthBiTree(BiTree b)
{//[1]返回条件:当前根结点为空,返回0if (b == NULL){return 0;}//[2]递归计算左子树的深度记为mint m = DepthBiTree(b->lchild);//[3]递归计算右子树的深度记为nint n = DepthBiTree(b->rchild);//[4]返回子树的深度:即m和n中的较大值,并加1//加1是因为子树根结点要算上return (m > n) ? m + 1 : n + 1;
}//3.计算二叉树中结点总数
int NodeCount(BiTree b)
{//[1]返回条件:当前根结点为空,返回0if (b == NULL){return 0;}//[2]递归计算左子树的结点总数记为mint m = NodeCount(b->lchild);//[3]递归计算右子树的结点总数记为nint n = NodeCount(b->rchild);//[4]返回子树的结点总数:即m和n之和,并加1//加1是因为子树根结点要算上return m + n + 1;
}//4.计算二叉树中叶子结点总数(叶子结点:左子树和右子树均为空的结点,一般在完全二叉树的最下面)
int LeadCountBiTree(BiTree b)
{//[1]返回条件1:当前根结点为空,返回0if (b == NULL){return 0;}//[2]返回条件2:当前结点为叶子结点,返回1if (b->rchild == NULL && b->lchild == NULL){return 1;}//[3]递归计算左子树和右子树的叶子结点总数记为m和nint m = LeadCountBiTree(b->lchild);int n = LeadCountBiTree(b->rchild);//[4]返回子树的叶子结点总数:即m和n之和return m+n;
}int main()
{BiTree T;CreateBiTree(&T);PreOrderTraverse(T);printf("\n");BiTree NewT;CopyBiTree(T,&NewT);PreOrderTraverse(NewT);printf("NewT的深度为:%d\n", DepthBiTree(NewT));printf("NewT的结点总数为:%d\n", NodeCount(NewT));printf("NewT的叶子结点总数为:%d\n", LeadCountBiTree(NewT));return 0;
}

相关文章:
【二叉树遍历算法应用】------补录
0.二叉树结点的链式存储结构 #include<stdio.h> #include<stdlib.h> #include<stdbool.h>typedef char TElemType;//树中元素基本类型为char类型//二叉树结点链式存储结构(二叉链表) typedef struct BiNode {TElemType data;//数据域…...
AtCoder Beginner Contest 368
A.Cut(模拟) 题意: 有一叠 N N N张扑克牌,最上面的 i i i张扑克牌上写着一个整数 A _ i A\_i A_i。 你从牌堆底部取出 K K K张牌,将它们放在牌堆顶部,并保持它们的顺序。 操作后从上到下输出写在卡…...
WebGL系列教程六(纹理映射与立方体贴图)
目录 1 前言2 思考题3 纹理映射介绍4 怎么映射?5 开始绘制5.1 声明顶点着色器和片元着色器5.2 修改顶点的颜色为纹理坐标5.3 指定顶点位置和纹理坐标的值5.4 获取图片成功后进行绘制5.5 效果5.6 完整代码 6 总结 1 前言 上一讲我们讲了如何使用索引绘制彩色立方体&a…...
为什么nii.gz转.nrrd标签体积变大?
import SimpleITK as sitk # nii nii.gz nrrd格式之间互相转换 def nii2nii(oripath, savepath):data sitk.ReadImage(oripath)img sitk.GetArrayFromImage(data)out sitk.GetImageFromArray(img)sitk.WriteImage(out, savepath)if __name__ __main__:oripath 00292625.ni…...
软件安装攻略:EmEditor编辑器下载安装与使用
EmEditor是一款在Windows平台上运行的文字编辑程序。EmEditor以运作轻巧、敏捷而又功能强大、丰富著称,得到许多用户的好评。Windows内建的记事本程式由于功能太过单薄,所以有不少用户直接以EmEditor取代,emeditor是一个跨平台的文本编辑器&a…...
Redis的watch机制详解
WATCH 是 Redis 提供的一个用于实现 乐观锁 (Optimistic Lock) 的命令,通常用于实现事务中的并发控制。它允许客户端监控一个或多个键的变化,并确保事务(MULTI/EXEC)中执行的操作在这些键没有发生改变的情况下才能成功提交。若在事…...
UnrealEngine 打包Android平台应用
虚幻引擎 支持将项目发布到 安卓(Android) 移动设备上,并且提供了若干功能帮你将项目发布到 谷歌游戏商店。本节包含了如何设置Android开发环境、如何使用Android功能和服务、以及如何为发布游戏做准备相关的指南。 当前SDK要求 当前UE版本…...
Linux:git
hello,各位小伙伴,本篇文章跟大家一起学习《Linux:git》,感谢大家对我上一篇的支持,如有什么问题,还请多多指教 ! 如果本篇文章对你有帮助,还请各位点点赞!!&…...
electron有关mac构建
针对 Mac M1/2/3 芯片的设备,proces.archarm64. 执行下面命令,检查下按照的 node.js 版本是不是 intel x64 指令集,如果是的话安装下 arm64 指令集的 node.js终端中执行以下命令:node -p process.arch 对应的node版本也是arm版 …...
C语言-数据结构 弗洛伊德算法(Floyd)邻接矩阵存储
弗洛伊德算法相比迪杰斯特拉相似的地方都是遍历邻接矩阵不断调整最短路径的信息,并且两种算法面对多源最短路径的时间复杂度都是O(n^3),Floyd采用的是动态规划而Dijkstra是采用贪心的思想。在Floyd中我们将创建两个数组进行辅助,一个path二维…...
pyspark 安装记录
1、安装软件 1、python 3.10 2、hadoop-3.3.4 里面的winutils 要记得添加 3、java-17 4、spark-3.5.1-bin-hadoop3 python 安装 pyspark,Jupyter notebook pip install pyspark pip install jupyter notebook 2、添加环境变量 JAVA_HOME=C:\PySparkService\java-17H…...
高度可定制的电竞鼠标,雷柏VT1 PRO MAX体验
不管是菜鸟还是老鸟,游戏玩到某个阶段很容易出现瓶颈,在游戏的某个阶段,这里面制约最大的除了操作之外,实际上还是我们用的硬件。比如在PC游戏中,鼠标的影响就非常大,像是在游戏中如果鼠标延迟过高…...
经验笔记:SOA(面向服务的架构)
SOA(面向服务的架构)经验笔记 引言 SOA(Service-Oriented Architecture, 面向服务的架构)是一种设计原则,用于构建灵活且可扩展的分布式系统。SOA强调将应用程序的不同功能封装为独立的服务,这些服务通过…...
triton之ttir学习
一 基本语句 1 常量 %cst arith.constant dense<520192> : tensor<4096xi32> %c127_i32 arith.constant 127 : i32 %cst arith.constant dense<520192> : tensor<4096xi32> 解释:这条语句定义了一个名为 %cst 的常量,它…...
如何在AWS账户上进行充值:一份详尽指南
大家好,小编今天给大家带来一份关于如何在AWS账户上进行充值的详尽指南。对于使用AWS服务的用户来说,保持账户余额充足是确保服务不中断的关键。下面,九河云将详细讲解具体的操作步骤。 步骤一:登录AWS管理控制台 首先ÿ…...
(六十四)第 10 章 内部排序(静态链表的插入排序)
示例代码 staticLinkList.h // 静态链表的插入排序实现头文件#ifndef STATIC_LINK_LIST_H #define STATIC_LINK_LIST_H#include "errorRecord.h"#define SIZE 100 #define NUM 8typedef int InfoType; typedef int KeyType;typedef struct {KeyType key;InfoType inf…...
appium历史版本地址链接
appium / Appium.app / Downloads — Bitbucket ios的appium界面图 链接: https://pan.baidu.com/s/1i8BRaZgQA3ImLUhKZjfhiA 提取码: 5c8b...
TCPIP网络编程(尹圣雨)UDP 轮流收发消息(windows)
端口号写的是 2345 客户端 #include <iostream> #include <winsock2.h> #pragma comment(lib, "ws2_32.lib")using std::cout; using std::endl; using std::cin;int main() {WSADATA wsa;if (WSAStartup(MAKEWORD(2, 2), &wsa) ! 0){cout <<…...
【相机方案(2)】V4L2 支持相机图像直接进入GPU内存吗?DeepStream 确实可以将图像数据高效地放入GPU内存进行处理!
V4L2 支持相机图像直接进入GPU内存吗? V4L2(Video4Linux Two)是Linux内核中用于视频捕获和播放的API,它本身并不直接支持将相机捕获的图像数据直接拷贝到GPU内存而不经过CPU内存。V4L2主要关注于视频设备的控制、数据的捕获和播放…...
UEFI——PEI阶段
一、PEI介绍 Pre-EFI Initialization(PEI)在引导的早期被调用,仅利用CPU资源调用PEIM,这些PEIM负责: (1)初始化一些永久内存 (2)在HOBs中描述内存信息 (3…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...
电脑插入多块移动硬盘后经常出现卡顿和蓝屏
当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时,可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案: 1. 检查电源供电问题 问题原因:多块移动硬盘同时运行可能导致USB接口供电不足&#x…...
3403. 从盒子中找出字典序最大的字符串 I
3403. 从盒子中找出字典序最大的字符串 I 题目链接:3403. 从盒子中找出字典序最大的字符串 I 代码如下: class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...
七、数据库的完整性
七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...
Git常用命令完全指南:从入门到精通
Git常用命令完全指南:从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...
Leetcode33( 搜索旋转排序数组)
题目表述 整数数组 nums 按升序排列,数组中的值 互不相同 。 在传递给函数之前,nums 在预先未知的某个下标 k(0 < k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...
Linux 下 DMA 内存映射浅析
序 系统 I/O 设备驱动程序通常调用其特定子系统的接口为 DMA 分配内存,但最终会调到 DMA 子系统的dma_alloc_coherent()/dma_alloc_attrs() 等接口。 关于 dma_alloc_coherent 接口详细的代码讲解、调用流程,可以参考这篇文章,我觉得写的非常…...
【Vue】scoped+组件通信+props校验
【scoped作用及原理】 【作用】 默认写在组件中style的样式会全局生效, 因此很容易造成多个组件之间的样式冲突问题 故而可以给组件加上scoped 属性, 令样式只作用于当前组件的标签 作用:防止不同vue组件样式污染 【原理】 给组件加上scoped 属性后…...
vue3 手动封装城市三级联动
要做的功能 示意图是这样的,因为后端给的数据结构 不足以使用ant-design组件 的联动查询组件 所以只能自己分装 组件 当然 这个数据后端给的不一样的情况下 可能组件内对应的 逻辑方式就不一样 毕竟是 三个 数组 省份 城市 区域 我直接粘贴组件代码了 <temp…...
