【数据结构】二叉树篇

embedded/2024/12/22 18:38:22/

文章目录

  • 1.二叉树链式结构功能的实现
    • 1.1 前置说明
    • 1.2 二叉树的遍历
      • 1.2.1 前序、中序以及后序遍历
      • 1.2.2 层序遍历
    • 1.3 节点个数以及高度差
      • 1.3.1 二叉树的节点个数
      • 1.3.2 二叉树叶子节点个数
      • 1.3.3 二叉树第K层节点个数
      • 1.3.4 二叉树树查找值为x的节点
      • 1.3.5 二叉树的销毁
    • 1.4 代码整合

1.二叉树链式结构功能的实现

1.1 前置说明

在学习二叉树的基本操作前，需要先创建一颗二叉树，然后才能学习相关的基本操作，由于现在大家可能堆二叉树结构掌握还不够深入，为了降低大家的学习成本，本文会手动创建一颗简单的二叉树，目的快速进入二叉树的操作学习。后续可能就要在C++篇章详讲二叉树了。

创建一个结构体，该结构体就是二叉树节点，主要维护节点的数据和指向左子树和右子树的指针。
再写一个创建节点的函数就可以开始建造二叉树了。

#define DataType inttypedef struct BinaryTreeNode
{DataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;//创建节点
BTNode* BuyNode(DataType x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}

下面我会手动创建一个如下图的二叉树：
二叉树

void CreateTree()
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);node1->left = node2;node1->right = node3;node2->left = node4;node2->right = node5;node3->left = node6;
}

注意：上述代码并不是创建二叉树的方式，正在创建二叉树的方式会再C++篇中再讲
在看二叉树基本操作前，再回顾下二叉树的概念，二叉树是：

  1. 空树
  2. 非空：根节点，根节点的左子树，根节点的右子树组成的。
    二叉树

从概念来看，二叉树的定义是递归式的因此后续遍历操作中基本都是按递归的方式来实现的。

1.2 二叉树的遍历

1.2.1 前序、中序以及后序遍历

学习二叉树结构，最简单的方式就是遍历。所谓二叉树的遍历是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问节点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，也是二叉树上进行其他运算的基础。
按照规则，二叉树的遍历有：前序/中序/后序的递归遍历

  1. 前序遍历（先序遍历）-- 访问根节点的操作发生在遍历其左右子树之前访问顺序：根-左-右
  2. 中序遍历 – 访问根节点的存在在遍历左右子树之中访问顺序：左-根-右
  3. 后序遍历 – 访问根节点的操作在遍历其左右子树之后访问顺序：左-右-根

由于被访问的节点是某子树的根，所以N(Node),L(Left)和R(Right)又可以解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别被称为先根遍历，中根遍历，和后根遍历。

//二叉树的先序遍历
void PreOrder(BTNode* root);
//二叉树的中序遍历
void InOrder(BTNode* root);
//二叉树的后序遍历
void PostOrder(BTNode* root);

下面开始解析：
二叉树

注意N表示空节点的意思
前面我们讲到，先序遍历的顺序是根-左-右
提问：这里的根-左-右是什么意思呢？
回答：当我们经过一个节点时，先会取到该节点的数据，然后会进入该节点的左子树当左子树的数据全部取出后，再进入右子树去取数据。期间经过的所有节点都会重复这一套流程。
当我们利用这一思路开始遍历时，先画出前序遍历的结果
前序遍历

了解完思路后，代码其实非常简洁明了的，我们先确定一个递归出口，当节点为空时。该节点肯定没有左右子树了，那么就可以返回了，不过要注意的是，我这里打印了N，打印N的目的是为了让前序遍历更加清晰，其实也是可以不打印的。
确定完递归出口后，就是递归的主要逻辑，当我们取出当前节点的数据后，就要继续找当前节点的左子树的数据，为此就需要调用先序遍历，传当前节点的左指针。同理当左子树完毕后就是右子树了。

//二叉树的先序遍历
void PreOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}printf("%d ", root->data);PreOrder(root->left);PreOrder(root->right);
}
//打印结果：
/*
1 2 4 N N 5 N N 3 6 N N N
*/

代码指向逻辑图：红色代表递进，绿色代表回归
代码运行图

