【数据结构】二叉树———Lesson2

Hi~！这里是奋斗的小羊，很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~~
💥💥个人主页：奋斗的小羊
💥💥所属专栏：C语言

🚀本系列文章为个人学习笔记，在这里撰写成文一为巩固知识，二为展示我的学习过程及理解。文笔、排版拙劣，望见谅。

目录

  • 前言
  • 一、TOP-K问题
  • 二、二叉树的链式结构
    • 2.1前中后序遍历
    • 2.2节点个数
    • 2.3叶子个数
    • 2.4高度 / 深度
    • 2.5第K层节点数
    • 2.6查找值为x的节点
    • 2.7相关OJ题
  • 总结

前言

在TOP-K问题中有一种方法能在占用很小空间的情况下高效地找出最大或最小的前K个数。
在上篇文章介绍树时说树是递归定义的，因此二叉树的遍历、二叉树的搜索、二叉树的深度、高度、节点数、二叉树的路径求解等问题，基本都会用递归解决。

一、TOP-K问题

接上篇文章，我们简单地了解了TOP-K问题，介绍了如何从比较大的数据量中快速找出最大（最小）的前K个数据。

| 方法一：

用这些较大的数据量建堆，循环Top、Pop，找出最大（最小）的前K个数。

但是这个方法有个致命缺陷，它只适合数据量还不是特别大的情况，因为如果数据量非常大时我们还建堆的话，这对空间的消耗是很大的，那我们就要想别的办法了。如果数据海量，但我们现在只有1GB的内存，直接建堆显然行不通。

| 方法二：

将这海量数据分成合适的若干份分别建堆，找出每份中的最大（最小）的前K的数，再将这些数建堆，循环Top、Pop K次就能找到最大（最小）的前K个数。

但是这个方法也不是特别好，因为1GB的内存还是比较大的，假如这个问题非要搞我们，它有海量的数据但是只给我们1KB的内存，甚至更狠一点只给我们100Byte的空间，这时候方法二就显得力不从心了，因为这个若干份将会非常大，非常不理想。

| 方法三：

先从这海量数据中拿出前K个数建小堆（大堆），然后再不断拿出剩下的数和堆顶数据比较，如果大（小）于堆顶就替换掉堆顶，再向下调整保证堆成立，当这海量的数据全都比完后，留在堆内的数就是这海量数据中最大（最小）的前K个数。

这个方法需要注意的是如果要求我们找最大的前K个数要建小堆，最小的前K个数要建大堆。当然K也不能太大，要是我们现在可用的内存连这K个数都装不下那就有点扯淡了。

方法三代码如下：

void test1()
{FILE* pf = fopen("data.txt", "w");if (pf == NULL){perror("fopen fail");return;}//产生随机的100000个数存到磁盘中for (int i = 0; i < 100000; i++){//rand函数产生的随机数有重复，+i减少重复的数int ret = rand() + i;fprintf(pf, "%d\n", ret);}fclose(pf);pf = NULL;
}void test2()
{FILE* pf = fopen("data.txt", "r");if (pf == NULL){perror("fopen fail");return;}int k = 0;scanf("%d", &k);int* arr = (int*)malloc(k * sizeof(int));if (arr == NULL){perror("malloc fail");return;}//读取k个数到数组中for (int i = 0; i < k; i++){fscanf(pf, "%d", &arr[i]);}//k个数建小堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, i, k);}//读取剩下的数与堆顶比较int ret = 0;while (fscanf(pf, "%d", &ret) > 0){if (ret > arr[0]){arr[0] = ret;AdjustDown(arr, 0, k);}}//留在堆内的数就是所有数中最大的前K个数for (int i = 0; i < k; i++){printf("%d ", arr[i]);}fclose(pf);pf = NULL;
}int main()
{srand((unsigned int)time(NULL));test1();test2();return 0;
}

这里又有个问题，我们怎么知道这K个数就是最大的前K个数呢？如何验证？

为了验证我们这个程序有没什么问题，这里有个简单的小方法，我们可以手动地在已经产生了100000个随机数的文件中修改K个使它们一定是最大的K个数，然后再运行程序看看是否有问题。运行前先把产生随机数的函数屏蔽掉。

在这里插入图片描述

可以看到此时打印出来的10个数就是我们故意放进去的最大的10个数。

二、二叉树的链式结构

