当前位置: 首页 > 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;专家们相信这个数字还会大幅增长。智能手机用户已…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)

说明&#xff1a; 想象一下&#xff0c;你正在用eNSP搭建一个虚拟的网络世界&#xff0c;里面有虚拟的路由器、交换机、电脑&#xff08;PC&#xff09;等等。这些设备都在你的电脑里面“运行”&#xff0c;它们之间可以互相通信&#xff0c;就像一个封闭的小王国。 但是&#…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例

使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件&#xff0c;常用于在两个集合之间进行数据转移&#xff0c;如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model&#xff1a;绑定右侧列表的值&…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

【安全篇】金刚不坏之身:整合 Spring Security + JWT 实现无状态认证与授权

摘要 本文是《Spring Boot 实战派》系列的第四篇。我们将直面所有 Web 应用都无法回避的核心问题&#xff1a;安全。文章将详细阐述认证&#xff08;Authentication) 与授权&#xff08;Authorization的核心概念&#xff0c;对比传统 Session-Cookie 与现代 JWT&#xff08;JS…...

数据结构第5章:树和二叉树完全指南(自整理详细图文笔记)

名人说&#xff1a;莫道桑榆晚&#xff0c;为霞尚满天。——刘禹锡&#xff08;刘梦得&#xff0c;诗豪&#xff09; 原创笔记&#xff1a;Code_流苏(CSDN)&#xff08;一个喜欢古诗词和编程的Coder&#x1f60a;&#xff09; 上一篇&#xff1a;《数据结构第4章 数组和广义表》…...

【免费数据】2005-2019年我国272个地级市的旅游竞争力多指标数据(33个指标)

旅游业是一个城市的重要产业构成。旅游竞争力是一个城市竞争力的重要构成部分。一个城市的旅游竞争力反映了其在旅游市场竞争中的比较优势。 今日我们分享的是2005-2019年我国272个地级市的旅游竞争力多指标数据&#xff01;该数据集源自2025年4月发表于《地理学报》的论文成果…...

TCP/IP 网络编程 | 服务端 客户端的封装

设计模式 文章目录 设计模式一、socket.h 接口&#xff08;interface&#xff09;二、socket.cpp 实现&#xff08;implementation&#xff09;三、server.cpp 使用封装&#xff08;main 函数&#xff09;四、client.cpp 使用封装&#xff08;main 函数&#xff09;五、退出方法…...