数据结构第六课 -----链式二叉树的实现

作者前言

🎂 ✨✨✨✨✨✨🍧🍧🍧🍧🍧🍧🍧🎂
​🎂 作者介绍： 🎂🎂
🎂 🎉🎉🎉🎉🎉🎉🎉 🎂
🎂作者id：老秦包你会， 🎂
简单介绍：🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂🎂
喜欢学习C语言和python等编程语言，是一位爱分享的博主，有兴趣的小可爱可以来互讨 🎂🎂🎂🎂🎂🎂🎂🎂
🎂个人主页::小小页面🎂
🎂gitee页面:秦大大🎂
🎂🎂🎂🎂🎂🎂🎂🎂
🎂 一个爱分享的小博主 欢迎小可爱们前来借鉴🎂

链式二叉树

  • **作者前言**
  • 二叉树
  • 二叉树的遍历
    • 前序遍历
    • 中序遍历
    • 后序遍历
  • 小例子
  • 知识点

二叉树

前面粗略的介绍了二叉树
二叉树主要有两种 空树和非空树
而非空树拆分为 : 根节点 和左子树和右子树
在这里插入图片描述
二叉树的性质

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

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

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

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

  5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：

    1. 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
    2. 若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子
    3. 若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子

二叉树的遍历

学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

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

  1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。(根 ->左 ->右)

  2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。(左->根->右)

  3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。(左->右->根)

为此特意构建一个二叉树

#include<stdio.h>
#include<stdlib.h>
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType* val;struct BinaryTreeNode* left;struct BinaryTreeNode* rigth;}BinaryTreeNode;
BinaryTreeNode* CreateNode(BTDataType elemest)
{BinaryTreeNode* p = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));if (p == NULL){perror("malloc");return -1;}p->val = elemest;return p;
}
int main()
{BinaryTreeNode* n1 = CreateNode(1);BinaryTreeNode* n2 = CreateNode(2);BinaryTreeNode* n3 = CreateNode(3);BinaryTreeNode* n4 = CreateNode(4);BinaryTreeNode* n5 = CreateNode(5);BinaryTreeNode* n6 = CreateNode(6);n1->left = n2;n1->rigth = n4;n2->left = n3;n2->rigth = NULL;n3->left = NULL;n3->rigth = NULL;n4->left = n5;n4->rigth = n6;n5->left = NULL;n5->rigth = NULL;n6->left = NULL;n6->rigth = NULL;return 0;
}

前序遍历

我们以上面图片为例
我们可以写成：
1 2 3 N N N 4 5 N N 6 N N
代码：

void PreOrder(BinaryTreeNode* n1)
{if (n1 == NULL){printf("NULL ");return;}printf("%d ", n1->val);PreOrder(n1->left);PreOrder(n1->rigth);
}

在这里插入图片描述

中序遍历

我们可以写成：N 3 N 2 N 1 N 5 N 4 N 6 N
代码：

void InOrdef(BinaryTreeNode* n1)
{if (n1 == NULL){printf("NULL ");return;}PreOrder(n1->left);printf("%d ", n1->val);PreOrder(n1->rigth);
}

后序遍历

我们可以写成： N N 3 N 2 N N 5 N N 6 4 1
代码：

void PostOrder(BinaryTreeNode* n1)
{if (n1 == NULL){printf("NULL ");return;}PreOrder(n1->left);PreOrder(n1->rigth);printf("%d ", n1->val);
}

小例子

叶子节点个数
思路:左子树的节点个数加上右子树的节点个数加上根节点

//节点个数
int TreeSize(BinaryTreeNode* n1)
{if (n1 == NULL)return 0;return 1 + TreeSize(n1->left) + TreeSize(n1->rigth);
}

叶节点个数
思路:左子树的叶节点个数加上右子树的叶节点个数加上根节点 需要注意的是为空树.和只有根节点的情况

//叶节点的个数
int TreeLeafSize(BinaryTreeNode* n1)
{//为空树if (n1 == NULL)return 0;//只有一个节点if (n1->left == NULL && n1->rigth == NULL)return 1;return TreeLeafSize(n1->left) + TreeLeafSize(n1->rigth);
}

树的高度
思路:左子树的高度和右子树高度比较,大的高度加上1就是整个二叉树的高度,需要注意的是空树情况下

