当前位置: 首页 > news >正文

链式二叉树--前序中序后序遍历,高度,节点个数问题

目录

 前言:

一:链式二叉树的结构定义

 二:链式二叉树的遍历--->前序,中序,后序

1.前序

 递归展开图分析

2.中序 

递归展开图分析 

3.后序 

三:二叉树结点的求解 

1.二叉树总结点

递归展开分析 

2.二叉树叶子结点数 

递归展开分析 

3.二叉树第k层节点个数 

递归展开分析 

四:二叉树的高度 

五:总结语


接下来的日子会顺顺利利,万事胜意,生活明朗-----------林辞忧

 前言:

链式二叉树作为后续AVL树,B系列树的雏形,理解掌握链式二叉树的各种操作很重要,此处就需要用递归来实现链式二叉树的各种操作,相信认真学习过后会对递归有更深刻的理解,接下来我们就开始上菜

一:链式二叉树的结构定义

链式二叉树的结构由指针域和数值域组成,况且链式二叉树并不都是完全二叉树,还有普通二叉树,每个节点最多两个孩子

 二:链式二叉树的遍历--->前序,中序,后序

1.前序

BTNode* Buynode(int x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc fail\n");return NULL;}newnode->left = NULL;newnode->right = NULL;newnode->data = x;return newnode;
}BTNode* CreatTree()
{BTNode* n1 = Buynode(1);BTNode* n2 = Buynode(2);BTNode* n3 = Buynode(3);BTNode* n4 = Buynode(4);BTNode* n5 = Buynode(5);BTNode* n6 = Buynode(6);BTNode* n7 = Buynode(7);n1->left = n2;n1->right = n3;n2->left = n4;n2->right = n5;n3->left = n6;n3->right = n7;return n1;
}
void PrevOrder(BTNode* root)
{if (root == NULL){printf("N ");return ;}printf("%d ", root->data);PrevOrder(root->left);PrevOrder(root->right);
}
 递归展开图分析

2.中序 

void InOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}
递归展开图分析 

3.后序 

void PostOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);
}

后续递归展开图同上展开即行

三:二叉树结点的求解 

1.二叉树总结点

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL)//递归结束条件{return 0;}return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;//从左子树和右子树中分别计数
}
递归展开分析 

2.二叉树叶子结点数 

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL)//空树返回0return 0;if (root->left == NULL && root->right == NULL)//叶子节点无孩子return 1;return BinaryTreeLeafSize(root->left)//递归往下寻找 + BinaryTreeLeafSize(root->right);
}
递归展开分析 

3.二叉树第k层节点个数 

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL)return 0;if (k == 1)//循环走到k==1时停止,且不为空return 1;//分治思想:转化为求k-1层的节点数return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root, k - 1);
}
递归展开分析 

四:二叉树的高度 

