【数据结构第十六节】实现链式结构二叉树（详细递归图解—呕心沥血版！）

ops/2025/2/25 5:37:29/

必须有为成功付出代价的决心，然后想办法付出这个代价。云边有个稻草人-CSDN博客

这节课挺抽象（苦笑），没事，我会帮你！干就完了！

（目录在路上）

正文开始——

引言

用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点有三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在链结点的存储地址，结构见下：

//创建链式结构二叉树的结构->二叉链
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType* data;struct BinaryTreeNode* left;//指定当前结点的左孩子struct BinaryTreeNode* right;//指定当前结点的右孩子
}BTNode;

二叉树的创建方式比较复杂，为了更好地步入到二叉树内容中，我们先手动创建一棵链式二叉树。

//申请结点
BTNode* BuyNode(BTDataType x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc faile!");exit(1);}newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}BTNode* CreateTree()
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);//改变指针指向，使其成为一棵链式二叉树node1->left = node2;node1->right = node3;node2->left = node4;return node1;}

回顾二叉树的概念，二叉树分为空树和非空二叉树，非空二叉树由根节点、根节点的左子树和根节点的右子树组成的。

根节点的左子树和右子树分别又是由子树节点、子树结点的左子树和子树结点的右子树组成的，因此二叉树是递归式的，后序链式二叉树的操作基本都是按照概念实现的。

一、前中后序遍历

1.1 遍历规则

按照规则，二叉树的遍历有：前序 /中序/ 后序的遍历结构：

  • 前序遍历（Preorder Traversal 亦称先序遍历）：访问根结点的操作发生在遍历其左右子树之前，访问的顺序：根节点、左子树、右子树
  • 中序遍历（Inorder Traversal）：访问根节点的操作发生在遍历其左右子树之间，访问顺序：左子树、根节点、右子树
  • 后序遍历（Postorder Traversal）：访问根节点的操作发生在遍历其左右子树之后，访问顺序：左子树、右子树、根节点

1.2 代码实现

（1）前序遍历

//前序遍历
void PreOrder(BTNode* root)
{if (root == NULL){return;}printf("%d ", root->data);PreOrder(root->left);PreOrder(root->right);
}

该图里面，前序遍历结果为：1 2 4 3 

（2）中序遍历

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

中序遍历结果为：4  2  1  3 

（3）后序遍历

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

二、结点个数以及高度等

2.1 二叉树结点个数

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

2.2 二叉树叶子结点的个数

//二叉树叶子结点个数
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);
}

2.3 二叉树第K层结点的个数

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

2.4 求二叉树的高度/深度

//求二叉树高度/深度
int BinaryTreeDepth(BTNode* root)
{if (root == NULL){return 0;}int leftDep = BinaryTreeDepth(root->left);int rightDep = BinaryTreeDepth(root->right);return leftDep > rightDep ? leftDep + 1 : rightDep + 1;
}

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

//二叉树找值为x的结点
BTNode* BinaryFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode* leftFind = BinaryFind(root->left, x);if (leftFind){return leftFind;}BTNode* rightFind = BinaryFind(root->right, x);if (rightFind){return rightFind;}return NULL;
}

2.6 二叉树的销毁

//二叉树的销毁
void BinaryTreeDestroy(BTNode** root)
{if (*root == NULL){return;}BinaryTreeDestroy(&((*root)->left));//注意这里的传参，传的是地址BinaryTreeDestroy(&((*root)->right));free(*root);*root = NULL;
}

三、层序遍历

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

我们要提前实现一个队列的结构，（1）在下面的函数里面我们创建一个队列，并且别忘记队列的初始化和销毁，（2）同时要注意，我们前面学习的队列里面的数据是整型类型，这次我们要将结点插入到队列里面，所以我们要将队列里面的数据类型改为二叉树节点的类型，并且我们不能直接写二叉树节点的缩写那样，我们要写成 struct BinaryTreeNode* / struct BTNode* ，反正都不能少 struct，不然会报错。（3）还有一点，在我们的层序遍历代码里面当while循环结束的时候队列为NULL，下一步再进行队列的销毁的时候就会报错，因为我们前面实现的队列的销毁里面队列为空时不能销毁，所以assert会报错，所以我们可以把队列的销毁里面判断队列是否为空的那一步给注释掉。

