当前位置: 首页 > news >正文

数据结构 | 二叉树的各种遍历

数据结构 | 二叉树的各种遍历

文章目录

  • 数据结构 | 二叉树的各种遍历
    • 创建节点 && 创建树
    • 二叉树的前中后序遍历
    • 二叉树节点个数
    • 二叉树叶子节点个数
    • 二叉树第k层节点个数
    • 二叉树查找值为x的节点
    • 二叉树求树的高度
    • 二叉树的层序遍历
    • 判断二叉树是否是完全二叉树

我们本章来实现二叉树的这些功能

Tree.h

#pragma once#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;//创建节点
BTNode* BuyTreeNode(int x);
//创建树
BTNode* CreateTree();
// 二叉树销毁
void BinaryTreeDestory(BTNode* root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root);
// 求树的高度
int TreeHeight(BTNode* root);
  • 我们先来几个简单的

创建节点 && 创建树

  • 直接手动个创建即可,很简单~~
//创建节点
BTNode* BuyTreeNode(int x)
{BTNode* root = (BTNode*)malloc(sizeof(BTNode));if (root == NULL){perror("malloc fail\n");exit(-1);}root->data = x;root->left = NULL;root->right = NULL;return root;
}
//创建树
BTNode* CreateTree()
{BTNode* node1 = BuyTreeNode(1);BTNode* node2 = BuyTreeNode(2);BTNode* node3 = BuyTreeNode(3);BTNode* node4 = BuyTreeNode(4);BTNode* node5 = BuyTreeNode(5);BTNode* node6 = BuyTreeNode(6);BTNode* node7 = BuyTreeNode(7);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;node5->right = node7;return node1;
}

二叉树的前中后序遍历

  • 这里也是很简单,也可以看做下图这样遍历,或者画一下递归展开图

在这里插入图片描述

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}printf("%d ", root->data);BinaryTreePrevOrder(root->left);BinaryTreePrevOrder(root->right);
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}BinaryTreeInOrder(root->left);printf("%d ", root->data);BinaryTreeInOrder(root->right);
}
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}BinaryTreePostOrder(root->left);BinaryTreePostOrder(root->right);printf("%d ", root->data);
}

二叉树节点个数

  • 我们这里看一下递归展开图

在这里插入图片描述

int BinaryTreeSize(BTNode* root)
{return root == NULL ? 0 : BinaryTreeSize(root->left)+ BinaryTreeSize(root->right);
}

二叉树叶子节点个数

  • 为空就返回0
  • 不是空,是叶子,返回1
  • 不是空,也不是叶子,就递归左子树和右子树
int BinaryTreeLeafSize(BTNode* root)
{// 为空返回0if (root == NULL)return 0;//不是空,是叶子 返回1if (root->left == NULL && root->right == NULL)return 1;// 不是空 也不是叶子  分治=左右子树叶子之和return BinaryTreeLeafSize(root->left)+ BinaryTreeLeafSize(root->right);
}

二叉树第k层节点个数

  • k是1的时候就是一层,就返回1
  • 递归左子树加右子树,每次递归k-1
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL)return NULL;if (k == 1)return 1;//递归左子树加右子树,每次递归k-1return BinaryTreeLevelKSize(root->left, k - 1)+ BinaryTreeLevelKSize(root->right, k - 1);
}

二叉树查找值为x的节点

  • 先看根节点是不是要找的
  • 然后递归左子树和右子树
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL)return NULL;//根if (root->data == x)return root;//左子树BTNode* ret1 = BinaryTreeFind(root->left, x);if (ret1)return ret1;//右子树BTNode* ret2 = BinaryTreeFind(root->right, x);if (ret2)return ret2;return NULL;
}

二叉树求树的高度

  • 遍历左子树和右子树(每次遍历都要保存值)
  • 返回最高的那个子树然后加1(根)
int TreeHeight(BTNode* root)
{if (root == NULL)return NULL;//遍历左子树和右子树int left = TreeHeight(root->left);int right = TreeHeight(root->right);//返回最高的那个子树然后加1(根)return left > right ? left + 1 : right + 1;
}

二叉树的层序遍历

  • 这里的这个层序遍历就需要用到我们之前学过的队列了~~
  • 这里用法是入根(root),然后带孩子节点
void BinaryTreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);//先入根if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){//取队头的数据BTNode* front = QueueFront(&q);QueuePop(&q);//打印数据printf("%d ", front->data);//将左子树和右子树代入进队列if (front->left)QueuePush(&q, front->left);if (front->right)QueuePush(&q, front->right);}printf("\n");QueueDestroy(&q);
}
  • 那如果要一层一层的打印,代码改怎么改呢?
  • 一层一层的带,一层一层的出
