二叉树的存储结构(链式存储)—— 数据结构与算法

在这里插入图片描述
请添加图片描述

😶‍🌫️Take your time ! 😶‍🌫️
💥个人主页:🔥🔥🔥大魔王🔥🔥🔥
💥代码仓库:🔥🔥魔王修炼之路🔥🔥
💥所属专栏:🔥魔王的修炼之路–数据结构🔥
如果你觉得这篇文章对你有帮助,请在文章结尾处留下你的点赞👍和关注💖,支持一下博主。同时记得收藏✨这篇文章,方便以后重新阅读。


文章目录

  • 一、前言
  • 二、二叉树的遍历
    • 前中后序
  • 三、求二叉树结点个数
  • 四、求二叉树深度
  • 五、第k层节点个数
  • 六、返回某个节点的地址
  • 七、总结

一、前言

学习完二叉树的顺序存储(堆),那么本篇博客将讲述二叉树的链式存储(左孩子右兄弟)。

  • 因为普通的二叉树增删查改没有任何意义,总不能只是因为结构复杂就用这个没有任何意义的普通二叉树来存储数据,所以我们不进行它的增删查改学习,而是先了解了解普通二叉树的一些操作:求二叉树节点个数、深度等等。

下面的所有内容都是以下图二叉树举例

在这里插入图片描述

二、二叉树的遍历

前中后序

前序:根左右
中序:左根右
后序:左右根

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef struct BTNode
{struct BTNode* left;struct BTNode* right;int data;
}BTNode;BTNode* BuyNewnode(int x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc error");assert(newnode);}newnode->data = x;newnode->left = NULL;newnode->right = NULL;return newnode;
}BTNode* BTCreat()
{BTNode* node1 = BuyNewnode(1);BTNode* node2 = BuyNewnode(2);BTNode* node3 = BuyNewnode(4);BTNode* node4 = BuyNewnode(3);BTNode* node5 = BuyNewnode(5);BTNode* node6 = BuyNewnode(6);node1->left = node2;node1->right = node3;node2->left = node4;node3->left = node5;node4->right = node6;return node1;
}//前序
void PreOrder(BTNode* n1)
{if (n1 == NULL){printf("NULL ");return;}printf("%d ", n1->data);PreOrder(n1->left);PreOrder(n1->right);
}//中序
void InOrder(BTNode* n1)
{if (n1 == NULL){printf("NULL ");return;}InOrder(n1->left);printf("%d ", n1->data);InOrder(n1->right);
}//后序
void PostOrder(BTNode* n1)
{if (n1 == NULL){printf("NULL ");return;}PostOrder(n1->left);PostOrder(n1->right);printf("%d ", n1->data);
}int main()
{BTNode* n1 = BTCreat();//前序PreOrder(n1);printf("\n");//中序InOrder(n1);printf("\n");//后序PostOrder(n1);printf("\n");return 0;
}

三、求二叉树结点个数

递归、分治,每层只需要知道自己下一层节点的总个数即可,然后传给上一层。记得每层向上回归的时候要加上自己的那一个。

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef struct BTNode
{struct BTNode* left;struct BTNode* right;int data;
}BTNode;BTNode* BuyNewnode(int x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc error");assert(newnode);}newnode->data = x;newnode->left = NULL;newnode->right = NULL;return newnode;
}BTNode* BTCreat()
{BTNode* node1 = BuyNewnode(1);BTNode* node2 = BuyNewnode(2);BTNode* node3 = BuyNewnode(4);BTNode* node4 = BuyNewnode(3);BTNode* node5 = BuyNewnode(5);BTNode* node6 = BuyNewnode(6);node1->left = node2;node1->right = node3;node2->left = node4;node3->left = node5;node4->right = node6;return node1;
}int BTSize(BTNode* n1)
{if (n1 == NULL)return 0;return BTSize(n1->left) + BTSize(n1->right) + 1;
}int main()
{BTNode* n1 = BTCreat();//二叉树节点个数int size = BTSize(n1);printf("%d\n", size);return 0;
}

在这里插入图片描述

四、求二叉树深度