提及到的代码需要注意的点都在下面，多看看！

//创建节点的结构
typedef struct BinaryTreeNode* QUDatatype;//这里需要注意
typedef struct QueueNode
{QUDatatype data;struct QueueNode* next;
}QueueNode;
//销毁
void QueueDestroy(Queue* pq)
{assert(pq);//assert(!QueueEmpty(pq));//往这看，注释掉这里也没事，就算队列为空也没关系//此时pcur为NULL，进不去循环QueueNode* pcur = pq->phead;while (pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}

//层序遍历
void LevelBinaryTree(BTNode* root)
{//先创建一个队列Queue q;QueueInit(&q);//取根节点入队列QueuePush(&q, root);while (!QueueEmpty(&q)){//打印队头数据BTNode* Front = QueueFront(&q);printf("%d ", Front->data);QueuePop(&Front);if (Front->left){QueuePush(&q, Front->left);}if (Front->right){QueuePush(&q, Front->right);}}QueueDestroy(&q);
}

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

//判断是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);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);if (front != NULL){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}

【图解】

五、本节课代码汇总

 Queue.h

#pragma once
#include<stdbool.h>
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//创建节点的结构
typedef struct BinaryTreeNode* QUDatatype;
typedef struct QueueNode
{QUDatatype data;struct QueueNode* next;
}QueueNode;//创建队列的结构
typedef struct Queue
{QueueNode* phead;QueueNode* ptail;int size;
}Queue;//初始化
void QueueInit(Queue* pq);//入队列
void QueuePush(Queue* pq,QUDatatype x);//判空
bool QueueEmpty(Queue* pq);//出队列
void QueuePop(Queue* pq);//取队头数据
QUDatatype QueueTop(Queue* pq);//去队尾数据
QUDatatype QueueBack(Queue* pq);//去队列中有效数据的个数
int QueueSize(Queue* pq);//销毁
void QueueDestroy(Queue* pq);

Queue.c

#include"Queue.h"void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}//入队列
void QueuePush(Queue* pq, QUDatatype x)
{assert(pq);//现申请新的结点QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;//如果为空if (pq->phead == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}//判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL;
}//出队列
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;}else{QueueNode* pcur = pq->phead->next;free(pq->phead);pq->phead = pcur;}pq->size--;
}//取队头数据
QUDatatype QueueTop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->phead->data;}//去队尾数据
QUDatatype QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->ptail->data;
}int QueueSize(Queue* pq)
{assert(pq);/*QueueNode* pcur = pq->phead;int count = 0;while (pcur){count++;QueuePop(pq);pcur = pq->phead;}*//*return count;*/return pq->size;
}//销毁
void QueueDestroy(Queue* pq)
{assert(pq);//assert(!QueueEmpty(pq));QueueNode* pcur = pq->phead;while (pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}

Tree.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//创建链式结构二叉树的结构->二叉链
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;//指定当前节点的左孩子struct BinaryTreeNode* right;//指定当前节点的右孩子
}BTNode;//申请节点
BTNode* BuyNode(BTDataType x);//前序遍历
void PreOrder(BTNode* root);//中序遍历
void InOrder(BTNode* root);//后序遍历
void PosOrder(BTNode* root);//求二叉树节点的个数
int BinaryTreeSize(BTNode* root);//二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root);//第K层节点个数
int BinaryTreeLevelKSize(BTNode* root,int k);//求二叉树高度/深度
int BinaryTreeDepth(BTNode* root);//找X的结点
BTNode* BinaryFind(BTNode* root, BTDataType x);//二叉树的销毁
void BinaryTreeDestroy(BTNode** root);//层序遍历
void LevelBinaryTree(BTNode* root);//判断是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);

Tree.c

