二叉树链式结构的实现（递归的暴力美学！！）

前言

Hello,小伙伴们。你们的作者菌又回来了，前些时间我们刚学习完二叉树的顺序结构，今天我们就趁热打铁，继续我们二叉树链式结构的学习。我们上期有提到，二叉树的的底层结构可以选为数组和链表，顺序结构我们选用的数组，那我们就不难知道，二叉树的链式结构采用链表为底层结构。

1.实现链式二叉树

用链表来表示一颗二叉树，即用链表来表示元素之间的逻辑关系。通常的方法就是链表中的每一个节点有三个域组成，数据域和左右指针，左右指针分别用来给出该节点左右孩子所在的链接点的存储地址，数据结构的定义如下：

typedef int BTDataType;
// ⼆叉链
typedef struct BinaryTreeNode
{
struct BinaryTreeNode* left; // 指向当前结点左孩⼦
struct BinaryTreeNode* right; // 指向当前结点右孩⼦
BTDataType val; // 当前结点值域
}BTNode;

不要忘记，我们在实现数据结构时，都要先创建三个文件来使测试代码变得更加的方便：

为了更好的演示效果，我们就在Test.c文件中手动的创建几个节点

BTNode* BuyBTNode(int val)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc fail");return NULL;} newnode->val = val;newnode->left = NULL;newnode->right = NULL;return newnode;
}  
BTNode* CreateTree()
{BTNode* n1 = BuyBTNode(1);BTNode* n2 = BuyBTNode(2);BTNode* n3 = BuyBTNode(3);BTNode* n4 = BuyBTNode(4);BTNode* n5 = BuyBTNode(5);BTNode* n6 = BuyBTNode(6);BTNode* n7 = BuyBTNode(7);n1->left = n2;n1->right = n4;n2->left = n3;n4->left = n5;n4->right = n6;n5->left = n7;return n1;}int main()
{BTNode* boot = CreateTree();return 0;
}

我们已经学习了链表，所以这里创建节点的操作我们就不再过多的赘述，因此，boot就是我们创建的这颗树的根节点。

接下来我们来回顾一下二叉树的概念，二叉树分为空树和非空树

 根节点的左子树和右子树分别有是有子树节点、子树节点的左子树和右子树组成，因此二叉树定义是递归式的，后续链式二叉树的操作中基本都是按照该概念实现的！！

1.1前中后序遍历

二叉树的操作离不开树的遍历，我们先来看看二叉树的遍历有哪些方式：

 1.1.1遍历的规则

按照规则，二叉树有：前中后续遍历的规则的递归结构遍历：

前序遍历：访问根节点的操作，发生在遍历其左右子树之前。

访问顺序：根节点、左子树、右子树。

中序遍历：访问根节点的操作发生在遍历其左右节点子树之间（间）

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

后序遍历：访问根节点的操作发生在遍历其左右子树的遍历之后

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

1.1.2 代码的实现

1.1.2.1 前序遍历（PreOrder）
void PreOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
} p
rintf("%d ", root->val);
PreOrder(root->left);
PreOrder(root->right);
}

这里我们就涉及到了之前学习函数栈帧的知识，我们可以通过图来理解

函数递归栈帧图：

 

最终我们测试可得：

可知这符合我们前序遍历的规则，因此我们就成功实现了前序遍历。

实现了前序遍历，其他的两个遍历就简单了，几乎和前序遍历一样，中后序遍历也沿用了递归的思想 

后面大家能否根据上面前序遍历的代码实现中序遍历和后序遍历呢？

大家不妨一试。

1.1.2.2中序遍历（InOrder）
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
} 
InOrder(root->left);
printf("%d ", root->val);
InOrder(root->right);
}

1.1.2.3后序遍历（PostOredr）
v
oid PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
} I
nOrder(root->left);
InOrder(root->right);
printf("%d ", root->val);
}
 

有序他们之间的相似性，在代码上的差异也就只是不同行的代码顺序不一样，但是转化为后面的函数栈帧却又不小的差别。但在本质上，却还是大差不差！！

1.2节点个数以及高度等

