【初阶数据结构】掌握二叉树遍历技巧与信息求解:深入解析四种遍历方法及树的结构与统计分析

在这里插入图片描述

初阶数据结构相关知识点可以通过点击以下链接进行学习一起加油!
时间与空间复杂度的深度剖析深入解析顺序表:探索底层逻辑深入解析单链表:探索底层逻辑深入解析带头双向循环链表:探索底层逻辑深入解析栈:探索底层逻辑
深入解析队列:探索底层逻辑深入解析循环队列:探索底层逻辑树与二叉树:从零开始的奇幻之旅理解堆的特性与应用:深入探索完全二叉树的独特魅力

本篇将介绍掌握二叉树的遍历和信息获取方法,有助于我们更好地理解树的结构与统计分析,为接下来学习AVL树与红黑树等高阶数据结构打下基础。对于最后面关于二叉树的特性,需要理解掌握在遇到相关题目可以直接套用。

请添加图片描述
Alt

🌈个人主页:是店小二呀
🌈C语言笔记专栏:C语言笔记
🌈C++笔记专栏: C++笔记
🌈初阶数据结构笔记专栏: 初阶数据结构笔记

🌈喜欢的诗句:无人扶我青云志 我自踏雪至山巅
请添加图片描述

文章目录

  • 一、快速搭建二叉树
  • 二、二叉树组成结构
  • 三、二叉树的遍历
    • 3.1 三种常见遍历(前序/中序/后序遍历)
    • 3.2 层序遍历
  • 四、求二叉树相关信息
    • 4.1 二叉树节点个数
    • 4.2 二叉树叶子节点个数
    • 4.3 求这个棵树的高度
    • 4.4 二叉树第k层节点个数
    • 4.5 二叉树查找值为x的节点
    • 4.5 单值二叉树
    • 4.6 相同的树
    • 4.7 树的销毁(后序)
  • 五、二叉树的性质

一、快速搭建二叉树

为了方便我们更快地学习二叉的基本操作,这里直接手动搭建一颗二叉树。不仅如此,在做二叉树相关题目时,由于部分原因做题平台不支持普通用户使用调试功能,可以快速搭建二叉树在本地编译器上进行调试相关操作

typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType _data;struct BinaryTreeNode* _left;struct BinaryTreeNode* _right;
}BTNode;BTNode* BuyNode(BTDataType x)
{BTNode* tmp = (BTNode*)malloc(sizeof(BTNode));if (tmp == NULL){// 处理内存分配失败的情况// 可以选择报错、退出程序或者其他适当的处理方式exit(EXIT_FAILURE)};  // 举例:退出程序tmp->_data = x;tmp->_left = NULL;tmp->_right = NULL;return tmp;
}BTNode* CreatBinaryTree()
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);node1->_left = node2;node1->_right = node4;node2->_left = node3;node4->_left = node5;node4->_right = node6;return node1;
}

二、二叉树组成结构

二叉树大致分为两种

  • 空树
  • 非空:根节点,的左子树,右子树(左右子树可能为空树)

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

在这里插入图片描述
从概念中可以看出来,根据不同节点可以划分多个子树,对此二叉树定义是递归式的,因此后续基本操作都是按照概念实现的。

三、二叉树的遍历

学习二叉树的结构,最简单的方式就是遍历,遍历是二叉树上最重要的运算之一,也是二叉树上进行其他运算的基础。二叉树遍历按照某种特定的规则,依次对二叉树中的节点进行对应的操作,并且每个节点只操作一次。

在这里插入图片描述

3.1 三种常见遍历(前序/中序/后序遍历)

根据规定,访问顺序左子树是先于右子树,导致了二叉树遍历有三种递归式结构前序/中序/后序的遍历,被访问节点必是某子树的根。根据英文缩写可以通过N、L、R表示根、左子树、右子树,对此NLR、LNR和LRN称为先根遍历、中根遍历和后根遍历。

在这里插入图片描述