#include"Tree.h"
#include"Queue.h"//申请节点
BTNode* BuyNode(BTDataType x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc faile!");exit(1);}newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}//前序遍历-
void PreOrder(BTNode* root)
{if (root == NULL){return;}printf("%d ", root->data);PreOrder(root->left);PreOrder(root->right);
}//中序遍历--左根右
void InOrder(BTNode* root)
{if (root == NULL){return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
} //后序遍历--左右根
void PosOrder(BTNode* root)
{if (root == NULL){return;}PosOrder(root->left);PosOrder(root->right);printf("%d ", root->data);
}//求二叉树节点的个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}//二叉树叶子结点个数
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;}if (k == 1){return 1;}return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}//求二叉树高度/深度
int BinaryTreeDepth(BTNode* root)
{if (root == NULL){return 0;}int leftDep = BinaryTreeDepth(root->left);int rightDep = BinaryTreeDepth(root->right);return leftDep > rightDep ? leftDep + 1 : rightDep + 1;
}//二叉树找值为x的结点
BTNode* BinaryFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode* leftFind = BinaryFind(root->left, x);if (leftFind){return leftFind;}BTNode* rightFind = BinaryFind(root->right, x);if (rightFind){return rightFind;}return NULL;
}//二叉树的销毁
void BinaryTreeDestroy(BTNode** root)
{if (*root == NULL){return;}BinaryTreeDestroy(&((*root)->left));BinaryTreeDestroy(&((*root)->right));free(*root);*root = NULL;
}//层序遍历
void LevelBinaryTree(BTNode* root)
{//先创建一个队列Queue q;QueueInit(&q);//取根节点入队列QueuePush(&q, root);while (!QueueEmpty(&q)){//打印队头数据BTNode* Front = QueueFront(&q);printf("%d ", Front->data);QueuePop(&Front);if (Front->left){QueuePush(&q, Front->left);}if (Front->right){QueuePush(&q, Front->right);}}QueueDestroy(&q);
}//判断是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);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);if (front != NULL){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}

 test.c

#include"Tree.h"BTNode* CreateTree()
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);node1->left = node2;node1->right = node3;node2->left = node4;return node1;}int main()
{BTNode* node = CreateTree();/*PreOrder(node);printf("\n");InOrder(node);printf("\n");PosOrder(node);*/printf("NodeSize:%d\n", BinaryTreeSize(node));printf("NodeSize:%d\n", BinaryTreeSize(node));printf("NodeSize:%d\n", BinaryTreeSize(node));printf("LeafSize：%d\n", BinaryTreeLeafSize(node));printf("%d\n", BinaryTreeLevelKSize(node, 3));printf("%d\n", BinaryTreeDepth(node));BTNode* find = BinaryFind(node, 22);printf("%s\n", find == NULL ? "没找到\n" : "找到了！\n");LevelBinaryTree(node);bool ret = BinaryTreeComplete(node);printf("%s\n", ret == false ? "不是完全二叉树\n" : "是完全二叉树\n");BinaryTreeDestroy(&node);return 0;
}

我感觉这节递归还是挺难理解的，感觉函数递归进行的过程不好想象，层层递归就比较难以理解透彻，我会忘记自己递归到那个地方了绕不回去了就很烧脑筋，难想的时候呢我就得画出函数进行栈帧的创建与销毁，这样一步一步来还是比较好的。对了，我画的红箭头还有绿箭头可以看成是函数栈帧的创建与销毁。把详细的函数的栈帧的创建与销毁多想几遍函数的递归应该就会好想象一点了。这节课我啃了两天了，后续还得多回顾理解多敲代码，告诉自己，别畏难，很难，但也得一步一步走下去，总不能放弃吧，那就坚定不移的前进！（这节课的博客真难写呀啊啊啊——）

知识点有不对的地方还请多多指教（抱拳）

完——

终——Relaxing Time！

好好休息一下，继续战斗！昨天又发现了一首好听的歌(＾－＾)V）分享给你

           ————————————《Falling U》————————————