1.2.1节点计数

// ⼆叉树结点个数
int BinaryTreeSize(BTNode* root);

我们来想一想，怎样才能达到我们的目的呢？

假设我们现在有这样的二叉树：
 

所以从上所述，我们就能够得出计数代码：

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

 代码测试：

这里我们创建的是这样的二叉树。

可知这样我们就实现了二叉树节点的计数！！

 1.2.2二叉树叶子结点个数

// ⼆叉树叶⼦结点个数
int BinaryTreeLeafSize(BTNode*root)

有了前面写求所有节点个数的经验，其实这个不就不难了：

叶子结点，就是没有子节点的节点。即root->left = root->right = NULL.

所以在这里我们就有两种返回情况，当遍历到NULL时，我们返回0， 当递归到叶子结点时，我们就返回1。借助函数栈帧，就可以进行计数！！

接下来我们来实现一下这个代码：

//求二叉树叶子节点的个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}if (root->left == NULL && root->right == NULL){return 1;}return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

我们可以先提前看看这颗二叉树有多少个叶子结点：

上面我们可以看出一共有3个没有子节点的节点，所以叶子结点的个数就是3

 

1.2.3 二叉树第K层的节点个数

// ⼆叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k);

我们要得到二叉树第K层节点的个数，其实也并不难，我们还是通过画图的方式来解析过程。

假设我们要求的是第三层的节点数：

 代码实现：

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

测试一下：

 1.2.4二叉树的深度/高度

//⼆叉树的深度/⾼度
int BinaryTreeDepth(BTNode* root);

在这里我们可以想出怎样的思路呢？

我们还是要先画图求证：

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

 代码测试：

 从上面我们事先创建的那棵树一样，树的深度为4.所以我们实现了我们的目的。

1.2.5二叉树查找置位x的节点

// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);

这个操作也十分的简单，我们只需要遍历二叉树，找到与目标值相等的节点，我们就将其返回。

我们先看看实现代码：

// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL)return NULL;if (root->val == x)return root;BTNode* left =BinaryTreeFind(root->left, x);if (left)return left;BTNode* right = BinaryTreeFind(root->right, x);if (right)return right;return NULL;
}

在这里我们还是要进行二叉树的左右子树遍历，但是我们为了提高效率，只要在一边找到了符合目标的节点我们就直接返回该节点！！

小伙伴们可以根据上面的知识，自行画出递归栈帧图。

我们来测试以下代码：

可知其成功的找到了，值为6的节点！！ 

1.2.6 二叉树的销毁

// ⼆叉树销毁
void BinaryTreeDestory(BTNode** root);

销毁的逻辑也十分的简单了，通过了递归的操作，我们遍历所有不为NULL的节点并销毁，这里我们就直接写出代码，大家可以自己进行递归栈帧的推理：

void BinaryTreeDestory(BTNode** root)
{if (*root == NULL){return;}BinaryTreeDestory(&((*root)->left));BinaryTreeDestory(&((*root)->right));free(*root);*root = NULL;
}

代码测试：

进行销毁操作：

 2.代码展示

2.1Test.c

#define _CRT_SECURE_NO_WARNINGS 1#include"Tree.h"
BTNode* BuyBTNode(int val)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc fail");return NULL;} newnode->val = val;newnode->left = NULL;newnode->right = NULL;return newnode;
}  
BTNode* CreateTree()
{BTNode* n1 = BuyBTNode(1);BTNode* n2 = BuyBTNode(2);BTNode* n3 = BuyBTNode(3);BTNode* n4 = BuyBTNode(4);BTNode* n5 = BuyBTNode(5);BTNode* n6 = BuyBTNode(6);BTNode* n7 = BuyBTNode(7);n1->left = n2;n1->right = n4;n2->left = n3;n4->left = n5;n4->right = n6;n5->left = n7;return n1;}int main()
{BTNode* root = CreateTree();PreOrder(root);printf("\n");InOredr(root);printf("\n");PostOrder( root);printf("\n");printf("TreeNodeCount: %d\n", BinaryNodeCount(root));printf("leafSize: %d\n", BinaryTreeLeafSize(root));printf("TreeLevelKSize: %d\n", BinaryTreeLevelKSize(root, 3));printf("TreeLevelDepth: %d\n", BinaryTreeDepth(root));BTNode* find = BinaryTreeFind(root, 6);printf("%s ", find == NULL ? "没找到" : "找到了！！");printf("返回节点的值为：%d\n", find->val);BinaryTreeDestory(&root);PostOrder(root);return 0;
}