还是递归和分治,每层只需要直到自己左子树和右子树中最高的那个即可。

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef struct BTNode
{struct BTNode* left;struct BTNode* right;int data;
}BTNode;BTNode* BuyNewnode(int x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc error");assert(newnode);}newnode->data = x;newnode->left = NULL;newnode->right = NULL;return newnode;
}BTNode* BTCreat()
{BTNode* node1 = BuyNewnode(1);BTNode* node2 = BuyNewnode(2);BTNode* node3 = BuyNewnode(4);BTNode* node4 = BuyNewnode(3);BTNode* node5 = BuyNewnode(5);BTNode* node6 = BuyNewnode(6);node1->left = node2;node1->right = node3;node2->left = node4;node3->left = node5;node4->right = node6;return node1;
}
int BinaryTreeHeight(BTNode* n1)
{if (n1 == NULL)return 0;int BTLeft = BinaryTreeHeight(n1->left);int BTRight = BinaryTreeHeight(n1->right);return BTLeft > BTRight ? BTLeft + 1: BTRight + 1;
}
int main()
{BTNode* n1 = BTCreat();//二叉树深度int BTHeight = BinaryTreeHeight(n1);printf("%d\n", BTHeight);return 0;
}

五、第k层节点个数

举例来说:第三层是相对于第一层来说的,相对于第二层就是第二层,相对于第三层就是第一层,也就是本层。

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef struct BTNode
{struct BTNode* left;struct BTNode* right;int data;
}BTNode;BTNode* BuyNewnode(int x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc error");assert(newnode);}newnode->data = x;newnode->left = NULL;newnode->right = NULL;return newnode;
}BTNode* BTCreat()
{BTNode* node1 = BuyNewnode(1);BTNode* node2 = BuyNewnode(2);BTNode* node3 = BuyNewnode(4);BTNode* node4 = BuyNewnode(3);BTNode* node5 = BuyNewnode(5);BTNode* node6 = BuyNewnode(6);node1->left = node2;node1->right = node3;node2->left = node4;node3->left = node5;node4->right = node6;return node1;
}
int BTKLevel(BTNode* n1,int k)
{if (n1 == NULL)return 0;if (k == 1)return 1;return BTKLevel(n1->left,k-1) + BTKLevel(n1->right,k-1);
}
int main()
{BTNode* n1 = BTCreat();//第K层有几个节点int k = BTKLevel(n1,4);printf("%d\n", k);return 0;
}

六、返回某个节点的地址

首先看能否找到该节点,找到的话返回该节点的地址,找不到的话返回NULL。

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef struct BTNode
{struct BTNode* left;struct BTNode* right;int data;
}BTNode;BTNode* BuyNewnode(int x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc error");assert(newnode);}newnode->data = x;newnode->left = NULL;newnode->right = NULL;return newnode;
}BTNode* BTCreat()
{BTNode* node1 = BuyNewnode(1);BTNode* node2 = BuyNewnode(2);BTNode* node3 = BuyNewnode(4);BTNode* node4 = BuyNewnode(3);BTNode* node5 = BuyNewnode(5);BTNode* node6 = BuyNewnode(6);node1->left = node2;node1->right = node3;node2->left = node4;node3->left = node5;node4->right = node6;return node1;
}
BTNode* BTFind(BTNode* n1,int x)
{if (n1 == NULL)return NULL;if (n1->data == x)return n1;BTNode* left = BTFind(n1->left,x);if (left)return left;BTNode* right = BTFind(n1->right,x);if (right)return right;return NULL;}
int main()
{BTNode* n1 = BTCreat();//返回某个值的位置BTNode* p = BTFind(n1,9);if(p!=NULL)printf("%p\n", p);return 0;
}

七、总结

  • 博主长期更新,博主的目标是不断提升阅读体验和内容质量,如果你喜欢博主的文章,请点个赞或者关注博主支持一波,我会更加努力的为你呈现精彩的内容。

🌈专栏推荐
😈魔王的修炼之路–C语言
😈魔王的修炼之路–数据结构初阶
😈魔王的修炼之路–C++
😈魔王的修炼之路–Linux
更新不易,希望得到友友的三连支持一波。收藏这篇文章,意味着你将永久拥有它,无论何时何地,都可以立即找到重新阅读;关注博主,意味着无论何时何地,博主将永久和你一起学习进步,为你带来有价值的内容。