// 层序遍历(一层一层的打印)
void _BinaryTreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);//先入根if (root)QueuePush(&q, root);int leveSize = 1;while (!QueueEmpty(&q)){while (leveSize--){//取队头的数据BTNode* front = QueueFront(&q);QueuePop(&q);printf("%d ", front->data);if (front->left)QueuePush(&q, front->left);if (front->right)QueuePush(&q, front->right);}printf("\n");leveSize = QueueSize(&q);}QueueDestroy(&q);
}

判断二叉树是否是完全二叉树

  • 和上面的代码基本一样,取数据如果遇到空就跳出
  • 如果前面遇到空以后,后面还有非空就不是完全二叉树
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);//先入根if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){// 取队头的数据BTNode* front = QueueFront(&q);QueuePop(&q);//等于空了就跳出,然后检查后面还有节点没有if (front == NULL)break;// 将左子树和右子树代入进队列QueuePush(&q, front->left);QueuePush(&q, front->right);}// 前面遇到空以后,后面还有非空就不是完全二叉树while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);// 如果是不是空就 return false;if (front){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}

相关文章:

数据结构 | 二叉树的各种遍历

数据结构 | 二叉树的各种遍历 文章目录 数据结构 | 二叉树的各种遍历创建节点 && 创建树二叉树的前中后序遍历二叉树节点个数二叉树叶子节点个数二叉树第k层节点个数二叉树查找值为x的节点二叉树求树的高度二叉树的层序遍历判断二叉树是否是完全二叉树 我们本章来实现二…...

Python-赋值运算符(详解)

表示赋值 左侧为变量&#xff0c;右边为值 a b 10#先把10赋值给b&#xff0c;再把b赋值给a 相当于a 10 b 10 链式赋值&#xff0c;但是不推荐&#xff0c;一般一行一个语句&#xff0c;提高可读性&#xff0c;良好的代码风格 多元赋值&#xff1a; a , b 10,20 #python语…...

算法工程师面试八股(搜广推方向)

文章目录 机器学习线性和逻辑回归模型逻辑回归二分类和多分类的损失函数二分类为什么用交叉熵损失而不用MSE损失&#xff1f;偏差与方差Layer Normalization 和 Batch NormalizationSVM数据不均衡特征选择排序模型树模型进行特征工程的原因GBDTLR和GBDTRF和GBDTXGBoost二阶泰勒…...

学习TypeScrip4(数组类型)

数组的类型 1.定义方法&#xff1a;类型[ ] //类型加中括号 let arr:number[] [123] //这样会报错定义了数字类型出现字符串是不允许的 let arr:number[] [1,2,3,1] //操作方法添加也是不允许的 let arr:number[] [1,2,3,] arr.unshift(1)var arr: number[] [1, 2, 3]; /…...

Python文件打包成exe可执行文件

我们平常用python写些脚本可以方便我们的学习办公&#xff0c;但限制就是需要有python环境才能运行。 那能不能直接在没有python环境的电脑上运行我们的脚本呢&#xff1f; 当然可以&#xff0c;那就是直接把python脚本打包成exe可执行程序&#xff08;注针对win系统&#xf…...

Android : SQLite 增删改查—简单应用

示例图&#xff1a; 学生实体类 Student.java package com.example.mysqlite.dto;public class Student {public Long id;public String name;public String sex;public int age;public String clazz;public String creatDate;//头像public byte[] logoHead;Overridepublic St…...

【蓝桥杯】马的遍历

马的遍历 题目描述 有一个 n m n \times m nm 的棋盘&#xff0c;在某个点 ( x , y ) (x, y) (x,y) 上有一个马&#xff0c;要求你计算出马到达棋盘上任意一个点最少要走几步。 输入格式 输入只有一行四个整数&#xff0c;分别为 n , m , x , y n, m, x, y n,m,x,y。 …...

导入JSON到xmind

写在前面 这只是一个思路&#xff0c;解决大量树状数据&#xff0c;创建xmind低效问题。 函数可以根据你的实际情况优化 1. 转换json格式 function formatToXimd(atd, str) {if (atd) {for (let index 0; index < atd.length; index) {console.log(str - atd[index].…...

DataGrip 2023.2.3(IDE数据库开发)

DataGrip是一款数据库集成开发环境&#xff08;IDE&#xff09;&#xff0c;用于数据库管理和开发。 DataGrip提供了许多强大的功能&#xff0c;如SQL语句编辑、数据库连接管理、数据导入和导出、数据库比较和同步等等。它支持多种数据库&#xff0c;如MySQL、PostgreSQL、Ora…...

身为 Go 程序员,我为啥更喜欢用 Zig?