//二叉树的高度
int BinaryTreeHeight(BTNode* root)
{if (root == NULL)return 0;//记录左右长度,再进行比较int leftHeight = BinaryTreeHeight(root->left);int rightHeight = BinaryTreeHeight(root->right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

 此图递归展开图就省略了昂

五:总结语

学会二叉树得学会画图,实在不懂时,画画递归展开图会好很多的

相关文章:

链式二叉树--前序中序后序遍历,高度,节点个数问题

目录 前言: 一:链式二叉树的结构定义 二:链式二叉树的遍历--->前序,中序,后序 1.前序 递归展开图分析 2.中序 递归展开图分析 3.后序 三:二叉树结点的求解 1.二叉树总结点 递归展开分析 2…...

HCIA——TCP协议详解

目录 1、TCP概念及协议头部格式 1.1TCP特点 1.2TCP协议协议头部格式 1.3字段进行介绍 1.3.1源端口和目的端口 1.3.2序号(seq) 1.3.3确认序号(ack) 1.3.4数据偏移 1.3.5标志位 1.3.6窗口 1.3.7校验和 1.3.8紧急指针 2、TCP的可靠性 2.1 TCP可靠性的保障 2.2排序机…...

Hadoop大数据应用:Linux 部署 HDFS 分布式集群

目录 一、实验 1.环境 2.Linux 部署 HDFS 分布式集群 3.Linux 使用 HDFS 文件系统 二、问题 1.ssh-copy-id 报错 2. 如何禁用ssh key 检测 3.HDFS有哪些配置文件 4.hadoop查看版本报错 5.启动集群报错 6.hadoop 的启动和停止命令 7.上传文件报错 8.HDFS 使用命令 一…...

纯 CSS 实现文字换行环绕效果

实现效果 实现代码 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8" /><meta name"viewport" content"widthdevice-width, initial-scale1.0" /><title>Document</title><…...

【爬虫逆向】Python逆向采集猫眼电影票房数据

进行数据抓包&#xff0c;因为这个网站有数据加密 !pip install jsonpathCollecting jsonpathDownloading jsonpath-0.82.2.tar.gz (10 kB)Preparing metadata (setup.py) ... done Building wheels for collected packages: jsonpathBuilding wheel for jsonpath (setup.py) .…...

解析服务器下载速度:上行、下行与带宽之谜

在日常使用中&#xff0c;我们经常会遇到从服务器下载内容速度忽快忽慢的情况&#xff0c;即便服务器的硬件配置如4核CPU、8GB内存和12Mbps的带宽看似足够。为何会出现这种现象&#xff1f;这背后涉及到网络中的上行、下行以及带宽等关键概念。本文旨在揭开这些术语背后的含义&…...

计算机网络的概念

目录 <计算机网络的定义> <计算机网络的形成与发展> 1.第一阶段远程联机阶段----60年代以前: 2.第二阶段多机互联网络阶段----60年代中期: 3.第三阶段标准化网络阶段----70年代末: 4.第四阶段网络互联与高速网络阶段一90年代: <计算机网络的未来--下一代…...

MATLAB中的脚本和函数有什么区别?

MATLAB中的脚本和函数是两种不同的代码组织方式&#xff0c;它们在结构、功能和使用方式上有显著的区别。以下是对这两种方式的详细解释&#xff0c;总计约2000字。 一、MATLAB脚本 MATLAB脚本是一种包含多条MATLAB命令的文件&#xff0c;这些命令按照在文件中的顺序依次执行…...

从电影《沙丘》说起——对人工智能的思考

正文 从《沙丘》开始说起 之前看《沙丘》电影&#xff0c;里面有一类角色叫门泰特&#xff0c;这类人大脑可以飞快地运算&#xff0c;在电影设定里是替换人工智能、机器运算的存在。男主保罗也是这类型的人&#xff0c;但他可能基因更强大&#xff0c;吸食了香料后&#xff0…...

使用Python进行自然语言处理(NLP):NLTK与Spacy的比较【第133篇—NLTK与Spacy】

&#x1f47d;发现宝藏 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。【点击进入巨牛的人工智能学习网站】。 使用Python进行自然语言处理&#xff08;NLP&#xff09;&#xff1a;NLTK与Spacy的比较 自…...

学习笔记--在线强化学习与离线强化学习的异同(3)

这篇博文很多部分仅代表个人学习观点&#xff0c;欢迎大家与我一起讨论 强化学习与离线强化学习的区别 强化学习和离线强化学习都是机器学习的分支&#xff0c;主要用于训练智能体以在不断尝试和错误的过程中学习如何最大化累积奖励。它们之间的主要区别在于数据的获取方式和训…...

使用Thymeleaf导出PDF,页眉插入图片与内容重叠?

CSS 打印分页功能 需求&#xff1a;打印 在第一页的内容被挤到第二页的时候&#xff0c;又想每一页页头都有相同的样式&#xff0c;使用页眉。 问题&#xff1a;第二页的内容与页眉重叠了&#xff1f; 查各路找出的原因&#xff1a;header 页眉不占空间 解决&#xff1a;不…...

python网络编程:通过socket实现TCP客户端和服务端

目录 写在开头 socket服务端&#xff08;基础&#xff09; socket客户端&#xff08;基础&#xff09; 服务端实现&#xff08;可连接多个客户端&#xff09; 客户端实现 数据收发效果 写在开头 近期可能会用python实现一些网络安全工具&#xff0c;涉及到许多关于网络…...

论文阅读——RSGPT

RSGPT: A Remote Sensing Vision Language Model and Benchmark 贡献&#xff1a;构建了一个高质量的遥感图像描述数据集&#xff08;RSICap&#xff09;和一个名为RSIEval的基准评估数据集&#xff0c;并在新创建的RSICap数据集上开发了基于微调InstructBLIP的遥感生成预训练…...

长连接技术

个人学习记录&#xff0c;欢迎指正 1.轮询 1.1 轮询的形式 短连接轮询 前端每隔一段时间向服务端发起一次Http请求来获取数据。 const shortPolling () > { const intervalHandler setInterval(() > {fetch(/xxx/yyy).then(response > response.json()).then(respo…...

供电系统分类详解

一、供电系统分类 电力供电系统一般有5种供电模式&#xff0c;常用的有&#xff1a;IT系统&#xff0c;TT系统&#xff0c;TN系统&#xff0c;其中TN系统又可以分为TN-C&#xff0c;TN-S&#xff0c;TN-C-S。 1、TN-C系统&#xff08;三相四线制&#xff09; 优点: 该系统中…...

基于centos7的k8s最新版v1.29.2安装教程

k8s概述 Kubernetes 是一个可移植、可扩展的开源平台&#xff0c;用于管理容器化的工作负载和服务&#xff0c;可促进声明式配置和自动化。 Kubernetes 拥有一个庞大且快速增长的生态&#xff0c;其服务、支持和工具的使用范围相当广泛。 Kubernetes 这个名字源于希腊语&…...

【赠书第20期】AI绘画与修图实战:Photoshop+Firefly从入门到精通

文章目录 前言 1 入门篇&#xff1a;初识Photoshop与Firefly 2 进阶篇&#xff1a;掌握Photoshop与Firefly的核心技巧 3 实战篇&#xff1a;运用Photoshop与Firefly进行创作 4 精通篇&#xff1a;提升创作水平&#xff0c;拓展应用领域 5 结语 6 推荐图书 7 粉丝福利 前…...

如何在并行超算云上玩转PWmat③:使用Q-Flow提交计算的案例演示

3月的每周二下午14:00我们将会在并行直播间为大家持续带来线上讲座。前面两期我们分享了”PWmat特色功能和应用“以及“如何在并行超算云平台使用PWmat计算软件”主题讲座&#xff0c;回看视频和PPT已上传至B站”龙讯旷腾“账号内。 本周张持讲师将继续带着大家手把手上机教学…...

html5cssjs代码 017样式示例

html5&css&js代码 017样式示例 一、代码二、解释 这段HTML代码定义了一个网页的基本结构&#xff0c;包括头部、主体和尾部。在头部中&#xff0c;设置了网页标题、字符编码和样式。主体部分包含一个标题和一个表格&#xff0c;表格内分为两个单元格&#xff0c;左侧为…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

vue3+vite项目中使用.env文件环境变量方法

vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量&#xff0c;这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

【笔记】WSL 中 Rust 安装与测试完整记录

#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统&#xff1a;Ubuntu 24.04 LTS (WSL2)架构&#xff1a;x86_64 (GNU/Linux)Rust 版本&#xff1a;rustc 1.87.0 (2025-05-09)Cargo 版本&#xff1a;cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...

Leetcode33( 搜索旋转排序数组)

题目表述 整数数组 nums 按升序排列&#xff0c;数组中的值 互不相同 。 在传递给函数之前&#xff0c;nums 在预先未知的某个下标 k&#xff08;0 < k < nums.length&#xff09;上进行了 旋转&#xff0c;使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...

离线语音识别方案分析

随着人工智能技术的不断发展&#xff0c;语音识别技术也得到了广泛的应用&#xff0c;从智能家居到车载系统&#xff0c;语音识别正在改变我们与设备的交互方式。尤其是离线语音识别&#xff0c;由于其在没有网络连接的情况下仍然能提供稳定、准确的语音处理能力&#xff0c;广…...