2.2Tree.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<time.h>
#include<stdbool.h>
typedef int BTDataType;
// ⼆叉链
typedef struct BinaryTreeNode
{struct BinaryTreeNode* left; // 指向当前结点左孩⼦struct BinaryTreeNode* right; // 指向当前结点右孩⼦BTDataType val; // 当前结点值域
}BTNode;
//前序遍历
void PreOrder(BTNode* root);
//中序遍历
void InOredr(BTNode* root);
//后序遍历
void PostOrder(BTNode* root);
//计数二叉树的节点
int BinaryNodeCount(BTNode* root);
//求二叉树叶子节点的个数
int BinaryTreeLeafSize(BTNode* root);
// ⼆叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
//⼆叉树的深度/⾼度
int BinaryTreeDepth(BTNode* root);
// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// ⼆叉树销毁
void BinaryTreeDestory(BTNode** root);

2.3Tree.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Tree.h"
void PreOrder(BTNode* root)
{if (root == NULL){return;}printf("%d ", root->val);PreOrder(root->left);PreOrder(root->right);
}
void InOredr(BTNode* root)
{if (root == NULL)return;InOredr(root->left);printf("%d ", root->val);InOredr(root->right);
}
void PostOrder(BTNode* root)
{if (root == NULL){return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->val);
}
int BinaryNodeCount(BTNode* root)
{if (root == NULL)return 0;return 1 + BinaryNodeCount(root->left) + BinaryNodeCount(root->right);}
//求二叉树叶子节点的个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}if (root->left == NULL && root->right == NULL){return 1;}return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL){return 0;}if (k == 1)return 1;return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
int BinaryTreeDepth(BTNode* root)
{if (root == NULL)return 0;int leftDepth = BinaryTreeDepth(root->left);int rightDepth = BinaryTreeDepth(root->right);return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL)return NULL;if (root->val == x)return root;BTNode* left =BinaryTreeFind(root->left, x);if (left)return left;BTNode* right = BinaryTreeFind(root->right, x);if (right)return right;return NULL;
}
void BinaryTreeDestory(BTNode** root)
{if (*root == NULL){return;}BinaryTreeDestory(&((*root)->left));BinaryTreeDestory(&((*root)->right));free(*root);*root = NULL;
}

好，今天的学习就到这里，我们下期再见，拜拜！！

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

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

相关文章

将YOLOv8模型从PyTorch的.pt格式转换为OpenVINO支持的IR格式

将YOLOv8模型从PyTorch的.pt格式转换为OpenVINO支持的IR格式

OpenVINO是Open Visual Inference & Neural Network Optimization工具包的缩写&#xff0c;是一个用于优化和部署AI推理模型的综合工具包。OpenVINO支持CPU、GPU和NPU设备。 OpenVINO的优势: (1).性能&#xff1a;OpenVINO利用英特尔CPU、集成和独立GPU以及FPGA的强大功能提…
阅读更多...
PHP学习：PHP基础

PHP学习：PHP基础

以.php作为后缀结尾的文件&#xff0c;由服务器解析和运行的语言。 一、语法 PHP 脚本可以放在文档中的任何位置。 PHP 脚本以 <?php 开始&#xff0c;以 ?> 结束。 <!DOCTYPE html> <html> <body><h1>My first PHP page</h1><?php …
阅读更多...
中国象棋 纯网页前端 演示与下载

中国象棋 纯网页前端 演示与下载

https://andi.cn/app/chess/
阅读更多...
3千米以上音视频键鼠延长解决方案：KVM光纤延长器

3千米以上音视频键鼠延长解决方案：KVM光纤延长器

