【数据结构】二叉树的链式结构

【数据结构】二叉树的链式存储结构

二叉树的存储结构

typedef int BTDataType;
// 二叉树的结构
typedef struct BinaryTreeNode {BTDataType data;             // 树的值struct BinaryTreeNode *left; // 左孩子struct BinaryTreeNode *right;// 右孩子
} BinaryTreeNode;

二叉树的深度优先遍历

在这里插入图片描述

前序遍历

前序遍历，又叫先根遍历。
遍历顺序：根 -> 左子树 -> 右子树

代码：

// 前序遍历
void BinaryTreePrevOrder(BinaryTreeNode *root) {// 前序遍历 根、左子树、右子树// 如果root为空，递归结束if (root == NULL) {printf("NULL ");return;}printf("%d ", root->data);BinaryTreePrevOrder(root->left);BinaryTreePrevOrder(root->right);
}

中序遍历

中序遍历，又叫中根遍历。
遍历顺序：左子树 -> 根 -> 右子树

代码：

// 中序遍历
void BinaryTreeInOrder(BinaryTreeNode *root) {// 中序遍历 - 左子树、根、右子树if (root == NULL) {printf("NULL ");return;}BinaryTreeInOrder(root->left);printf("%d ", root->data);BinaryTreeInOrder(root->right);
}

后序遍历

后序遍历，又叫后根遍历。
遍历顺序：左子树 -> 右子树 -> 根

代码：

// 后序遍历
void BinaryPostOrder(BinaryTreeNode *root) {// 后序遍历 - 左子树、右子树、根if (root == NULL) {printf("NULL ");return;}BinaryPostOrder(root->left);BinaryPostOrder(root->right);printf("%d ", root->data);
}

二叉树的广度优先遍历

层序遍历

除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层 上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

在这里插入图片描述

思路（借助一个队列）：

  1. 先把根入队列，然后开始从队头出数据。
  2. 出队头的数据，把它的左孩子和右孩子依次从队尾入队列（NULL不入队列）。
  3. 重复进行步骤2，直到队列为空为止。

img

特点：借助队列先进先出的性质，上一层数据出队列的时候带入下一层数据。

// 层序遍历 - 利用队列
void BinaryTreeLevelOrder(BinaryTreeNode *root) {// 创建一个队列，队列中入数据，取队头，然后带左右子树，出一个数，带一个树的所有子树Queue q;QueueInit(&q);if (root) {// root不为NULL，就入队列QueuePush(&q, root);}while (!QueueEmpty(&q)) {// 取队头，打印BinaryTreeNode *front = QueueFront(&q);printf("%d ", front->data);// 取完POPQueuePop(&q);// 取队头，带下一层,if (front->left) {QueuePush(&q, front->left);}if (front->right) {QueuePush(&q, front->right);}}printf("\n");QueueDestroy(&q);
}

二叉树的节点个数

求解树的节点总数时，可以将问题拆解成子问题：

  1. 若为空，则结点个数为0。
  2. 若不为空，则结点个数 = 左子树节点个数 + 右子树节点个数 + 1（自己）。

代码：