请添加图片描述

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

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

相关文章

Linux 操作文件的系统调用

一、系统调用 系统调用表现出来的形式和库函数看着是一样的&#xff0c;但是系统调用的实现是在内核中&#xff0c;一旦执行系统调用以后&#xff0c;会产生中断&#xff0c;陷入内核&#xff0c;内核去执行相应的代码。我们无法直接去执行内核的代码&#xff0c;系统调用执行…

零基础看懂免费开源的Stable Diffusion

文章目录 前言Diffusion模型推理过程训练过程 Stable Diffusion模型参考 前言 前面一篇文章主要讲了扩散模型的理论基础&#xff0c;还没看过上篇的小伙伴可以点击查看&#xff1a;DDPM理论基础。这篇我们主要讲一下一经推出&#xff0c;就火爆全网的Stable Diffusion模型。St…

SQL-每日一题【1341. 电影评分】

题目 表&#xff1a;Movies 表&#xff1a;Users 请你编写一个解决方案&#xff1a; 查找评论电影数量最多的用户名。如果出现平局&#xff0c;返回字典序较小的用户名。查找在 February 2020 平均评分最高 的电影名称。如果出现平局&#xff0c;返回字典序较小的电影名称。 …

「鲸脸识别」已上线,夏威夷大学用 5 万张图像训练识别模型,平均精度 0.869

内容一览&#xff1a;人脸识别可以锁定人类身份&#xff0c;这一技术延申到鲸类&#xff0c;便有了「背鳍识别」。「背鳍识别」是利用图像识别技术&#xff0c;通过背鳍识别鲸类物种。传统的图像识别依赖于卷积神经网络 (CNN) 模型&#xff0c;需要大量训练图像&#xff0c;并且…

《3D 数学基础》12 几何图元

目录 1 表达图元的方法 1.1 隐式表示法 1.2 参数表示 1.3 直接表示 2. 直线和射线 2.1 射线的不同表示法 2.1.1 两点表示 2.1.2 参数表示 2.1.3 相互转换 2.2 直线的不同表示法 2.2.1 隐式表示法 2.2.2 斜截式 2.2.3 相互转换 3. 球 3.1 隐式表示 1 表达图元的方…

【C语言】每日一题(多数元素)

多数元素&#xff0c;链接奉上 方法 1.摩尔投票2.合理但错误的方法2.1暴力循环2.2排序求出中间元素中间元素 1.摩尔投票 先来简单的介绍摩尔投票&#xff1a; 摩尔投票是一种用来解决绝对众数问题的算法。 什么是绝对众数呢&#xff1f; 在一个集合中&#xff0c;如果一个元素…

PHP最简单自定义自己的框架model使用(七)

1、实现model使用效果 2、自动加载model,KJ.php //自动加载文件public static function _autoload($className){switch ($className){//自动model类case substr($className,-5)Model:$path MODEL./.$className..php;if(is_file($path)) include $path;break;//自动加载控制器…

机器学习理论笔记(一):初识机器学习

文章目录 1 前言&#xff1a;蓝色是天的机器学习笔记专栏1.1 专栏初衷与定位1.2 本文主要内容 2 机器学习的定义2.1 机器学习的本质2.2 机器学习的分类 3 机器学习的基本术语4 探索"没有免费的午餐"定理&#xff08;NFL&#xff09;5 结语 1 前言&#xff1a;蓝色是天…

隧道人员定位方案

针对隧道环境的人员定位方案&#xff0c;UWB定位技术同样可以提供高精度和可靠的定位服务。以下是一个可行的方案&#xff1a; 部署基站网络&#xff1a;在隧道内建立一个基站网络&#xff0c;基站需要均匀分布在各个关键位置&#xff0c;以确保全方位的覆盖。由于隧道的特殊环…

一、Dubbo 简介与架构

一、Dubbo 简介与架构 1.1 应用架构演进过程 单体应用&#xff1a;JEE、MVC分布式应用&#xff1a;SOA、微服务化 1.2 Dubbo 简介一种分布式 RPC 框架&#xff0c;对专业知识&#xff08;序列化/反序列化、网络、多线程、设计模式、性能优化等&#xff09;进行了更高层的抽象和…