中序遍历后后序遍历，其实都是类似的逻辑，大差不差的
中序遍历

//二叉树的中序遍历
void InOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}
//打印结果：
/*
N 4 N 2 N 5 N 1 N 6 N 3 N
*/

中序遍历

后序遍历：

//二叉树的后序遍历
void PostOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);
}
//打印结果
/*
N N 4 N N 5 2 N N 6 N 3 1
*/

后序遍历

1.2.2 层序遍历

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

1.3 节点个数以及高度差

下面将解释一些关于二叉树的常用功能

1.3.1 二叉树的节点个数

要数二叉树的节点个数，前面我们已经学会了二叉树的递归遍历，用到这里来就是了，这次我们不打印数据了，每经过一个节点就+1，然后进入该节点的左右子树。当遍历到空节点时就返回0，毕竟空节点可不算二叉树的节点个数的。

//二叉树的节点个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL)return 0;return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;//+1的位置随便放
}

1.3.2 二叉树叶子节点个数

要写出代码肯定要知道叶子节点的定义是什么，叶子节点就是没有度的节点。了解完这个，其实和上一个也没什么区别，无非就是把返回的节点从空变成了叶子节点，同时在返回的是还带来一个数据1。不过要注意的是，该函数依旧要判断节点为空的情况，如果初始时就传了一个空节点会导致程序崩溃的（解引用空指针）

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

1.3.3 二叉树第K层节点个数

别被什么第K层节点个数吓到了，其实也是很简单的。每次递进的时候就让k-1，当k==1时就说明到达了目标层数。不相信的话可以举几个例子。就比如第一层吧，刚进节点就成功匹配。

//二叉树第K层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL)return 0;return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1) + (k == 1);
}

1.3.4 二叉树树查找值为x的节点

返回的关键就是接收到的值是否为空，因为递归最终的时只会返回两种情况，一种就是找到了返回地址，一种就是返回NULL。了解完这两情况就很简单了，只有返回就是不是NULL就返回呗。

//二叉树树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, DataType x)
{if (root == NULL)return NULL;if (root->data == x)return root;BTNode* a = BinaryTreeFind(root->left, x);BTNode* b = BinaryTreeFind(root->right, x);if (a!=NULL||b!=NULL ){if (a != NULL)return a;elsereturn b;}return NULL;
}

1.3.5 二叉树的销毁

销毁要用后序遍历，可不能先释放。

//二叉树的销毁
void DestoryTree(BTNode* root)
{if (root == NULL)return;DestoryTree(root->left);DestoryTree(root->right);free(root);
}

1.4 代码整合

//tree.h
#include <stdio.h>
#include <stdlib.h>#define DataType inttypedef struct BinaryTreeNode
{DataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;//创建节点
BTNode* BuyNode(DataType x);//二叉树的先序遍历
void PreOrder(BTNode* root);//二叉树的中序遍历
void InOrder(BTNode* root);//二叉树的后序遍历
void PostOrder(BTNode* root);//二叉树的节点个数
int BinaryTreeSize(BTNode* root);//二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);//二叉树第K层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);//二叉树树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, DataType x);//二叉树的销毁
void DestoryTree(BTNode* root);//tree.c
#include "tree.h"//创建节点
BTNode* BuyNode(DataType x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}//二叉树的先序遍历
void PreOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}printf("%d ", root->data);PreOrder(root->left);PreOrder(root->right);
}//二叉树的中序遍历
void InOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}//二叉树的后序遍历
void PostOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);
}//二叉树的节点个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL)return 0;return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}//二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL)return 0;if (root->left == NULL && root->right == NULL)return 1;return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}//二叉树第K层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL)return 0;return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1) + (k == 1);
}//二叉树树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, DataType x)
{if (root == NULL)return NULL;if (root->data == x)return root;BTNode* a = BinaryTreeFind(root->left, x);BTNode* b = BinaryTreeFind(root->right, x);if (a!=NULL||b!=NULL ){if (a != NULL)return a;elsereturn b;}
}//二叉树的销毁
void DestoryTree(BTNode* root)
{if (root == NULL)return;DestoryTree(root->left);DestoryTree(root->right);free(root);
}//test.c
#include "tree.h"void CreateTree()
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);BTNode* node7 = BuyNode(6);node1->left = node2;node1->right = node3;node2->left = node4;node2->right = node5;node3->left = node6;node3->right = node7;//int n = BinaryTreeSize(node1);//int n = BinaryTreeLeafSize(node1);//int n = BinaryTreeLevelKSize(node1,3);//printf("%d", n);BTNode* tmp = BinaryTreeFind(node1, 1);
}int main()
{CreateTree();return 0;
}