// 求二叉树节点个数
int BinaryTreeSize(BinaryTreeNode *root) {if (root == NULL) {return 0;}return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

二叉树的叶子节点个数

子问题拆解：

  1. 若为空，则叶子结点个数为0。
  2. 若结点的左指针和右指针均为空，则叶子结点个数为1。
  3. 除上述两种情况外，说明该树存在子树，其叶子结点个数 = 左子树的叶子结点个数 + 右子树的叶子结点个数。

代码：

// 求二叉树的叶子节点个数
int BinaryTreeLeafSize(BinaryTreeNode *root) {if (root == NULL) {return 0;}if (root->left == NULL && root->right == NULL) {return 1;}return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

第K层节点的个数

思路：
相对于根结点的第k层结点的个数 = 相对于以其左孩子为根的第k-1层结点的个数 + 相对于以其右孩子为根的第k-1层结点的个数。

在这里插入图片描述

代码：

// 求第k层的节点个数 k>=1
int BinaryTreeLevelSize(BinaryTreeNode *root, int k) {if (root == NULL) {return 0;}if (k == 1) {return 1;}return BinaryTreeLevelSize(root->left, k - 1) + BinaryTreeLevelSize(root->right, k - 1);
}

值为x的节点

子问题：

  1. 先判断根结点是否是目标结点。
  2. 再去左子树中寻找。
  3. 最后去右子树中寻找。

代码：

// 二叉树查找值为x的节点
BinaryTreeNode *BinaryTreeFind(BinaryTreeNode *root, BTDataType x) {if (root == NULL) {return NULL;}if (root->data == x) {return root;}// 左子树递归的节点保存到leftTree中,如果leftTree不为NULL，则return leftTreeBinaryTreeNode *leftTree = BinaryTreeFind(root->left, x);if (leftTree) {return leftTree;}// 右子树递归的节点保存到rightTree中,如果rightTree不为NULL，则return rightTreeBinaryTreeNode *rightTree = BinaryTreeFind(root->right, x);if (rightTree) {return rightTree;}// 找不到，返回NULLreturn NULL;
}

树的高度

子问题：

  1. 若为空，则深度为0。
  2. 若不为空，则树的最大深度 = 左右子树中深度较大的值 + 1。

代码：

// 求二叉树的高度
int BinaryTreeHeight(BinaryTreeNode *root) {// 求左子树的高度，右子树的高度// 取最大的if (root == NULL) {return 0;}int leftHeight = BinaryTreeHeight(root->left);int rightHeight = BinaryTreeHeight(root->right);//如果左右子树两边相等就取左边的高度,所以大于等于return leftHeight >= rightHeight ? leftHeight + 1 : rightHeight + 1;
}

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

判断二叉树是否是完全二叉树的方法与二叉树的层序遍历类似，但又有一些不同。

思路（借助一个队列）：

  1. 先把根入队列，然后开始从队头出数据。
  2. 出队头的数据，把它的左孩子和右孩子依次从队尾入队列（NULL也入队列）。
  3. 重复进行步骤2，直到读取到的队头数据为NULL时停止入队列。
  4. 检查队列中剩余数据，若全为NULL，则是完全二叉树；若其中有一个非空的数据，则不是完全二叉树。

在这里插入图片描述

代码：

// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BinaryTreeNode *root) {// 层序走，走到第一个为空的时候，就跳出去，如果是满二叉树，后面的节点都应该为空Queue q;QueueInit(&q);if (root) {QueuePush(&q, root);}while (!QueueEmpty(&q)) {BinaryTreeNode *front = QueueFront(&q);QueuePop(&q);if (front == NULL) {break;} else {QueuePush(&q, front->left);QueuePush(&q, front->right);}}// 出到空以后，如果后面全是空，则是完全二叉树while (!QueueEmpty(&q)) {BinaryTreeNode *front = QueueFront(&q);QueuePop(&q);if (front != NULL) {QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}

判断二叉树是否是单值二叉树

单值二叉树，所有节点的值都相同的二叉树即为单值二叉树，判断某一棵二叉树是否是单值二叉树的一般步骤如下：

  1. 判断根的左孩子的值与根结点是否相同。
  2. 判断根的右孩子的值与根结点是否相同。
  3. 判断以根的左孩子为根的二叉树是否是单值二叉树。
  4. 判断以根的右孩子为根的二叉树是否是单值二叉树。

若满足以上情况，则是单值二叉树。

注：空树也是单值二叉树。

代码：

//求单值二叉树
bool isUnivalTree(BinaryTreeNode *root) {if (root == nullptr) {return true;}if (root->left && root->data != root->left->data) {return false;}if (root->right && root->data != root->right->data) {return false;}return isUnivalTree(root->left) && isUnivalTree(root->right);
}

判断二叉树是否是对称二叉树

对称二叉树，这里所说的对称是指镜像对称：

要判断某二叉树是否是对称二叉树，则判断其根结点的左子树和右子树是否是镜像对称即可。因为是镜像对称，所以左子树的遍历方式和右子树的遍历方式是不同的，准确来说，左子树和右子树的遍历是反方向进行的。

代码：

//求对称二叉树
bool _isSymmetric(BinaryTreeNode *left, BinaryTreeNode *right) {// 两个都为NULL，对称if (left == NULL && right == NULL)return true;// 两个其中一个为NULL，一个不为NULL，不对称if (left == NULL || right == NULL)return false;// left的左孩子的值和right的值不相等，不对称if (left->data != right->data)return false;// 左子树的左孩子，和右子树的右孩子对比，然后左子树的右孩子和右子树的左孩子在对比return _isSymmetric(left->left, right->right) && _isSymmetric(left->right, right->left);
}bool isSymmetric(BinaryTreeNode *root) {if (root == nullptr) {return true;}return _isSymmetric(root->left, root->right);
}

翻转二叉树

思路：

  1. 翻转左子树。
  2. 翻转右子树。
  3. 交换左右子树的位置。

代码：

BinaryTreeNode *invertTree(BinaryTreeNode *root) {if (root == nullptr) {return nullptr;}BinaryTreeNode *leftTree = invertTree(root->left);BinaryTreeNode *rightTree = invertTree(root->right);root->left = rightTree;root->right = leftTree;return root;
}

二叉树的构建和销毁

// 申请树节点
BinaryTreeNode *BuyBinaryTreeNode(BTDataType x) {BinaryTreeNode *newnode = (BinaryTreeNode *) malloc(sizeof(BinaryTreeNode));if (newnode == NULL) {perror("malloc fail");exit(-1);}newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BinaryTreeNode *BinaryTreeCreate(BTDataType *a, int *pi) {if (a[*pi] == '#') {(*pi)++;return NULL;}BinaryTreeNode *root = (BinaryTreeNode *) malloc(sizeof(BinaryTreeNode));if (root == NULL) {perror("malloc fail");exit(-1);}root->data = a[(*pi)++];root->left = BinaryTreeCreate(a, pi);root->right = BinaryTreeCreate(a, pi);return root;
}

销毁：

// 二叉树销毁
void BinaryTreeDestory(BinaryTreeNode **root) {if (*root == NULL) {return;}// 后序遍历销毁，根要最后释放BinaryTreeDestory(&(*root)->left);BinaryTreeDestory(&(*root)->right);free(*root);*root = NULL;
}

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

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

相关文章

跟模型和中间层聊聊：什么是最好的AI原生应用？

跟模型和中间层聊聊：什么是最好的AI原生应用？

软件 2.0 注定会发生：所有软件都值得用神经网络重做一遍。 这个 OpenAI 大神 Karpathy 多年前的预言，指向了今天 LLM 应用层的一个关键问题——如何基于 LLM 能力，设计好 AI 原生应用。 我们看到，应用层的创业者们感到悲观、质疑和…
阅读更多...
腾讯发布超千亿参数规模的混元大模型；深度学习与音乐分析与生成课程介绍

腾讯发布超千亿参数规模的混元大模型；深度学习与音乐分析与生成课程介绍

🦉 AI新闻 🚀 腾讯发布超千亿参数规模的混元大模型 摘要：腾讯在2023腾讯全球数字生态大会上发布混元大模型，该模型拥有超千亿的参数规模和超2万亿 tokens 的预训练语料。混元大模型将支持多轮对话、内容创作、逻辑推理、知识增强…
阅读更多...
计算机毕设 大数据上海租房数据爬取与分析可视化 -python 数据分析 可视化

计算机毕设 大数据上海租房数据爬取与分析可视化 -python 数据分析 可视化

# 1 前言 🔥 这两年开始毕业设计和毕业答辩的要求和难度不断提升，传统的毕设题目缺少创新和亮点，往往达不到毕业答辩的要求，这两年不断有学弟学妹告诉学长自己做的项目系统达不到老师的要求。 为了大家能够顺利以及最少的精力通…
阅读更多...
Zookeeper应用场景和底层设计

Zookeeper应用场景和底层设计

一、什么是zookeeper Zookeeper是一个开源的分布式协调服务框架，它是服务于其它集群式框架的框架。 【简言之】 有一个服务A，以集群的方式提供服务。只需要A专注于它提供的服务就可以，至于它如何以多台服务器协同完成任务的事情&#xff0c…
阅读更多...
(文末赠书)我为什么推荐应该人手一本《人月神话》

(文末赠书)我为什么推荐应该人手一本《人月神话》

能点进来的朋友，说明你肯定是计算机工作的朋友或者对这本书正在仔细琢磨着的朋友。 文章目录 1、人人都会编程的时代，我们如何留存?2、小故事说明项目管理着为什么必看这本书3、如何评价《人月神话：纪念典藏版》4、本书的目录（好…
阅读更多...
科技资讯|苹果Vision Pro获得被动冷却系统及数字表冠控制界面专利

科技资讯|苹果Vision Pro获得被动冷却系统及数字表冠控制界面专利

据patentlyapple报道，美国专利商标局正式授予苹果一项与头戴式设备（Apple Vision Pro）相关的专利11751366，该设备可以提供被动冷却系统，利用光学组件的表面来管理热量，而不会对用户显示的视觉信息产生不利影…
阅读更多...
博客系统（升级（Spring））(四)（完）基本功能（阅读，修改，添加，删除文章）（附带项目）

博客系统（升级（Spring））(四)（完）基本功能（阅读，修改，添加，删除文章）（附带项目）

博客系统 (三） 博客系统博客主页前端后端个人博客前端后端显示个人文章删除文章 修改文章前端后端提取文章修改文章 显示正文内容前端后端文章阅读量功能 添加文章前端后端 如何使用Redis项目地点： 博客系统 博客系统是干什么的？ CSDN就是一…
阅读更多...
【用unity实现100个游戏之10】复刻经典俄罗斯方块游戏

【用unity实现100个游戏之10】复刻经典俄罗斯方块游戏

文章目录 前言开始项目网格生成Block方块脚本俄罗斯方块基类，绘制方块形状移动逻辑限制移动自由下落下落后设置对应风格为不可移动类型检查当前方块是否可以向指定方向移动旋转逻辑消除逻辑游戏结束逻辑怪物生成源码参考完结 前言 当今游戏产业中，经典游…
阅读更多...
关于HTTP协议的概述

关于HTTP协议的概述

HTTP 的报文大概分为三大部分。第一部分是请求行，第二部分是请求的首部，第三部分才是请求的正文实体。 POST 往往是用来创建一个资源的，而 PUT 往往是用来修改一个资源的。 Accept-Charset，表示客户端可以接受的字符集。防止传过…
阅读更多...
YOLOv5：修改backbone为ConvNeXt

YOLOv5：修改backbone为ConvNeXt

YOLOv5：修改backbone为ConvNeXt 前言前提条件相关介绍ConvNeXtYOLOv5修改backbone为ConvNeXt修改common.py修改yolo.py修改yolov5.yaml配置 参考 前言 记录在YOLOv5修改backbone操作，方便自己查阅。由于本人水平有限，难免出现错漏&#xff0c…
阅读更多...
python 列表常用方法

python 列表常用方法

python的列表和js的数组是相似的 mylist ["add", "item", "msg", "add", "add", "add"] # 语句[索引] 值 改变列表中某一项的值 # mylist[1] 122 # insert插入值 # mylist.insert(2, "age") # appe…
阅读更多...
Vite和Webpack如何使用CDN包

Vite和Webpack如何使用CDN包

为了精简打包输出的dist目录大小，我们可以引入CDN外部包的方式，来缩小打包的体积，加快打包速度。这里介绍Vite和Webpack中如何引入React CDN外部包。 一、Vite引入CDN包 1、安装插件 npm i vitejs/plugin-react-refresh vite-plugin-cdn-i…
阅读更多...
无涯教程-JavaScript - BESSELK函数

无涯教程-JavaScript - BESSELK函数

描述 BESSELK函数返回修改后的Bessel函数Kn(x),该函数等效于针对纯虚参判断的Bessel函数。 这些也称为双曲贝塞尔函数。 语法 BESSELK(X, N)争论 Argument描述Required/OptionalXThe value at which to evaluate the function.RequiredNThe order of the function. If n i…
阅读更多...
深度学习-全连接神经网络-训练过程-欠拟合、过拟合和Dropout- [北邮鲁鹏]

深度学习-全连接神经网络-训练过程-欠拟合、过拟合和Dropout- [北邮鲁鹏]

目录标题 机器学习的根本问题过拟合overfitting泛化能力差。应对过拟合最优方案次优方案调节模型大小约束模型权重，即权重正则化(常用的有L1、L2正则化)L1 正则化L2 正则化对异常值的敏感性随机失活(Dropout)随机失活的问题 欠拟合 机器学习的根本问题 机器学习的根…
阅读更多...
WebRTC 源码 编译 iOS端

WebRTC 源码 编译 iOS端

1. 获取依赖工具 首先，确保你已经安装了以下工具： GitDepot ToolsXcode（确保已安装命令行工具） 2. 下载 depot_tools 使用 git 克隆 depot_tools 并将其添加到你的 PATH 中： /path/to/depot_tools 替换为自己的路径…
阅读更多...
正规股票配资网站的三个明显特点分析

正规股票配资网站的三个明显特点分析

随着股票市场的快速发展，越来越多的投资者开始考虑使用股票配资来增加自己的资金流动性和收益率。然而，在选择股票配资网站时，投资者往往难以辨别哪些网站是正规的，哪些网站存在风险。因此，以下将分析正规股票配资网站…
阅读更多...
如果你想了解远程工作，这篇文章不容错过

如果你想了解远程工作，这篇文章不容错过

大家好，好久不见，我好久都没写原创文章了。 最近周边的越来越多朋友来找我了解远程工作相关的问题，正好这个月也是我远程工作一年半了，所以就写篇文章聊聊关于这块的话题吧。 语言问题 首先远程工作基本分两种团队，一种…
阅读更多...
实用工具JRebel XRebel【2023】配置和使用的详解

实用工具JRebel XRebel【2023】配置和使用的详解

🥳🥳Welcome Huihuis Code World ! !🥳🥳 接下来看看由辉辉所写的关于JRebel & XRebel的相关操作吧 目录 🥳🥳Welcome Huihuis Code World ! !🥳🥳 一.JRebel 的简介 二.插件的…
阅读更多...
学习javaEE初阶的第一堂课

学习javaEE初阶的第一堂课

学习金字塔 java发展简史 Java最初诞生的时候是用来写前端的!! 199x年 199x年,互联网还处在比较早期的阶段,当时主流的编程语言是 C/C, 有个大佬要搞个"智能面包机",觉得用C来做太难了 于是就基于C搞了个简单点的语言,Java 就诞生了~~ 遗憾的是项目流产了,没做成…
阅读更多...
day6_C++

day6_C++

day6_C 模板 栈模板 队列思维导图 模板 栈 stack.h #ifndef STACK_H #define STACK_H#include <iostream> #include <cstring>using namespace std;#define MAX 5template<typename T> class Stack { public:/*构造函数*/Stack();/*拷贝构造函数*/Stack(co…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023