Falling U_T-ara_高音质在线试听_Falling U歌词|歌曲下载_酷狗音乐

至此结束——

我是云边有个稻草人

期待与你的下一次相遇！


http://www.ppmy.cn/ops/161126.html

相关文章

单链表相关操作(基于C语言)

单链表相关操作(基于C语言)

文章目录 单链表定义版本一(可自己选择是否含头节点)创建单链表打印单链表对单链表进行冒泡排序删除单链表中值为key的节点求单链表表长在单链表位序为i的位置插入新元素e 单链表定义 typedef struct node {int data;struct node* next; }LinkNode,*LinkList;版本一(可自己选择…
阅读更多...
网关和过滤器学习

网关和过滤器学习

一、网关是什么&#xff1f;有什么用&#xff1f; 在微服务架构中&#xff0c;一个模块可能会部署到多个不同地址的服务器上&#xff0c;比如一个item模块&#xff0c;它的端口号可能有8081、8082等。如果是以前&#xff0c;当用户发送请求时只能指定发送给某一个地址&#xff…
阅读更多...
【VUE框架】深入剖析 Vue2 与 Vue3 的 Diff 算法区别

【VUE框架】深入剖析 Vue2 与 Vue3 的 Diff 算法区别

引言 在前端开发中&#xff0c;Vue 作为一款流行的 JavaScript 框架&#xff0c;以其高效的数据驱动和响应式特性受到广泛青睐。Diff 算法是 Vue 实现高效更新 DOM 的核心机制之一&#xff0c;它通过比较新旧虚拟 DOM&#xff08;Virtual DOM&#xff09;树的差异&#xff0c;…
阅读更多...
mysql之InnoDB 统计信息收集

mysql之InnoDB 统计信息收集

文章目录 InnoDB 统计信息收集核心概念&#xff1a;统计信息的价值表级别统计信息索引级别统计信息列统计(MySQL 8.0) 统计信息的存储位置统计信息的收集方式自动统计信息收集的触发条件自动统计信息收集的具体机制手动统计信息收集&#xff1a; ANALYZE TABLE 命令 统计信息的…
阅读更多...
【Python爬虫(46)】解锁分布式爬虫：实时数据处理的奥秘

【Python爬虫(46)】解锁分布式爬虫：实时数据处理的奥秘

【Python爬虫】专栏简介&#xff1a;本专栏是 Python 爬虫领域的集大成之作&#xff0c;共 100 章节。从 Python 基础语法、爬虫入门知识讲起&#xff0c;深入探讨反爬虫、多线程、分布式等进阶技术。以大量实例为支撑&#xff0c;覆盖网页、图片、音频等各类数据爬取&#xff…
阅读更多...
uniapp修改picker-view样式

uniapp修改picker-view样式

解决问题&#xff1a; 1.选中文案样式&#xff0c;比如字体颜色 2.修改分割线颜色 3.多列时&#xff0c;修改两边间距让其平分 展示效果&#xff1a; 代码如下 <template><u-popup :show"showPicker" :safeAreaInsetBottom"false" close&quo…
阅读更多...
Linux远程kill进程及$处理

Linux远程kill进程及$处理

个人博客地址&#xff1a;Linux远程kill进程及$处理 | 一张假钞的真实世界 在远程执行的命令中如果包含特殊字符&#xff08;$&#xff09;时需要转义&#xff0c;如下&#xff1a; ssh rootremote_host "ps -ef|grep process_name | grep -v grep | awk {print $2}&qu…
阅读更多...
【后端基础】布隆过滤器原理

【后端基础】布隆过滤器原理

文章目录 一、Bloom Filter&#xff08;布隆过滤器&#xff09;概述1. Bloom Filter 的特点2. Bloom Filter 的工作原理 二、示例1. 添加与查询2. 假阳性 三、Bloom Filter 的操作1、假阳性概率2、空间效率3、哈希函数的选择 四、应用 Bloom Filter 是一种非常高效的概率型数据…
阅读更多...
最新文章

Copyright @ 2022~2023