数据结构第九讲:二叉树

server/2024/9/23 7:31:17/

数据结构第九讲:二叉树

  • 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.ppmy.cn/server/96282.html

相关文章

网络安全 - 应急响应检查表

前言 本项目旨在为应急响应提供全方位辅助,以便快速解决问题。结合自身经验和网络资料,形成检查清单,期待大家提供更多技巧,共同完善本项目。愿大家在应急之路一帆风顺。 图片皆来源于网络,如有侵权请联系删除。 一…

前端面试题- 如何让vue页面重新渲染

哈喽小伙伴们,大家好!我是爱学英语的程序员,上周五结束了我的第一段实习,接下来将会为大家继续更新面试题系列,不断积累,不断进步! 在Vue中,可以使用以下几种方式让页面重新渲染: 改变数据状态: Vue中的响应式系统会自动监听数据的变化&am…

【多线程-从零开始-肆】线程安全、加锁和死锁

进程状态 进程状态: 就绪:正在 CPU 上执行,或者随时可以去 CPU 上执行阻塞:暂时不能参与 CPU 的执行 Java 的线程,对应状态做了更详细的区分,不仅仅是就绪和阻塞了 六种状态: NEW 当前 Thread…

MySQL数据的增删改查 where 条件查询 基础知识 【3】推荐

操作数据是数据库很重要的一部分,今天整理了下关于MySQL数据库数据的增删改查,包括基础查询、where条件查询、排序、分页、聚合、分组、having以及多表查询,多表查询的直接查询、内连接、外连接以及子查询。方便自己以后查看,也欢…

C++——多态经典案例(一)组装电脑

案例:小明打算买两台组装电脑,假设电脑零部件包括CPU、GPU和内存组成。 一台电脑使用intel的CPU、GPU和内存条 一台电脑使用Huawei的CPU、GPU和Intel的内存条 分析:使用多态进行实现 将CPU、GPU和内存条定义为抽象类,内部分别定义…

【docker快捷部署系列一】docker快速入门,安装docker,解决运行Docker Quickstart Terminal出错

1、docker快速入门 视频链接 知识点概述 docker是轻量级虚拟机image是镜像 相当于虚拟机快照container是容器,相当于运行起来的虚拟机程序Dockerfile 是创建docker镜像的自动化脚本docker-compose 是一个定义和运行多个容器命令的工具,包括运行Docker…

VsCode无法远程调试

一、问题描述 按照《VsCode gdb gdbserver远程调试C程序》中介绍的方法,配置好VsCode后,按下F5快捷键,或点击“Start Debugging”按钮,没有反应,无法启动调试: 二、解决方法 针对该问题,我尝…

【Material-UI】异步请求与Autocomplete的高效集成指南

文章目录 一、异步请求的两种用法1. 延迟加载(Load on open)实现方法 2. 动态搜索(Search as you type)实现方法 二、性能优化与注意事项1. 请求节流与去抖2. 禁用内置过滤3. 错误处理 三、实际应用案例:Google Maps P…