KVM光纤延长器​​​​​​​是什么&#xff1f; KVM光纤延长器是一种使用光纤来传输键盘、视频和鼠标&#xff08;KVM&#xff09;信号的设备&#xff0c;由发送端和接收端组成&#xff0c;一般成对使用。它可以让用户在远离电脑的地方如同在本地一样方便快捷的操作电脑。 KV…
阅读更多...
mysql数据库基础语法（未完）

mysql数据库基础语法（未完）

数据库的超级用户是root 一、注释 &#xff08;1&#xff09;“-- ”减号减号空格 注意不要省略空格 &#xff08;2&#xff09;“#” 井号 二、数据库操作 1、创建 CREATE DATABASE [IF NOT EXISTS] <数据库名> [CHARACTER SET utf8] 2、删除 DROP DATABASE …
阅读更多...
MySQL —— 初始数据库

MySQL —— 初始数据库

数据库概念 在学习数据库之前&#xff0c;大家保存数据要么是在程序运行期间&#xff0c;例如&#xff1a;在学习编程语言的时候&#xff0c;大家写过的管理系统&#xff0c;运用一些简单的数据结构&#xff08;例如顺序表&#xff09;来组织数据&#xff0c;可是程序一旦结束…
阅读更多...
硬盘数据丢失不再怕，四大恢复工具帮你轻松逆转局面！

硬盘数据丢失不再怕，四大恢复工具帮你轻松逆转局面！

硬盘故障、误删文件、病毒攻击等原因导致数据丢失的情况时有发生。面对这种情况&#xff0c;如何高效、快速地进行硬盘数据恢复呢&#xff1f;接下来几款好用的数据恢复软件推荐给大家。 一、福昕数据恢复&#xff1a;全方位恢复&#xff0c;让数据无遗漏 链接&#xff1a;ww…
阅读更多...
Windows（Win10、Win11）本地部署开源大模型保姆级教程

Windows（Win10、Win11）本地部署开源大模型保姆级教程

目录 前言1.安装ollama2.安装大模型3.安装HyperV4.安装Docker5.安装聊天界面6.总结 点我去AIGIS公众号查看本文 本期教程用到的所有安装包已上传到百度网盘 链接&#xff1a;https://pan.baidu.com/s/1j281UcOF6gnOaumQP5XprA 提取码&#xff1a;wzw7 前言 最近开源大模型可谓闹…
阅读更多...
观测器控制仿真案例详解(s-function函数)

观测器控制仿真案例详解(s-function函数)

目录 一、弹簧-质量-阻尼系统1. 系统状态空间方程2. 观测器状态空间方程 二、仿真(Simulink s-function函数)1. 搭建Simulink仿真模型2. s-function函数代码3. 仿真效果 控制理论–观测器设计 一、弹簧-质量-阻尼系统 系统参数&#xff1a; m 1 , K 1 , B 0.5 m 1\,, K 1…
阅读更多...
【前端面试题】后端一次性返回10w条数据，该如何渲染？

【前端面试题】后端一次性返回10w条数据，该如何渲染？

后端一次返回 10w 条数据&#xff0c;本身这种技术方案设计就不合理。 问题分析&#xff1a; JS 支持处理10w 条数据&#xff0c;但 DOM 一次渲染 10w 条数据&#xff0c;可能会卡顿&#xff0c;所以需想办法减少 DOM 渲染 若非要实现&#xff0c;则可以考虑以下两种方案 自…
阅读更多...
【C语言】程序环境，预处理，编译，汇编，链接详细介绍，其中预处理阶段重点讲解

【C语言】程序环境，预处理，编译，汇编，链接详细介绍，其中预处理阶段重点讲解

目录 程序环境 翻译环境 1. 翻译环境的两个过程 2. 编译过程的三个阶段 执行环境 预处理(预编译) 1. 预定义符号 2. #define 2.1 用 #define 定义标识符(符号) 2.2 用 #define 定义宏 2.3 #define 的替换规则 2.4 # 和 ## 的用法 2.5 宏和函数 2.6 #undef …
阅读更多...
Java小白入门到实战应用教程-权限修饰符