int TreeHeigth(BinaryTreeNode* n1)
{if (n1 == NULL)return 0;if (n1->left == NULL && n1->rigth == NULL)return 1;int a = TreeHeigth(n1->left);int b = TreeHeigth(n1->rigth);return (a > b ? a : b) + 1;
}

#第k层的节点
思路: 左子树的第k-1层的节点个数 加上右子树的第k-1层的节点个数,如果k为0就是空,k=1,就是1
​

int NodeNum(BinaryTreeNode* n1, int k)
{if (n1 == NULL)return 0;if (k == 0)return 0;if (k == 1)return 1;return NodeNum(n1->left, k - 1) + NodeNum(n1->rigth, k - 1);
}

层次遍历
思路:层次遍历就是从第一层开始横向遍历
我们可以借助队列的性质,先进先出,我们先开始插入根节点,然后开始进行循环判断,只要出去的节点的左右孩子不为NULL就插入到队列,直到队列为空
在这里插入图片描述

// 层序遍历
void BinaryTreeLevelOrder(BinaryTreeNode* root)
{//创建一个队列Queue Qu;//初始化QueueInit(&Qu);//插入的是节点,if (root != NULL)QueuePush(&Qu, root);while (QueueSize(&Qu)){BinaryTreeNode* from = QueueFront(&Qu);printf("%d ", from->val);//删除QueuePop(&Qu);//需要注意的是删除只是释放掉存储了二叉树节点的地址的空间,并没有释放二叉树节点if (from->left != NULL){QueuePush(&Qu, from->left);}if (from->rigth != NULL){QueuePush(&Qu, from->rigth);}}printf("\n");QueueDestroy(&Qu);}

这个是打印全部的
如果要一层层的打印
思路: 我们可以定义一个变量,用来统计当前队列的个数,也就是当层的节点个数,然后每出列一个就把对应的左右孩子插入进去,然后该变量减1,直到为0,也就是该层的节点全部出列了,然后再计算出队列的长度,也就是下一层的节点个数,然后继续，直到队列的长度为0

在这里插入图片描述

// 层序遍历
void BinaryTreeLevelOrder(BinaryTreeNode* root)
{//创建一个队列Queue Qu;//初始化QueueInit(&Qu);//插入的是节点,if (root != NULL)QueuePush(&Qu, root);int size = QueueSize(&Qu);while (QueueSize(&Qu)){while (size--){BinaryTreeNode* from = QueueFront(&Qu);printf("%d ", from->val);//删除QueuePop(&Qu);//需要注意的是删除只是释放掉存储了二叉树节点的地址的空间,并没有释放二叉树节点if (from->left != NULL){QueuePush(&Qu, from->left);}if (from->rigth != NULL){QueuePush(&Qu, from->rigth);}}printf("\n");size = QueueSize(&Qu);}printf("\n");QueueDestroy(&Qu);}

判断是否是完全二叉树
思路：我们和上面的层次遍历一样，先找一个队列进行一层层的入队和出队，如果遇见节点为NULL的就判断后面是否还有节点存在

// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BinaryTreeNode* root)
{//创建一个队列Queue Qu;//初始化QueueInit(&Qu);//插入的是节点,if (root != NULL)QueuePush(&Qu, root);while (QueueSize(&Qu)){BinaryTreeNode* from = QueueFront(&Qu);if (from == NULL)break;//删除QueuePop(&Qu);//需要注意的是删除只是释放掉存储了二叉树节点的地址的空间,并没有释放二叉树节点QueuePush(&Qu, from->left);QueuePush(&Qu, from->rigth);}//判断后面是否还有非空while (!QueueEmtry(&Qu)){BinaryTreeNode* from = QueueFront(&Qu);if (from != NULL)return 0;//删除QueuePop(&Qu);}QueueDestroy(&Qu);return 1;}

知识点

前序：深度优先遍历
层序： 广度优先遍历

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

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

相关文章

Java SpringBoot Controller常见写法

Java SpringBoot Controller常见写法

文章目录 环境Controller调用脚本运行结果总结 环境 系统: windows 11 工具: java, idea, git bash Controller 接口常见有以下几种方式 其中&#xff1a; Tobj 调用脚本 我的是windows 系统&#xff0c;使用 git bash 窗口运行, 用 cmd 或者 power shell 会有问题 curl …
阅读更多...
C盘分析文件大小的软件

C盘分析文件大小的软件

https://sourceforge.net/projects/windirstat/ 上面是windirstat的下载链接 界面是这样的&#xff1a; 选择C盘或者D盘&#xff0c;点击OK&#xff0c;就可以分析了 然后就可以看到哪些占比最高&#xff0c;可以针对性的清理
阅读更多...
C#网络编程UDP程序设计（UdpClient类）

C#网络编程UDP程序设计（UdpClient类）

目录 一、UdpClient类 二、示例 1.源码 &#xff08;1&#xff09;Client &#xff08;2&#xff09;Server 2.生成 &#xff08;1&#xff09;先启动服务器&#xff0c;发送广播信息 &#xff08;2&#xff09;再开启客户端接听 UDP是user datagram protocol的简称&a…
阅读更多...
整数的立方和

整数的立方和

系列文章目录 进阶的卡莎C++_睡觉觉觉得的博客-CSDN博客数1的个数_睡觉觉觉得的博客-CSDN博客双精度浮点数的输入输出_睡觉觉觉得的博客-CSDN博客足球联赛积分_睡觉觉觉得的博客-CSDN博客大减价(一级)_睡觉觉觉得的博客-CSDN博客小写字母的判断_睡觉觉觉得的博客-CSDN博客纸币(…
阅读更多...
bad_python

bad_python

攻防世界 (xctf.org.cn) 前戏 下载文件&#xff0c;解压完成后是这个 一个pyc文件 这里要用到python的反编译 要用到的工具有两个 1.python自带的uncompyle6 2.pycdc文件——比uncompyle6强大一点 我们一个一个来尝试一下 uncompyle6&#xff1a; 我是直接在pycharm里面…
阅读更多...
uniapp在H5端实现PDF和视频的上传、预览、下载

uniapp在H5端实现PDF和视频的上传、预览、下载

上传 上传页面 <u-form-item :label"(form.ququ3 1 ? 参培 : form.ququ3 2 ? 授课 : ) 证明材料" prop"ququ6" required><u-button click"upload" slot"right" type"primary" icon"arrow-upward" t…
阅读更多...
设计模式-结构型模式之代理设计模式

设计模式-结构型模式之代理设计模式

文章目录 八、代理设计模式 八、代理设计模式 代理设计模式通过代理控制对象的访问&#xff0c;可以详细访问某个对象的方法&#xff0c;在这个方法调用处理&#xff0c;或调用后处理。既(AOP微实现) 。 代理有分静态代理和动态代理&#xff1a; 静态代理&#xff1a;在程序…
阅读更多...
集成开发环境PyCharm的使用【侯小啾python基础领航计划 系列（三）】

集成开发环境PyCharm的使用【侯小啾python基础领航计划 系列（三）】

集成开发环境 PyCharm 的使用【侯小啾python基础领航计划 系列（三）】 大家好，我是博主侯小啾， 🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹…
阅读更多...
QT 中 QProgressDialog 进度条窗口 备查

QT 中 QProgressDialog 进度条窗口 备查

基础API //两个构造函数 QProgressDialog::QProgressDialog(QWidget *parent nullptr, Qt::WindowFlags f Qt::WindowFlags());QProgressDialog::QProgressDialog(const QString &labelText, const QString &cancelButtonText, int minimum, int maximum, QWidget *…
阅读更多...
BFS求树的宽度——结合数组建树思想算距离

BFS求树的宽度——结合数组建树思想算距离

二叉树最大宽度 https://leetcode.cn/problems/maximum-width-of-binary-tree/description/ 1、考虑树的宽度一定是在一层上的所以进行BFS&#xff0c;树的BFS不建议直接使用队列&#xff0c;每次add/offer然后poll/remove&#xff0c;这样子层级关系不好显示。我们可以定义…
阅读更多...
java连接池 理解及解释（DBCP、druid、c3p0、HikariCP）

java连接池 理解及解释（DBCP、druid、c3p0、HikariCP）

一、在Java开发中&#xff0c;有许多常见的数据库连接池可供选择。以下是一些常见的Java数据库连接池&#xff1a;不使用数据库连接池的特性&#xff1a; 优点&#xff1a;实现简单 缺点&#xff1a;网络 IO 较多数据库的负载较高响应时间较长及 QPS 较低应用频繁的创建连接和关…
阅读更多...
深入理解JVM虚拟机第二十七篇：详解JVM当中InvokeDynamic字节码指令，Java是动态类型语言么？

深入理解JVM虚拟机第二十七篇：详解JVM当中InvokeDynamic字节码指令，Java是动态类型语言么？

😉😉 学习交流群： ✅✅1：这是孙哥suns给大家的福利！ ✨✨2：我们免费分享Netty、Dubbo、k8s、Mybatis、Spring...应用和源码级别的视频资料 🥭🥭3：QQ群：583783824 📚📚 工作微信：BigTreeJava 拉你进微信群，免费领取！ 🍎🍎4：本文章内容出自上述：Sp…
阅读更多...
3D模型渲染导致电脑太卡怎么办？

3D模型渲染导致电脑太卡怎么办？

在线工具推荐&#xff1a; 三维数字孪生场景工具 - GLTF/GLB在线编辑器 - Three.js AI自动纹理化开发 - YOLO 虚幻合成数据生成器 - 3D模型在线转换 - 3D模型预览图生成服务 1、什么是3D渲染&#xff1f; 3D渲染是指通过计算机图形学技术将三维模型转化为二维图像的过程…
阅读更多...
Stable Diffusion AI绘画系列【12】:国风美女剑客系列

Stable Diffusion AI绘画系列【12】:国风美女剑客系列

《博主简介》 小伙伴们好&#xff0c;我是阿旭。专注于人工智能、AIGC、python、计算机视觉相关分享研究。 ✌更多学习资源&#xff0c;可关注公-仲-hao:【阿旭算法与机器学习】&#xff0c;共同学习交流~ &#x1f44d;感谢小伙伴们点赞、关注&#xff01; 《------往期经典推…
阅读更多...
FLASK博客系列6——数据库之谜

FLASK博客系列6——数据库之谜

我们上一篇已经实现了简易博客界面&#xff0c;你还记得我们的博客数据是自己手动写的吗&#xff1f;但实际应用中&#xff0c;我们是不可能这样做的。大部分程序都需要保存数据&#xff0c;所以不可避免要使用数据库。我们这里为了简单方便快捷&#xff0c;使用了超级经典的SQ…
阅读更多...
具有五层协议的网络体系结构

具有五层协议的网络体系结构

目录 一、计算机的网络体系结构 二、五层协议的体系结构 1、物理层 2、数据链路层 3、网络层 4、传输层 5、应用层 三、数据在各层之间传输的过程 一、计算机的网络体系结构 二、五层协议的体系结构 1、物理层 利用传输介质为通信的网络结点之间建立、管理和释放物理连…
阅读更多...
leetcode：对称二叉树

leetcode：对称二叉树

题目描述 题目链接&#xff1a;101. 对称二叉树 - 力扣&#xff08;LeetCode&#xff09; 题目分析 题目中说至少存在一个节点&#xff0c;所以我们只需要对比左右子树 写一个子函数对比左右子树&#xff1a;用递归的思路&#xff0c;左子树的左子树和右子树的右子树对比&…
阅读更多...
语音识别从入门到精通——1-基本原理解释

语音识别从入门到精通——1-基本原理解释

文章目录 语音识别算法1. 语音识别简介1.1 **语音识别**1.1.1 自动语音识别1.1.2 应用 1.2 语音识别流程1.2.1 预处理1.2.2 语音检测和断句1.2.3 音频场景分析1.2.4 识别引擎(**语音识别的模型**)1. 传统语音识别模型2. 端到端的语音识别模型基于Transformer的ASR模型基于CNN的…
阅读更多...
价差后的几种方向，澳福如何操作才能盈利

价差后的几种方向，澳福如何操作才能盈利

在价差出现时&#xff0c;澳福认为会出现以下几种方向。 昂贵资产的贬值和便宜资产的平行升值。昂贵的资产贬值&#xff0c;而便宜的资产保持不变。昂贵资产的贬值和便宜资产的平行贬值&#xff0c;但昂贵资产的贬值速度更快&#xff0c;超过便宜资产。更贵的一对的进一步升值和…
阅读更多...
鸿蒙4.0开发笔记之ArkTS装饰器语法基础之发布者订阅者模式@Provide和@Consume（十三）

鸿蒙4.0开发笔记之ArkTS装饰器语法基础之发布者订阅者模式@Provide和@Consume（十三）

1、定义 在鸿蒙系统的官方语言ArkTS中&#xff0c;有一套类似于发布者和订阅的模式&#xff0c;使用Provide、Consume两个装饰器来实现。 Provide、Consume&#xff1a;Provide/Consume装饰的变量用于跨组件层级&#xff08;多层组件&#xff09;同步状态变量&#xff0c;可以…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023