Zig 是一种比较新的编程语言&#xff0c;于 2016 年首次推出。Zig 社区将其描述为“一种用于维护稳固的、可优化和可重用软件的通用编程语言”。 看似一句简单的描述&#xff0c;却隐藏着远大的抱负。Zig被看作是可与C语言一较高下的编程语言。此外&#xff0c;Zig 也是一个编…...

Amazon CodeWhisperer 使用体验

文章作者&#xff1a;STRIVE Amazon CodeWhisperer 是最新的代码生成工具&#xff0c;支持多种编程语言&#xff0c;如 java,js,Python 等&#xff0c;能减少开发人员手敲代码时间&#xff0c;提升工作效率。PS:本人是一名 CodeWhisperer 业余爱好者 亚马逊云科技开发者社区为开…...

公众号留言功能怎么申请?

为什么公众号没有留言功能&#xff1f;2018年2月12日&#xff0c;TX新规出台&#xff1a;根据相关规定和平台规则要求&#xff0c;我们暂时调整留言功能开放规则&#xff0c;后续新注册帐号无留言功能。这就意味着2018年2月12日号之后注册的公众号不论个人主体还是组织主体&…...

探索三种生成模型:基于DDPMs、NCSNs和SDEs方法的Diffusion

探索三种生成模型&#xff1a;基于DDPMs、NCSNs和SDEs方法的Diffusion 去噪扩散概率模型&#xff08;DDPMs&#xff09;正向过程反向过程 噪声条件得分网络&#xff08;NCSNs&#xff09;正向过程初始化训练 NCSNs生成样本 反向过程 随机微分方程&#xff08;SDEs&#xff09;原…...

Linux随记(七)

一、欧拉bclinux 21.10安装zabbix-5.0.37.tar.gz &#xff08;zbx-客户端&#xff09; #系统环境&#xff1a; BigCloud Enterprise Linux For Euler 21.10 LTS #软件信息&#xff1a; zabbix-5.0.37.tar.gz &#xff0c; pcre-devel-8.44-2.oe1.x86_64.rpm &#xff0c; inst…...

RESTful API,以及如何使用它构建 web 应用程序。

RESTful API是一种基于REST&#xff08;Representational State Transfer&#xff09;架构风格的API&#xff08;Application Programming Interface&#xff09;&#xff0c;它采用HTTP协议中的GET、POST、PUT、DELETE等方法&#xff0c;对资源进行操作。RESTful API的核心思想…...

【华为OD题库-075】拼接URL-Java

题目 题目描述: 给定一个url前缀和url后缀,通过,分割。需要将其连接为一个完整的url。 如果前缀结尾和后缀开头都没有/&#xff0c;需要自动补上/连接符 如果前缀结尾和后缀开头都为/&#xff0c;需要自动去重 约束:不用考虑前后缀URL不合法情况 输入描述: url前缀(一个长度小于…...

【Unity动画】为一个动画片段添加事件Events

动画不管播放到那一帧&#xff0c;我们都可以在这里“埋伏”一个事件&#xff08;调用一个函数并且给函数传递一个参数&#xff0c;参数在外部设置&#xff0c;甚至传递一个物体&#xff09;&#xff01; 嗨&#xff0c;亲爱的Unity小伙伴们&#xff01;你是否曾想过为你的动画…...

CoDeF视频处理——视频风格转化部署使用与源码解析

一、算法简介与功能 CoDef是作为一种新型的视频表示形式&#xff0c;它包括一个规范内容场&#xff0c;聚合整个视频中的静态内容&#xff0c;以及一个时间变形场&#xff0c;记录了从规范图像&#xff08;即从规范内容场渲染而成&#xff09;到每个单独帧的变换过程。针对目标…...

ubuntu server 20.04 备份和恢复 系统 LTS

ubuntu server 20.04 备份和恢复 系统 LTS tar命令系统备份与恢复&#xff08;还原or新装&#xff09; 备份系统 cd / su root tar cvpzf backup.tgz --exclude/tmp --exclude/run --exclude/dev --exclude/snap --exclude/proc --exclude/lostfound --exclude/backup.tgz …...

NFC对物联网开发的影响及用途

当谈到NFC对物联网的影响时&#xff0c;不得不提它的几个重要的优势&#xff0c;可能在未来几年影响着物联网的发展方向。 全球智能手机的普及是其中一个重要因素&#xff1a;市面上已有数十亿部支持NFC的智能手机&#xff0c;专家们相信这个数字还会大幅增长。智能手机用户已…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论

路径问题的革命性重构&#xff1a;基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中&#xff08;图1&#xff09;&#xff1a; mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...

GitFlow 工作模式(详解)

今天再学项目的过程中遇到使用gitflow模式管理代码&#xff0c;因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存&#xff0c;无论是github还是gittee&#xff0c;都是一种基于git去保存代码的形式&#xff0c;这样保存代码…...