根据例子更好的理解其中的含义,不然很难get到其中的真谛。尝试下前序/中序/后序,写出访问顺序(空也会访问,用N代表)

在这里插入图片描述

前序:123NNN45NN6NN
中序:N3N2N1N5N4N6N
后序:NN3N2NN5NN641

过程解析:

达到1号节点为根,访问左子树;达到2号节点为根;访问左子树;达到3号节点为根;访问左子树;达到为空位置返回,访问根(3号),访问右子树;达到空位置,以3号为根子树访问完;以2号为根左子树访问完,访问根(2号);以此类推直到遍历完毕(按照这种方式,剩下两种遍历也是很好掌握的)

在这里插入图片描述

3.2 层序遍历

除了先序遍历、中序遍历、后序遍历外,还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1,层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根节点,然后从左到右访问第2层上的节点,接着是第三层的节点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历

在这里插入图片描述

void LevelOrder(BTNode* root)
{// 0. 声明队列queue<TreeNode*> q;// 1. 将根节点加入队列q.push(root);// 2. 遍历队列中每个节点while (!q.empty()) {TreeNode* cur = q.front();q.pop();// 3. 记录当前节点值vec.push(cur->val);// 4. 将左右孩子放入队列q.push(cur->left);q.push(cur->right);}
}

这里使用C++语法直接调用库里面的queue容器,直接主要是分享思路,语法看不懂没有关系。

在这里插入图片描述

使用场景:判断是否为完全二叉树(C++代码)。

// 判断是否为完全二叉树
bool isCompleteTree(TreeNode* root) {if (root == nullptr) {return true;}queue<TreeNode*> q;q.push(root);bool foundNull = false;while (!q.empty()) {TreeNode* currentNode = q.front();q.pop();if (currentNode == nullptr) {foundNull = true;} else {if (foundNull) {return false;}q.push(currentNode->left);q.push(currentNode->right);}}return true;
}

大致思路:完全二叉树特性是从左到右是连续的,该特性保证了最后一个位置为空,那么判断是否为完全二叉树只需要在遇到空节点之后不会再出现非空节点即可。可以使用层序遍历(层序遍历也是适用于普通二叉树)如果队列出空,但是队列不为空说明不是完全二叉树.。

四、求二叉树相关信息

4.1 二叉树节点个数

瑕疵版本:使用静态局部变量进行计数

int TreeSize(TreeNode* root)
{static int size = 0;if (root == NULL){return 0;}++size;TreeSize(root->left);TreeSize(root->right);return size;
}

瑕疵版本:使用全局变量进行计数

int size = 0;
void TreeSize(TreeNode* root)
{if (root == NULL)return;++size;TreeSize(root->left);TreeSize(root->right);
}

方法分析:无论是使用静态还是全局变量,使得生命周期不会受到函数栈帧销毁的影响,可以解决求节点个数的问题。问题在于静态还是全局变量只能被定义一次,这就意味着第一次计算出来的结果是正确的,那么第二次的结果会延用上一次变量存储的值,不会清空重新计数,程序结束(以上一次值为基准)导致结果错误。

修正版本:画图分析
在这里插入图片描述

