数据结构第九讲:二叉树

数据结构第九讲:二叉树

  • 1.实现链式结构二叉树
    • 1.1二叉树的节点结构
    • 1.2创建二叉树节点
    • 1.3前中后序遍历
      • 1.3.1前序遍历
      • 1.3.2中序遍历
      • 1.3.3后序遍历
      • 1.3.4总结
    • 1.4二叉树结点的个数
      • 1.4.1错误示范
      • 1.4.2实现方法
    • 1.5二叉树叶子结点的个数
    • 1.6二叉树第k层结点的个数
    • 1.7二叉树的深度/高度
    • 1.8二叉树查找值为x的结点
    • 1.9二叉树的销毁
  • 2.二叉树的层序遍历
    • 2.1什么是层序遍历
    • 2.2层序遍历的实现
      • 2.2.1实现思路
      • 2.2.2先创建一个队列
      • 2.2.3代码的实现
  • 3.判断是否为完全二叉树
    • 3.1解题思路
    • 3.2代码实现

这一讲我们要实现二叉树的链式结构,二叉树结构体中包含了数据、指向左孩子节点的指针和指向右孩子节点的指针,在这一讲中,我们将要体会的递归的暴力!!!

1.实现链式结构二叉树

1.1二叉树的节点结构

//二叉树的节点结构
typedef int BinaryTreeDataType;typedef struct BinaryTreeNode
{BinaryTreeDataType data;//保存数据struct BinaryTreeNode* left;//指向左孩子节点struct BinaryTreeNode* right;//指向右孩子节点
}BTNode;

1.2创建二叉树节点

也就是为二叉树创建节点,并将节点进行初始化

//创建二叉树节点
BTNode* BuyBTNode(int val)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc fail!");return NULL;}newnode->data = val;newnode->left = newnode->right = NULL;return newnode;
}

1.3前中后序遍历

接下来我们要实现的是二叉树的遍历:

二叉树的遍历操作分为三种:前序遍历、中序遍历、后序遍历:
在这里插入图片描述
可以看出:这里区分的前中后其实就是根节点遍历的顺序
我们先总体看三种遍历的不同:
在这里插入图片描述

接下来我们来实现三种遍历,注意:三种遍历方法的代码实现非常简单,主要是思路的体会,三种方法都是使用的递归的思想

1.3.1前序遍历

//前序遍历
//函数传入的是树的根节点
void PreOrder(BTNode* root)
{if (root == NULL){return;}//将节点的数据进行打印printf("%d ", root->data);PreOrder(root->left);PreOrder(root->right);
}

在这里插入图片描述

对于递归,return之后只是一个递归函数终止,然而形参的值不变,函数会继续向下执行,形成一个全新的递归函数:
在这里插入图片描述

1.3.2中序遍历

//中序遍历
void InOrder(BTNode* root)
{//也就是左根右进行遍历if (root == NULL){return;}//先对左边的数据进行读取,其实就是将左边的节点当成是根节点进行传入InOrder(root->left);//先打印根节点的值,然后再检查右节点是否为空printf("%d ", root->data);//当右节点不为空时,它会按照从上向下的顺序一直走到右节点的尽头//当然,当有右节点中存在左节点时,会先走左节点的循环,因为左节点的循环在上//而且会一下走到左节点的尽头,然后从下往上遍历左节点InOrder(root->right);
}

1.3.3后序遍历

//后序遍历
void PostOrder(BTNode* root)
{if (root == NULL){return;}//仍然是先走到最后一个左节点PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);
}

1.3.4总结

在这里插入图片描述

1.4二叉树结点的个数

1.4.1错误示范

根据我们之前所讲,那么我们应该会有一个初步的思路,我们先实现一下:

//二叉树结点个数
//先定义一个变量sz
int sz = 0;
int BTSize(BTNode* root)
{if (root == NULL){return 0;}//每循环一次,那么就将sz++一次++sz;BTSize(root->left);BTSize(root->right);return sz;
}

这时打印的结果也是非常beautiful啊,和预想的一样,但是,当我们这样时:

//二叉树结点个数
int size = BTSize(n1);
printf("%d ", size);//6
size = BTSize(n1);
printf("%d ", size);//12

我们就会惊奇地发现:结点的次数竟然会随着函数调用次数的增加而成倍地增长!原因就是使用了全局变量,全局变量在函数使用后不会销毁,那么我们就要进行更改了:

1.4.2实现方法