http://www.ppmy.cn/embedded/97365.html

相关文章

OpenCV仿射变换

OpenCV仿射变换

图像的仿射变换涉及到图像的形状位置角度的变化&#xff0c;是深度学习预处理中常用到的功能&#xff0c;仿射变换主要是对图像的缩放&#xff0c;旋转&#xff0c;翻转和平移等操作的组合。 仿射变换&#xff1a;一个任意的仿射变换都能表示为 乘以一个矩阵 (线性变换) 接着再…
阅读更多...
【Unity实战】NavMeshAgent实现Strafe固定朝向移动

【Unity实战】NavMeshAgent实现Strafe固定朝向移动

众所周知&#xff0c;NavMeshAgent一旦设定了destination&#xff0c;它就会直奔目标。但是在一些场景中&#xff0c;比如NPC是个射手&#xff0c;除了瞄准玩家&#xff0c;也需要走位。如果不加以处理&#xff0c;我们恐怕会遇见瞄准IK和朝向…难以言表的表现&#xff0c;直接…
阅读更多...
electron 中的ipcMain.handle和ipcMain.on 的区别

electron 中的ipcMain.handle和ipcMain.on 的区别

在Electron中，ipcMain.handle和ipcMain.on是主进程（main process）用于处理来自渲染进程（renderer process）消息的两个主要方法，它们之间存在明显的区别，主要体现在消息处理的同步性、响应方式和应用场景上。 ipcMain.on 同步性：ipcMain.on是异步的。当渲染进程通过ipc…
阅读更多...
Matlab simulink建模与仿真 第一章（simulink入门）

Matlab simulink建模与仿真 第一章（simulink入门）

参考视频&#xff1a;simulink1.1simulink简介_哔哩哔哩_bilibili 一、simulink简介 1、simulink与MATLAB的关系 &#xff08;1&#xff09;MATLAB是一种以矩阵为来处理数据的的计算软件&#xff0c;其应用范围十分广泛&#xff0c;该产品由若干模块组成&#xff0c;simulin…
阅读更多...
web开发环境搭配与创建javaee项目

web开发环境搭配与创建javaee项目

一.web开发 (1)web开发指的是前端,后端,以及数据库进行交互&#xff0c;前端发送请求到后端&#xff0c;后端经过程序处理后到达数据库&#xff0c;最后在进行后端处理响应回前端。 (2)一次三端交互的doget或者dopost简单请求流程 (3)web开发除了需要前端,后端,数据库开发工具…
阅读更多...
Docker-安装软件

Docker-安装软件

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、安装MySQL&#xff08;一&#xff09;拉取MySQL镜像&#xff08;二&#xff09;运行MySQL容器&#xff08;1&#xff09;数据卷概念 &#xff08;三&#x…
阅读更多...
git的学习教程

git的学习教程

目录 1.初始化仓库 2.环境配置 2.1配置用户姓名&#xff1a; 2.2配置用户邮箱&#xff1a; ​编辑 2.3删除姓名配置&#xff1a; 2.4删除邮箱配置&#xff1a; 2.5全局配置姓名&#xff1a; 2.6全局配置邮箱&#xff1a; 2.7全局删除姓名&#xff1a; 2.8全局删除邮箱…
阅读更多...
vue 拦截器

vue 拦截器

拦截器——main.js中&#xff0c;可以编写 Axios.interceptors.request.use()来拦截所有的请求&#xff0c;对请求做相应护理后再放行搭配后端&#xff0c;这也是全局的&#xff0c;每个请求中无需自己处理 在main.js中配置 Axios.defaults.baseURLhttp://127.0.0.1:8088; …
阅读更多...
最新文章

Copyright @ 2022~2023