int BinaryTreeSize(TreeNode* root)
{if (root == NULL) return 0;return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

过程解析:这里使用分治思想,可以将求整课树节点个数分为求左右子树节点个数加上根节点之和,不断划分,去看最几步过程去递推和归并去发现规律。比如:以3为根节点,得到左右子树为空返回结果为0,返回给2节点的结果就是0 + 0 + 1(1为根节点)返回结果为:以2为根节点左子树的节点个数BinaryTreeSize(root->left)等于BinaryTreeSize(root->left-left) + BinaryTreeSize(root->left->right) + 1(如果觉得这样子很难理解,建议画图去研究递归的过程)。

4.2 二叉树叶子节点个数

在这里插入图片描述

int BinaryTreeLeafSize(TreeNode* root)
{if (root == NULL) return 0;if (root->left == NULL && root->right == NULL) return 1;return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

过程解析这里也是使用了分治的思想,求整棵树叶子节点个数之和分为求左右子树叶子节点个数之后。根据题目要求访问三种情况:空节点返回0,不是空节点,属于叶子节点返回1,不是空节点也不是叶子节点,使用分治等于左右子树叶子之后。

4.3 求这个棵树的高度

在这里插入图片描述

过程解析这里也是使用了分治的思想,求整棵树高度分为求左右子树高度之间最大的高度再+1

瑕疵版本

int TreeHeight(TreeNode* root)
{if (root == NULL) return 0;return TreeHeight(root->left) > TreeHeight(root->right) ?TreeHeight(root->left) + 1 : TreeHeight(root->right) + 1;
}

在这里插入图片描述

由于TreeHeight(root->left) > TreeHeight(root->right) 的比较是不会记录结果,需要高的那一份再次递归调用,因此多次递归调用 TreeHeight(root->left)TreeHeight(root->right),造成重复计算。

修正版本:(记录得到目前高度进行比较)

int TreeHeight(TreeNode* root) 
{if (root == NULL) return 0;int leftHeight = TreeHeight(root->left);int rightHeight = TreeHeight(root->right);return max(leftHeight, rightHeight) + 1;
}

4.4 二叉树第k层节点个数

在这里插入图片描述

int TreeLevelK(TreeNode* root, int k)
{assert(k > 0);if (root == NULL)return 0;if (k == 1)return 1;return TreeLevelK(root->left, k-1)+ TreeLevelK(root->right, k-1);
}

过程解析:跟求整棵树节点个数问题是差不多,主要差异在于对于范围的限制,无非添加一个变量(临时变量)进行递归,每一层的k值是不同的,到达一定条件停止返回如果为空返回0,如果为非空返回1,都建立在k>0的前提下。

4.5 二叉树查找值为x的节点

瑕疵版本:在这里插入图片描述

TreeNode* TreeFind(TreeNode* root, BTDataType x)
{if (root == NULL) return NULL;if (root->data == x) return root;TreeFind(root->left, x);TreeFind(root->right, x);return NULL;
}

过程解析:return 是return 上一层的,不是直接到最外层的。这里导致了没有接受到返回值传出。

修正版本

TreeNode* TreeFind(TreeNode* root, BTDataType x)
{if (root == NULL) return NULL;if (root->data == x) return root;TreeNode* ret1 = TreeFind(root->left, x);if (ret1) return ret1;TreeNode* ret2 =  TreeFind(root->right, x);if (ret2) return ret2;return NULL;
}

4.5 单值二叉树

在这里插入图片描述

bool isUnivalTree(TreeNode* root)
{if(root == NULL) return true;if(root->left && root->left->val != root->val)return false;if(root->right && root->right->val != root->val)return false;return isUnivalTree(root->left) && isUnivalTree(root->right);
}

4.6 相同的树

在这里插入图片描述

bool isSameTree(struct TreeNode* p, struct TreeNode* q) 
{//都为空if(p == NULL && q == NULL) return true;//其中一个为空(前面排除了都为空的情况)if(p == NULL || q == NULL) return false;//都不为空且不相等if(p->val != q->val) return false;return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}

4.7 树的销毁(后序)

在这里插入图片描述

五、二叉树的性质

二叉树的性质

  1. 若规定根节点的层数为1,则一棵非空二叉树的第i层上最多有2(i-1)个结点

  2. 若规定根节点的层数为1,则深度为h的二叉树的最大结点数是2h-1

  3. 若规定根节点的层数为1,具有n个结点的满二叉树的深度,h= log2(n + 1)(ps: 是log以2为底,n+1为对数)

  4. 对任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为n2,则有 n0 = n2 + 1

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传


以上就是本篇文章的所有内容,在此感谢大家的观看!这里是店小二初阶数据结构笔记,希望对你在学习初阶数据结构中有所帮助!
请添加图片描述

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

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

相关文章

Chromium CI/CD 之Jenkins实用指南2024 - 常见的构建错误(六)

1. 引言 在前一篇《Chromium CI/CD 之 Jenkins - 发送任务到Ubuntu&#xff08;五&#xff09;》中&#xff0c;我们详细讲解了如何将Jenkins任务发送到Ubuntu节点执行&#xff0c;并成功验证了文件的传输和回传。这些操作帮助您充分利用远程节点资源&#xff0c;提升了构建和…

CrossKD: Cross-Head Knowledge Distillation for Dense Object Detection

CrossKD&#xff1a;用于密集目标检测的交叉头知识蒸馏 论文链接&#xff1a;https://arxiv.org/abs/2306.11369v2 项目链接&#xff1a;https://github.com/jbwang1997/CrossKD Abstract 知识蒸馏(Knowledge Distillation, KD)是一种有效的学习紧凑目标检测器的模型压缩技术…

Uniapp 组件 props 属性为 undefined

问题 props 里的属性值都是 undefined 代码 可能的原因 组件的名字要这样写&#xff0c;这个官方文档有说明

【转盘案例-弹框-修改Bug-完成 Objective-C语言】

一、我们来看示例程序啊 1.旋转完了以后,它会弹一个框,这个框,是啥, Alert 啊,AlertView 也行, AlertView,跟大家说过,是吧,演示过的啊,然后,我们就用iOS9来做了啊,完成了以后,我们要去弹一个框, // 弹框 UIAlertController *alertController = [UIAlertContr…

爬虫案例(读书网)(下)

上篇链接&#xff1a; CSDN-读书网https://mp.csdn.net/mp_blog/creation/editor/139306808 可以看见基本的全部信息&#xff1a;如(author、bookname、link.....) 写下代码如下&#xff1a; import requests from bs4 import BeautifulSoup from lxml import etreeheaders{…

【中项】系统集成项目管理工程师-第2章 信息技术发展-2.1信息技术及其发展-2.1.1计算机软硬件与2.1.2计算机网络

前言&#xff1a;系统集成项目管理工程师专业&#xff0c;现分享一些教材知识点。觉得文章还不错的喜欢点赞收藏的同时帮忙点点关注。 软考同样是国家人社部和工信部组织的国家级考试&#xff0c;全称为“全国计算机与软件专业技术资格&#xff08;水平&#xff09;考试”&…

内部类+图书管理系统

内部类图书管理系统 1. 实例内部类1.1 实例内部类的结构1.2 实例内部类的一些问题1.2.1 如何在main中创建实例内部类对象&#xff1f;1.2.2 内部类成员变量被static修饰问题&#xff1f;1.2.3 内部类和外部类变量重名的调用问题&#xff1f;1.2.4 外部类访问内部类变量的问题 2…

HiFi-GAN——基于 GAN 的声码器,能在单 GPU 上生成 22 KHz 音频

拟议的 HiFiGAN 可从中间表征生成原始波形 源码地址&#xff1a;https://github.com/NVIDIA/DeepLearningExamples 论文地址&#xff1a;https://arxiv.org/pdf/2010.05646.pdf 研究要点包括 **挑战&#xff1a;**基于 GAN 的语音波形生成方法在质量上不及自回归模型和基于流…

Linux网络——TcpServer

一、UDP 与 TCP 在现实生活中&#xff0c;Udp 类似于发传单&#xff0c;Tcp 类似于邮局的挂号信服务。 1.1 UDP&#xff08;用户数据报协议&#xff09; 无连接&#xff1a;发放传单时&#xff0c;你不需要提前和接受传单的人建立联系&#xff0c;直接把传单发出去。不可靠&…

Spring Boot1(概要 入门 Spring Boot 核心配置 YAML JSR303数据校验 )

目录 一、Spring Boot概要 1. SpringBoot优点 2. SpringBoot缺点 二、Spring Boot入门开发 1. 第一个SpringBoot项目 项目创建方式一&#xff1a;使用 IDEA 直接创建项目 项目创建方式二&#xff1a;使用Spring Initializr 的 Web页面创建项目 &#xff08;了解&#…

低代码中间件学习体验分享:业务系统的创新引擎

前言 星云低代码平台介绍 星云低代码中间件主要面向企业IT部门、软件实施部门的低代码开发平台&#xff0c;无需学习开发语言/技术框架&#xff0c;可视化开发PC网页/PC项目/小程序/安卓/IOS原生移动应用&#xff0c;低门槛&#xff0c;高效率。针对企业研发部门人员少&#…

Vue3 + uni-app 微信小程序:仿知乎日报详情页设计及实现

引言 在移动互联网时代&#xff0c;信息的获取变得越来越便捷&#xff0c;而知乎日报作为一款高质量内容聚合平台&#xff0c;深受广大用户喜爱。本文将详细介绍如何利用Vue 3框架结合微信小程序的特性&#xff0c;设计并实现一个功能完备、界面美观的知乎日报详情页。我们将从…

使用Python和Pandas进行数据分析:入门与实践

目录 引言 准备工作 安装Python与Pandas 导入Pandas库 Pandas基础 数据结构 创建Series和DataFrame 读取数据 数据探索 查看数据 数据清洗 数据可视化 实战案例&#xff1a;分析销售数据 引言 在当今数据驱动的时代&#xff0c;数据分析已成为各行各业不可或缺的…

数据结构(单链表算法题)

1.删除链表中等于给定值 val 的所有节点。 OJ链接 typedef struct ListNode ListNode;struct ListNode {int val;struct ListNode* next; };struct ListNode* removeElements(struct ListNode* head, int val) {//创建新链表ListNode* newhead, *newtail;newhead newtail N…

解决TypeError: __init__() takes 1 positional argument but 2 were given

问题描述&#xff1a; 如下图&#xff0c;在使用torch.nn.Sigmoid非线性激活时报错 源代码&#xff1a; class testrelu(nn.Module):def __init__(self):super().__init__()self.sigmoid Sigmoid()def forward(self, input):output self.sigmoid(input)return outputwriter…

源码分析SpringCloud Gateway如何加载断言(predicates)与过滤器(filters)

我们今天的主角是Gateway网关&#xff0c;一听名字就知道它基本的任务就是去分发路由。根据不同的指定名称去请求各个服务&#xff0c;下面是Gateway官方的解释&#xff1a; Spring Cloud Gateway&#xff0c;其他的博主就不多说了&#xff0c;大家多去官网看看&#xff0c;只…

vue和微信小程序的区别、比较

找到一篇很好的关于vue和小程序之间的理解文章&#xff0c;在此分享一下&#xff1a; 前端 - vue和微信小程序的区别、比较 - 个人文章 - SegmentFault 思否https://segmentfault.com/a/1190000015684864

huawei USG6001v1学习---信息安全概念

目录 1.什么是分布式&#xff1f; 2.什么是云计算&#xff1f; 3.APT攻击 4.安全风险能见度不足 5.常见的一些攻击 6.交换机转发原理&#xff1f; 7.各层攻击类型 7.1链路层&#xff1a; 7.2网络层&#xff1a; 7.3传输层&#xff1a; 7.4应用层&#xff1a; 1.什么…

github上的工程如何下载子模块.gitmodules如何下载指定的模块download submodules开源项目子模块下载externals

github上的工程如何下载子模块.gitmodules如何下载指定的模块download submodules 说明(废话)解决方案无法执行下载子模块无法下载子项目 说明(废话) 今天在编译一个开源库时&#xff0c;该开源库依赖其他项目&#xff0c;并且项目还挺多的&#xff0c;所以有此解决方案 在编…

云微客如何实现低成本快速获客?AI矩阵来传播

目前市场环境较为严峻&#xff0c;超过上千万家实体商家都会遇到线下获客难、线上营销成本高的困境&#xff0c;因此商家急需新的获客方案。 云微客AI矩阵系统基于AIGC的企业短视频矩阵及内容生成、协作、管理平台&#xff0c;通过对多个短视频平台进行营销覆盖&#xff0c;深入…