//二叉树结点个数
int BTSize(BTNode* root)
{if (root == NULL){return 0;}//返回左节点的个数和右节点的个数return 1 + BTSize(root->left) + BTSize(root->right);
}

1.5二叉树叶子结点的个数

//二叉树叶子结点个数
int BTLeafSize(BTNode* root)
{if (root == NULL){return 0;}if (root->left == NULL && root->right == NULL){return 1;}//这里的返回值也会参与加法运算,所以会呈现出累加的效果//也就是说,返回值会存储到BTLeafSize(root->left)或另一个函数中,然后再进入加法运算//返回左边的树的叶子节点个数 + 右边的树的叶子结点个数return BTLeafSize(root->left) + BTLeafSize(root->right);
}

对于递归,先搞清总体思路,如上边的:返回左边的树的叶子节点个数 + 右边的树的叶子结点个数,然后再想清楚结束条件,如:当左节点和右节点都为0时返回1,此时会发现递归已经写完了!!!

1.6二叉树第k层结点的个数

//二叉树第k层结点的个数
int BTLevelKSize(BTNode* root, int k)
{if (root == NULL){return 0;}//返回条件:当k = 1时if (k == 1){return 1;}//返回左边的二叉树第k层的节点个数和右边二叉树第k层的结点个数return BTLevelKSize(root->left, k - 1) + BTLevelKSize(root->right, k - 1);
}

1.7二叉树的深度/高度

要想在递归的过程中对数据逐渐进行增大,必须要让return返回的值被接收,而且参与递归运算,这里是创建变量进行存储,还可以使用递归函数进行存储,如:1+BTDeapth(root->right)(这里是瞎写,仅代表一个格式)

//二叉树的深度/高度
int BTDepth(BTNode* root)
{if (root == NULL){return 0;}int leftdepth = BTDepth(root->left);int rightdepth = BTDepth(root->right);//要想在递归的过程中对数据逐渐进行增大,必须要让return返回的值被接收,而且参与递归运算//这里是创建变量进行存储//还可以使用递归函数进行存储,如:1+BTDeapth(root->right)(这里是瞎写,仅代表一个格式)return leftdepth > rightdepth ? leftdepth + 1 : rightdepth + 1;
}

在这里插入图片描述

1.8二叉树查找值为x的结点

//二叉树查找值为x的结点
BTNode* BTFind(BTNode* root, BinaryTreeDataType x)
{if (root == NULL){return NULL;}//返回条件:当数据是我们想要的数据时,就进行返回if (root->data == x){return root;}BTNode* left = BTFind(root->left, x);if (left){//这里要十分注意的是://这里的return表示的是整个函数的返回,上面的return代表的是递归函数的返回//原因就在于使用了一个值来接受递归函数的返回值,使得递归函数结束递归了//如果这里不适用变量来接受的话,函数将会错误返回return left;}BTNode* right = BTFind(root->right, x);if (right){return right;}return NULL;
}

1.9二叉树的销毁

//二叉树的销毁
//因为销毁要改变指针的指针的指向,所以这里传的是二级指针
void BTDestory(BTNode** root)
{if (*root == NULL){return;}//这里的传参要注意:因为是二级指针接收,所以传入的应该是一级指针的地址//直接遍历所有结点,然后一一删除即可BTDestory(&(*root)->left);BTDestory(&(*root)->right);free(*root);*root = NULL;
}

2.二叉树的层序遍历

2.1什么是层序遍历

层序遍历就是按照层数,从左到右一次对数据进行遍历:
在这里插入图片描述

2.2层序遍历的实现

2.2.1实现思路

对于递归,它会一直执行下去,直到遇到结束条件,然而,这个算法中,并不支持递归的使用,因为我们想不出来什么结束条件能够成立,所以这时我们就想到了其它的方法:队列!!!

在这里插入图片描述
下面我们来看实现方法:

2.2.2先创建一个队列

恰巧我们刚刚学过了队列,所以我们完全可以将之前写的队列代码拿过来,但是要注意的是,之前我们所实现的队列中保存的值为int类型,但是现在因为插入的值为BTNode*类型,所以还要将类别进行更改:

//结点结构体
//尽管我们之前已经使用typedef将结构体的名字改变成了BTNode*
//这里仍然需要加上struct,否则编译器会识别不出来,万一是一个变量名呢对不对
typedef struct BTNode* QueueDataType;typedef struct QueueNode
{//和链表一样,也需要结点进行链接QueueDataType val;struct QueueNode* next;
}QueueNode;

2.2.3代码的实现