在上篇文章中简单地了解了二叉树的链式存储，即用链表来表示一棵二叉树，用链表来指示元素的逻辑关系。
通常每个节点由三个域组成，一个数据域和两个指针域，分别用左指针和右指针来指向左孩子和右孩子。链式结构又分为二叉链和三叉链，当前我们学习的是二叉链，三叉链会在后面的学习中学到。

typedef int BTDataType;
//二叉链
typedef struct BinTreeNode
{struct BinTreeNode* pleft;//左孩子struct BinTreeNode* pright;//右孩子BTDataType data;
}BTNode;

二叉树的创建方式比较复杂，后续我们会深入学习，这里为了测试下面将要介绍的二叉树遍历，我们先手动创建一棵链式二叉树。

#define  _CRT_SECURE_NO_WARNINGS#include <stdio.h>
#include <stdlib.h>typedef int BinTreeType;typedef struct BinaryTreeNode
{BinTreeType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;BTNode* BuyNode(BinTreeType x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail");return;}node->data = x;node->left = node->right = NULL;return node;
}BTNode* GreatBinaryTree()
{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;
}int main()
{BTNode* root = GreatBinaryTree();return 0;
}

2.1前中后序遍历

在这里插入图片描述

二叉树的操作离不开树的遍历，按照规则，二叉树的遍历有：前序、中序、后序（前根序、中根序、后根序）的递归结构遍历。

  • 前序： 访问顺序为根节点、左子树、右子树

A B D N N N C E N N F N N

  • 中序： 访问顺序为左子树、根节点、右子树

N D N B N A N E N C N F N

  • 后序： 访问顺序为左子树、右子树、根节点

N N D N B N N E N N F C A

代码实现：

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

请添加图片描述
请添加图片描述
请添加图片描述

2.2节点个数

如何计算节点的个数呢？可能有同学会想到用上面学到的前中后序遍历二叉树++计数：

int TreeSize(BTNode* root)
{int size = 0;if (root == NULL){printf("N ");return;}size++;printf("%d ", root->data);TreeSize(root->left);TreeSize(root->right);return size;
}

但这样是行不通的，因为上面我们前中后序遍历二叉树是递归实现的，每一次递归函数栈帧内都重新定义了size。
那可能又有同学说用static修饰size不就好了，但是这个方法也不太能行得通。

int TreeSize(BTNode* root)
{static int size = 0;if (root == NULL){printf("N ");return;}size++;printf("%d ", root->data);TreeSize(root->left);TreeSize(root->right);return size;
}

请添加图片描述

可以看到用static修饰后这个方法也只能计算一次，因为static修饰的变量在静态区，程序运行结束才销毁。
我们可以考虑用递归的思想解决这个问题。因为一个二叉树的节点个数是左子树节点个数+右子树节点个数+1（根节点），左子树的节点个数又是它的左子树节点个数+右子树节点个数+1（根节点），所以我们可以用递归解决这个问题。

在这里插入图片描述

递归计算节点数代码如下：

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

2.3叶子个数

如果节点的左指针和右指针都指向NULL，那这个节点就是叶子，如果节点为空就返回0。

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

2.4高度 / 深度

一个二叉树的高度是左子树高度和右子树高度大的一个再加一，左子树的高度又是它的左子树高度和右子树高度大的一个再加一，这显然又是一个递归问题。

int TreeHight(BTNode* root)
{ if (root == NULL){return 0;}int lefthight = TreeHight(root->left);int leftright = TreeHight(root->right);return lefthight > leftright ? lefthight + 1 : leftright + 1;
}

这里需要注意要用一个值来接收左右子树的高度，不要写成下面这种：

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

虽然下面这种看起来更简单，但是当二叉树的深度比较深时，这个代码的时间消耗是非常非常非常大的。

2.5第K层节点数

求第K层的节点数，就是相对于第二层来说求第K-1层节点数，相对于第三层来说求第K-2层节点数，也可以用递归解决，当节点不为空且K==1时返回1。

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

2.6查找值为x的节点

查找值为x的节点可以用前序遍历二叉树解决，当节点值等于x时返回节点指针，如果不等于则查找左子树，如果左子树找到了就返回节点指针，如果没找到（返回NULL）则查找右子树，不管找没找到都返回右子树的返回值。

BTNode* TreeFind(BTNode* root, BinTreeType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode* node = TreeFind(root->left, x);if (node)//如果为空则左子树没找到{return node;}return TreeFind(root->right, x);
}

2.7相关OJ题

Leetcode—单值二叉树

bool isUnivalTree(struct 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);
}