Java小白入门到实战应用教程-权限修饰符

Java小白入门到实战应用教程-权限修饰符 前言 在前面的内容中我们其实已经接触到了权限修饰符&#xff1a;public 在java中权限修饰符除了public外&#xff0c;还有private、protected、默认权限。 权限修饰符可用来修饰类、成员变量、方法(函数)。 其中修饰类只能用publi…
阅读更多...
使用Response.Write实现在页面的生命周期中前后台的交互

使用Response.Write实现在页面的生命周期中前后台的交互

最近在做一个很大的查询&#xff0c;花时间很多&#xff0c; 用户会以为死掉了&#xff0c;就做了一个前后交互的&#xff0c;用于显示执行进度&#xff0c;在网上找了一下&#xff0c;这个比较合适。 主要是简单&#xff0c;大道至简 改进了一下&#xff1a;效果如下图 代码…
阅读更多...
【数学建模】评价类模型：优劣解距离法

【数学建模】评价类模型：优劣解距离法

【数学建模】评价类模型&#xff1a;优劣解距离法 目录 【数学建模】评价类模型&#xff1a;优劣解距离法 1&#xff1a;前言 2&#xff1a;算法 1. 将原始矩阵正向化(统一为极大型) 2. 正向矩阵标准化(消除量纲) 3. 计算得分并归一化 3&#xff1a;例题 4&#xff1a…
阅读更多...
shell脚本自动化部署

shell脚本自动化部署

1、自动化部署DNS [rootweb ~]# vim dns.sh [roottomcat ~]# yum -y install bind-utils [roottomcat ~]# echo "nameserver 192.168.8.132" > /etc/resolv.conf [roottomcat ~]# nslookup www.a.com 2、自动化部署rsync [rootweb ~]# vim rsync.sh [rootweb ~]# …
阅读更多...
jenkins集成jmeter

jenkins集成jmeter

jenkins 安装插件HTML Publisher startup trigger Groovy 脚本介绍 cd /app/jmeter rm -rf result.jtl jmeter.log report mkdir -p report sh /app/jmeter/apache-jmeter-5.6.3/bin/jmeter.sh -n -t test.jmx -l result.jtl -e -o ./report-n: 表示以非 GUI 模式运行 JMete…
阅读更多...
Java每日一练_模拟面试题1（死锁）

Java每日一练_模拟面试题1（死锁）

一、死锁的条件 死锁通常发生在两个或者更多的线程相互等待对方释放资源&#xff0c;从而导致它们都无法继续执行。死锁的条件通常被描述为四个必要条件&#xff0c;也就是互斥条件、不可剥夺条件、占有并等待条件和循环等待条件。 互斥条件&#xff1a;资源不能被共享&#x…
阅读更多...
unity中实现流光效果——世界空间下

unity中实现流光效果——世界空间下

Properties{_MainTex ("Texture", 2D) "white" {}_FlowColor ("Flow Color", Color) (1, 1, 1, 1) // 流光颜色_FlowFrequency ("Flow Frequency", Float) 1.0 // 流光频率_FlowSpeed ("Flow Speed", Float) 1.0 // 流光…
阅读更多...
QListView实现自定义的控件展示（可以根据选中与否置顶展示）

QListView实现自定义的控件展示（可以根据选中与否置顶展示）

文章目录 0 问题引入1、方案1&#xff1a;使用QListwidget自定义的widget1.1 效果1.1 思路 2、方案2&#xff1a;使用QListView自定义model自定义delegate2.1.浅谈2.2.实现 3、总结4、引用 0 问题引入 问题&#xff1a;有人问我如何实现上图的功能&#xff0c;当时我脑海里有了…
阅读更多...
手把手使用 SVG + CSS 实现渐变进度环效果

手把手使用 SVG + CSS 实现渐变进度环效果

效果 轨道 使用 svg 画个轨道 <svg viewBox"0 0 100 100"><circle cx"50" cy"50" r"40" fill"none" stroke-width"10" stroke"#333"></circle></svg>简单的说&#xff0c;就是…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023