//二叉树层序遍历
void LevelOrder(BTNode* root)
{//先创建一个队列Queue q;//队列初始化Init(&q);//将二叉树链表入队列QueuePush(&q, root);//循环,当队列为空时结束循环,当队列不为空时进行循环while (!QueueEmpty(&q)){//将一个结点出队列BTNode* ret = QueueFront(&q);printf("%d ", ret->data);QueuePop(&q);//如果有左右结点的话,按顺序入队列if (ret->left){QueuePush(&q, ret->left);}if (ret->right){QueuePush(&q, ret->right);}}Destory(&q);
}

3.判断是否为完全二叉树

3.1解题思路

这一道题目仍然是应用队列的知识:
在这里插入图片描述

3.2代码实现

//判断是否为完全二叉树
bool BinaryTreeComplete(BTNode* n1)
{//先创建一个队列Queue q;Init(&q);//先将二叉树中的数据全部插入到队列中//先将对头元素插入到队列中QueuePush(&q, n1);while (!QueueEmpty(&q)){BTNode* top = QueueFront(&q);QueuePop(&q);if (top == NULL){break;}//如果top不为空,将top的左孩子结点和右孩子结点入队,这样就保障了NULL结点的入队QueuePush(&q, top->left);QueuePush(&q, top->right);}//入队完成之后,检查队列中的数据,不能够存在一个NULL数据while (!QueueEmpty(&q)){BTNode* top = QueueFront(&q);QueuePop(&q);//如果存在不为空的数据,返回falseif (top){Destory(&q);return false;}}Destory(&q);return true;
}

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

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

相关文章

计算机语言-CSP初赛知识点整理

历年真题 [2020-CSP-J-第2题] 编译器的主要功能( ) A. 将源程序翻译成机器指令代码 B. 将源程序重新组合 C. 将低级语言翻译成高级语言 D. 将一种高级语言翻译成另一种高级语言 [2021-CSP-J-第1题] 以下不属于面向对象程序设计语言的是()。 A. C B. Pyt…

CLOS架构

CLOS Networking CLOS Networking 是指使用 Clos 网络拓扑结构(Clos Network Topology)进行网络设计的一种方法。该方法是由贝尔实验室的工程师 Charles Clos 在1950年代提出的,以解决电路交换网络的可扩展性和性能问题。随着现代计算和网络…

P33-模拟实现字符串相关函数

模拟实现strcpy strcpy函数是C语言中的字符串拷贝函数,用于将一个字符串复制到另一个字符串中。 函数原型如下: char* strcpy(char* destination, const char* source);参数说明: destination:目标字符串的指针,用于存…

北大和鹏城实验室联合推出的图像视频统一多模态大模型Chat-UniVi(CVPR 2024)

Chat-UniVi: Unified Visual Representation Empowers Large Language Models with Image and Video Understanding 论文信息 paper:CVPR 2024 code:https://github.com/PKU-YuanGroup/Chat-UniVi 训练130亿大模型仅3天,北大提出Chat-UniVi…

Tomcat 漏洞

一.CVE-2017-12615 1.使用burp抓包 把get改成put jsp文件后加/ 添加完成后访问 木马 然后木马的网址 在哥斯拉测试并且添加 添加成功 然后我们就成功进去啦、 二.弱口令 点击后输入默认用户名、密码:tomcat/tomcat 登陆之后上传一个jsp文件 后缀改成war 然后访问我…

android compose设置圆角不起作用