SpringBoot集成Redis及Redis使用方法

目录 应用背景 Redis简介 更新问题 一&#xff1a;环境配置 1.1: 在pom.xml文件中添加依赖 1.2&#xff1a;配置SpringBoot核心配置文件application.properties 二&#xff1a;在Config文件夹中创建RedisConfig配置文件类 2.1&#xff1a;RedisTemplate中的几个角色&am…

基于安防监控EasyCVR视频汇聚融合技术的运输管理系统的分析

一、项目背景 近年来&#xff0c;随着物流行业迅速发展&#xff0c;物流运输费用高、运输过程不透明、货损货差率高、供应链协同能力差等问题不断涌现&#xff0c;严重影响了物流作业效率&#xff0c;市场对于运输管理数字化需求愈发迫切。当前运输行业存在的难题如下&#xf…

mysql-事务特性以及隔离机制

一.ACID 事务&#xff08;Transaction&#xff09;是访问和更新数据库的程序执行单元&#xff1b;事务中可能包含一个或多个sql语句&#xff0c;这些语句要么都执行&#xff0c;要么都不执行。 1.逻辑架构和存储引擎 如上图所示&#xff0c;MySQL服务器逻辑架构从上往下可以分…

【密码学】维京密码

维京密码 瑞典罗特布鲁纳巨石上的图案看起来毫无意义&#xff0c;但是它确实是一种维京密码。如果我们注意到每组图案中长笔画和短笔画的数量&#xff0c;将得到一组数字2、4、2、3、3、5、2、3、3、6、3、5。组合配对得到24、23、35、23、36、35。现在考虑如图1.4所示的内容&a…

六、Linux系统下,文件操作命令都有哪些?

总括&#xff1a; 创建文件/文件夹&#xff1a;touch&#xff1b; 查看&#xff1a;cat/more&#xff1b; 复制&#xff1a;copy&#xff1b; 移动文件/文件夹&#xff1a;mv&#xff1b; 删除&#xff1a;rm&#xff1b; 1、创建文件 &#xff08;1&#xff09;语法&#x…

java实现docx,pdf文件动态填充数据

一&#xff0c;引入pom 根据需求引入自己所需pom org.apache.poi poi 4.1.1 org.apache.poi poi-ooxml 4.1.1 org.jxls jxls 2.6.0 ch.qos.logback logback-core org.jxls jxls-poi 1.2.0 fr.opensagres.xdocreport fr.opensagres.xdocreport.core 2.0.2 fr.opensagres.xdocrep…

最小生成树 — Prim算法

同Kruskal算法一样&#xff0c;Prim算法也是最小生成树的算法&#xff0c;但与Kruskal算法有较大的差别。 Prim算法整体是通过“解锁” “选中”的方式&#xff0c;点 -> 边 -> 点 -> 边。 因为是最小生成树&#xff0c;所以针对的也是无向图&#xff0c;所以可以随意…

MySql011——检索数据:过滤数据(使用正则表达式)

前提&#xff1a;使用《MySql006——检索数据&#xff1a;基础select语句》中创建的products表 一、正则表达式介绍 关于正则表达式的介绍大家可以看我的这一篇博客《Java038——正则表达式》&#xff0c;这里就不再累赘。 二、使用MySQL正则表达式 2.1、基本字符匹配 检索…

Java版企业电子招投标采购系统源码之首页设计 tbms

​ 功能描述 1、门户管理&#xff1a;所有用户可在门户页面查看所有的公告信息及相关的通知信息。主要板块包含&#xff1a;招标公告、非招标公告、系统通知、政策法规。 2、立项管理&#xff1a;企业用户可对需要采购的项目进行立项申请&#xff0c;并提交审批&#xff0c;查…

照耀国产的星火,再度上新!

国产之光&#xff0c;星火闪耀 ⭐ 新时代的星火⭐ 多模态能力⭐ 图像生成与虚拟人视频生成⭐ 音频生成与OCR笔记收藏⭐ 助手模式更新⭐ 插件能力⭐ 代码能力⭐ 写在最后 ⭐ 新时代的星火 在这个快速变革的时代&#xff0c;人工智能正迅猛地催生着前所未有的革命。从医疗到金融…