Leetcode—相同的树

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);
}

Leetcode—对称二叉树

bool _isSymmetric(struct TreeNode* p, struct TreeNode* q) {if (p && q){if (p->val != q->val){return false;}return _isSymmetric(p->left, q->right) && _isSymmetric(p->right, q->left);}if (p == q){return true;}return false;
}
bool isSymmetric(struct TreeNode* root) {if (root == NULL){return true;}return _isSymmetric(root->left, root->right);
}

Leetcode—二叉树的前序遍历

int TreeSize(struct TreeNode* root)
{if (root == NULL){return 0;}return TreeSize(root->left) + TreeSize(root->right) + 1;
}
void PreOrder(struct TreeNode* root, int* arr, int* pi)
{if (root == NULL){return;}//每次递归都会建立新的栈帧空间，不同的栈帧空间内相同的变量之间互不影响，//而我们需要的是每次函数递归都要改变下标，所以需要传地址。arr[(*pi)++] = root->val;PreOrder(root->left, arr, pi);PreOrder(root->right, arr, pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize = TreeSize(root);//在开辟空间前可以先算出节点个数以开辟合适的空间int* arr = (int*)malloc(*returnSize * sizeof(int));int i = 0;PreOrder(root, arr, &i);return arr;
}

函数每次递归都会建立独立的栈帧空间，同一个变量在不同的栈帧空间中互不影响，如果我们想让某一变量在每次函数递归都改变，则应该传变量地址。
Leetcode—另一棵树的子树

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);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){if (root == NULL){return false;}if (root->val == subRoot->val && isSameTree(root, subRoot)){return true;}return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

我们知道二叉树是由根节点和左右子树构成，因此我们可以先判断两个根节点是否相等，如果相等且左右子树也相等则两个二叉树互为子树；如果根节点不相等则递归判断左子树或右子树。

总结

  • 二叉树由根节点、左子树和右子树组成，每个子树也是一个二叉树。递归方法很适合处理这种具有递归结构的数据结构，例如通过递归函数不断地遍历左右子树。递归的思想可以帮助我们分解复杂问题，将大问题转化为相同结构的小问题，从而简化解题过程。

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

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

相关文章

网安小贴士（17）认证技术原理应用

网安小贴士（17）认证技术原理应用

前言 认证技术原理及其应用是信息安全领域的重要组成部分&#xff0c;涉及多个方面&#xff0c;包括认证概念、认证依据、认证机制、认证类型以及具体的认证技术方法等。以下是对认证技术原理及应用的详细阐述&#xff1a; 一、认证概述 1. 认证概念 认证是一个实体向另一个实…
阅读更多...
【初阶数据结构】掌握二叉树遍历技巧与信息求解：深入解析四种遍历方法及树的结构与统计分析

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

初阶数据结构相关知识点可以通过点击以下链接进行学习一起加油&#xff01;时间与空间复杂度的深度剖析深入解析顺序表:探索底层逻辑深入解析单链表:探索底层逻辑深入解析带头双向循环链表:探索底层逻辑深入解析栈:探索底层逻辑深入解析队列:探索底层逻辑深入解析循环队列:探索…
阅读更多...
Chromium CI/CD 之Jenkins实用指南2024 - 常见的构建错误（六）

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: 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

Uniapp 组件 props 属性为 undefined

问题 props 里的属性值都是 undefined 代码 可能的原因 组件的名字要这样写&#xff0c;这个官方文档有说明
阅读更多...
【转盘案例-弹框-修改Bug-完成 Objective-C语言】

【转盘案例-弹框-修改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计算机网络

【中项】系统集成项目管理工程师-第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 音频

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

Linux网络——TcpServer

一、UDP 与 TCP 在现实生活中&#xff0c;Udp 类似于发传单&#xff0c;Tcp 类似于邮局的挂号信服务。 1.1 UDP&#xff08;用户数据报协议&#xff09; 无连接&#xff1a;发放传单时&#xff0c;你不需要提前和接受传单的人建立联系&#xff0c;直接把传单发出去。不可靠&…
阅读更多...
Spring Boot1（概要 入门 Spring Boot 核心配置 YAML JSR303数据校验 ）

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 微信小程序：仿知乎日报详情页设计及实现

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

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

使用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

解决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）

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

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

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

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

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.什么…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023