进度条progress设置背景圆角不起作用: 源码: Composablefun CircularProgress(modifier: Modifier, vm: TabarCmpViewModel?) {if (vm?.showLoading?.value ! true) returnBox(modifier modifier.background(Color(0x99000000)).defaultMinSize(minW…

【深度学习】【语音TTS】OpenVoice v2,测评,中英文语料,Docker镜像,对比GPT-SoVITS、FishAudio、BertVITS2

https://github.com/myshell-ai/OpenVoice/blob/main/docs/USAGE.md 实际体验OpenVoice v2的TTS效果。 文章目录 环境启动 jupyter代码代码分析主要模块和功能测试一些别的中文和中英文混合总结优点缺点对比GPT-SoVITS、FishAudio、BertVITS2使用我的Docker镜像快速体验OpenVo…

4.7.深层循环神经网络

深层循环网络 ​ 就是更深了,因为之前的网络都只有一层隐藏层,弄多一点 ​ 我们将多层循环神经网络堆叠在一起,通过对几个简单层的组合,产生了一个灵活的机制。上图展示了一个具有 L L L个隐藏层的深度循环神经网络,每…

【C++】STL | vector 详解及重要函数的实现

目录 前言 总代码 vector类框架建立(模板与成员变量) 构造、析构、swap 与 赋值重载 构造 析构 swap 赋值重载 reserve 扩容(重要!!)、size、capacity operator[ ]重载 insert 插入 逻辑讲解 i…

Oracle认证1Z0-071线上考试注意事项

目录 一、前言二、回顾过往战绩第一次 裸考🐒第二次 背题库硬考!🐒第三次 软件卡住,寄!🙈第四次 汇总纠错,通过!🌚 三、考试流程四、考试注意事项1. 是否需要科学上网2. …

探索四川财谷通抖音小店:安全与信赖的购物新体验

在数字经济蓬勃发展的今天,抖音平台凭借其庞大的用户基础和强大的内容生态,逐渐成为了电商领域的一股不可忽视的力量。其中,四川财谷通抖音小店作为这一浪潮中的佼佼者,不仅以其丰富的商品种类和独特的品牌魅力吸引了众多消费者的…

Java多线程的单例设计模式 多种实现方法

目录 前言 饿汉式 懒汉式 Double_check volatile double_check Holder方式 枚举 前言 单例设计模式GOF23中设计模式中最常用的设计模式之一, 单例设计模式提供了多线程环境下的保证唯一实例性的解决方案, 虽然简单, 但是实现单例模式的方式多种多样, 因此需要从多个维度去…

[安洵杯 2019]easy_serialize_php

[安洵杯 2019]easy_serialize_php [安洵杯 2019]easy_serialize_php - DGhh - 博客园 (cnblogs.com) [安洵杯 2019]easy_serialize_php - 何止(h3zh1) - 博客园 (cnblogs.com) 涉及的考点是字符串逃逸 <?php //GET一个f $function $_GET[f];//定义过滤的字符串数组 fu…

c++初阶-------模板

作者前言 &#x1f382; ✨✨✨✨✨✨&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f382; ​&#x1f382; 作者介绍&#xff1a; &#x1f382;&#x1f382; &#x1f382; &#x1f389;&#x1f389;&#x1f389…

科普文:微服务之全文检索SpringBoot整合ElasticSearch说明

一、RestHighLevelClient介绍 JavaREST客户端有两种模式&#xff1a; Java Low Level REST Client&#xff1a;ES官方的低级客户端。低级别的客户端通过http与Elasticsearch集群通信。Java High Level REST Client&#xff1a;ES官方的高级客户端。基于上面的低级客户端&…

Io 35

FIleinputStream字节输入 package File.io;import java.io.*;public class io1 {public static void main(String[] args) throws IOException {// InputStream is new FileInputStream(new File("C:\\Users\\SUI\\Desktop\\Java1\\one\\src\\kaishi"));//简化Input…

C++ 几何算法 - 求两条直线交点

一&#xff1a;算法介绍 1. 首先定义两条直线方程&#xff1a; 2. 解方程&#xff0c;求出x, y坐标 3. 如果x分母的行列式等于0&#xff0c; 说明两条直线平行或方向相反 4. 如果x&#xff0c;y分母的行列式都等于0&#xff0c;说明两条线重叠 二&#xff1a;代码实现: #inclu…

求职Leetcode题目(5)

1.分割回文串 每一个结点表示剩余没有扫描到的字符串&#xff0c;产生分支是截取了剩余字符串的前缀&#xff1b;产生前缀字符串的时候&#xff0c;判断前缀字符串是否是回文。如果前缀字符串是回文&#xff0c;则可以产生分支和结点&#xff1b;如果前缀字符串不是回文&#…

Vue常见问题(一)组件的使用

Failed to resolve component. 报错原因&#xff1a; 组件注册错误&#xff1a;我们在组件中使用了未注册的组件。在Vue中&#xff0c;组件必须先注册才能使用。 解决方法&#xff1a; 引用组件 &#xff1a; import ItemPage from "/components/itemPage.vue";…

【踩坑】pytorch中的索引与copy_结合不会复制数据及其解决方案

转载请注明出处&#xff1a;小锋学长生活大爆炸[xfxuezhagn.cn] 如果本文帮助到了你&#xff0c;欢迎[点赞、收藏、关注]哦~ 目录 背景知识 实验验证 结论分析 错误案例 处理方法 注意事项 附加说明 基本索引返回视图 高级索引返回副本 赋值操作都是原地操作 以下内容…