二叉树的链式结构 - C语言（含有大量递归）

news/2025/3/29 19:41:29/

目录：

🍔前言

🍔二叉树链式结构的实现

🍟基本构架

😍代码：

🍔二叉树的遍历

🍟前序遍历

🍟中序遍历

🍟后序遍历

🍟层序遍历

🔴层序遍历的思路及代码

🍔 构建二叉树

 😍代码：

🍔二叉树销毁

😍代码：  

🍔二叉树节点个数

😍代码：

🍔二叉树叶子节点个数

😍代码：

🍔二叉树第k层节点个数

😍代码： 

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

😍代码：

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

😍代码：

😍二叉树的链式结构所有代码汇总😍

✅BinaryTree.c

✅Queue.c

🍔前言

        🥰我们学习完二叉树的“堆”以及堆的应用以后还有一个在平时面试题目中出现频率也非常高的结构等着我们呢，那就是—二叉树的链式结构（二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系）链式结构又分为二叉链和三叉链，当前我们使用的都是二叉链，后面的博客（红黑树等会用到三叉链）各位客官老爷，关注一下后续会更新呦！！！🥰🥰

🍔二叉树链式结构的实现

🍟基本构架

🥝在看二叉树基本操作前，再回顾下二叉树的概念

🔴二叉树是：

⭕ 空树
⭕ 非空：根节点，根节点的左子树、根节点的右子树组成的。

✅从概念中可以看出，二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的。

😍代码：

typedef int BTDataType;  //记录树内数据类型，方便后面修改
typedef struct BinaryTreeNode
{BTDataType data;  //记录节点struct BinaryTreeNode* left; //指针指向左子树struct BinaryTreeNode* right;//指针指向右子树
}BTNode;  //结构体的名字

      💧运用上面的这些代码，可以记录一颗二叉树的所有节点，所有推论也从这个地方出来了。后面也会有很多的结构跟这个有关。

🍔二叉树的遍历

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

🍟前序遍历

    🚩前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。（根——左子树——右子树）

 数据结构——二叉树先序、中序、后序及层次四种遍历（C语言版）_中序遍历_正弦定理的博客-CSDN博客

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

🍟中序遍历

         🚩中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。（左子树——根——右子树）

 二叉树三种遍历（动态图+代码深入理解）_二叉树的三种遍历例题带图_杨 戬的博客-CSDN博客

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

🍟后序遍历

       🚩 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。（左子树——右子树——根）

 二叉树三种遍历（动态图+代码深入理解）-阿里云开发者社区

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

 🍟层序遍历

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

🔴层序遍历的思路及代码

        ⭕层序遍历需要用到队列的一些知大家可以先去了解一下队列的特点队列的概念及结构（内有成型代码可供CV工程师参考）_硕硕C语言的博客-CSDN博客如下图：

      🚨需要注意的是进入队列的不是节点的值，而是节点的地址，这样做可以方便的把后面的左右子树的节点带出来，也方便了后面的判断。 

// 层序遍历
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);//队列的销毁
}

        🥰 这个思想后面的判断二叉树是否是完全二叉树也要用到

🍔 构建二叉树

    🚩构建二叉树的时候要先来引用一道牛客网的题目 二叉树遍历_牛客题霸_牛客网 (nowcoder.com)这个是它的链接可以试着去做一下

✅ 题目要求：

        编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

🥝 示例：

输入：abc##de#g##f###                   

输出：c b e g d f a

 🍟示例的实际图应该是下图这样的一颗树

🥰解题思路：  这个题目要我们构造一个链式二叉树，在先序遍历的过程中构建每一个节点。

 😍代码：

#include <stdio.h>
#include <malloc.h>typedef struct BTNode
{char _data;struct BTNode* _left;struct BTNode* _right;
}BTNode;//中序遍历
void Inorder(BTNode* root)
{if(root){Inorder(root->_left);printf("%c ", root->_data);Inorder(root->_right);}
}BTNode* CreatBTree(char* str, int* pi)
{if(str[*pi]!= '#'){//当前节点非空，则创建当前节点BTNode*root=(BTNode*)malloc(sizeof(BTNode));root->_data = str[*pi];//字符位置向后移动一个位置++(*pi);//创建左子树root->_left=CreatBTree(str,pi);//字符位置向后移动一个位置++(*pi);//创建右子树root->_right=CreatBTree(str,pi);return root;}elsereturn NULL;  //如果是空节点，则返回NULL
}int main()
{char str[101];int i = 0;//读入字符串scanf("%s", str);//创建二叉树BTNode* root = CreatBTree(str, &i);//中序打印二叉树Inorder(root);printf("\n");return 0;
}

🍔二叉树销毁

😍代码：  

// 二叉树销毁—递归实现
void BinaryTreeDestory(BTNode* root)
{if (root == NULL)  {return;}BinaryTreeDestory(root->right);  BinaryTreeDestory(root->left);free(root);
}

        ✅运用后序遍历（因为如果先释放根节点的话就不能直接找到左右子树了）来实现递归二叉树销毁，结束标志是遇见空节点返回上一级。

🍔二叉树节点个数

😍代码：

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

        ✅运用递归（前序）简化了问题，即：二叉树节点个数 = 左子树节点数 + 右子树节点数 + 1 

        ✅递归结束条件是遇到空节点返回 0。

🍔二叉树叶子节点个数

😍代码：

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

🍎叶子节点的概念：度为0的节点称为叶节点

        🍟运用递归（前序）简化了问题，即：二叉树叶子节点个数 = 左子树叶子节点个数 + 右子树叶子节点个数 

       🍟递归结束条件是遇到空节点返回 0， 该节点的左子树节点为空 并且 右子树节点为空，则该节点为叶子节点，返回1。

🍔二叉树第k层节点个数

😍代码： 

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{assert(k > 0); //k的值不能为负数if (k == 1 && root)  //第k层的判断条件{return 1;}return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

🍎层的概念：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；

        🍟不满足第k层的判断条件的不计数,（继续递归下去），当满足第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);BTNode* ret2 = BinaryTreeFind(root->right, x);if (ret1)return ret1;if (ret2)return ret2;return NULL;
}

        ✅运用递归（前序）简化了问题，即：二叉树中等于X的节点个数 = 左子树等于X的节点个数 + 右子树等于X的节点个数 

        ✅等于空，或者等于这个要找的值为这里的结束条件，返回的是值等于X的节点指针。这里用了两个临时变量来储存左右两边的个数，这样做可以在返回的时候直接返回，不用再一次的计算。🥰

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

     🍁完全二叉树的概念：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

        ✅运用前面层序遍历的思想用队列进行层序遍历，与它不一样的地方在于这次空值也要入队列，只要队列的队头为空指针就停止操作，看后面是否都为空，由于完全二叉树的自身特性决定了它的后面如果都为空则是完全二叉树，否则不是。

😍代码：

// 判断二叉树是否是完全二叉树
int 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);if (front){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}

😍二叉树的链式结构所有代码汇总😍

✅BinaryTree.c

typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;
BTNode* BuyNode(BTDataType x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail");return NULL;}node->data = x;node->left = NULL;node->right = NULL;return node;
}
//二叉树创建
BTNode* CreatBTree(char* str, int* pi)
{if(str[*pi]!= '#'){//当前节点非空，则创建当前节点BTNode*root=(BTNode*)malloc(sizeof(BTNode));root->_data = str[*pi];//字符位置向后移动一个位置++(*pi);//创建左子树root->_left=CreatBTree(str,pi);//字符位置向后移动一个位置++(*pi);//创建右子树root->_right=CreatBTree(str,pi);return root;}elsereturn NULL;  //如果是空节点，则返回NULL
}// 二叉树销毁
void BinaryTreeDestory(BTNode* root)
{if (root == NULL){return;}BinaryTreeDestory(root->right);BinaryTreeDestory(root->left);free(root);
}// 二叉树节点个数
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)
{assert(k > 0);if (k == 1 && root){return 1;}return 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);BTNode* ret2 = BinaryTreeFind(root->right, x);if (ret1)return ret1;if (ret2)return ret2;return NULL;
}// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}printf("%d ", root->data);BinaryTreePrevOrder(root->left);BinaryTreePrevOrder(root->right);
}// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root) 
{if (root == NULL){printf("N ");return;}BinaryTreeInOrder(root->left);printf("%d ", root->data);BinaryTreeInOrder(root->right);
}// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}BinaryTreePostOrder(root->left);BinaryTreePostOrder(root->right);printf("%d ", root->data);
}// 层序遍历
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);
}// 判断二叉树是否是完全二叉树
int 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);if (front){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}

 ✅Queue.c

void QueueInit(Queue* pq)
{assert(pq);pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail\n");return;}newnode->data = x;newnode->next = NULL;if (pq->ptail == NULL){assert(pq->phead == NULL);pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->phead->next == NULL){QNode* head = pq->phead;free(head);pq->phead = pq->ptail = NULL;pq->size = 0;}else{QNode* head = pq->phead;pq->phead = pq->phead->next;free(head);pq->size--;}
}
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return(pq->phead->data);
}
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->ptail->data;
}
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}


http://www.ppmy.cn/news/199689.html

相关文章

联想天逸无法进入bios

联想天逸无法进入bios

原因 台式机有集成显卡和独立显卡双显卡 解决办法 显示器必须连到主机横着的VGA接口&#xff08;下图红色2&#xff09;&#xff0c;不能是竖着的VGA接口。然后在开机的时候按F1键进入bios
阅读更多...
联想微型计算机开机黑屏什么原因,联想电脑开机后显示屏是黑屏怎么办

联想微型计算机开机黑屏什么原因,联想电脑开机后显示屏是黑屏怎么办

以联想天逸510s&#xff0c;win10为例&#xff1a;检查连接笔记本的电源接触是否良好&#xff0c;电源指示灯是否亮&#xff0c;建议使用万用表测试下笔记本电源是否有电源标签中标注数值的电压输出。 按开机键后电脑没有任何反应&#xff0c;也没有任何指示灯亮&#xff0c;这…
阅读更多...
联想天逸510pro开机故障，迁移主机硬盘

联想天逸510pro开机故障，迁移主机硬盘

环景&#xff1a; 电脑&#xff1a;联想天逸510pro-181kl 台式电脑 操作系统&#xff1a;Windows 10 专业版 64位 问题描述&#xff1a; 电脑正常关机然后就开不了机&#xff0c; 拔电源线插上开机才行 解决方案&#xff1a; 1.临时办法 拆掉硬盘直接安装在备用主机上面 …
阅读更多...
Windows 10 开机不一会出现MEMORY_MANAGEMENT蓝屏

Windows 10 开机不一会出现MEMORY_MANAGEMENT蓝屏

环境&#xff1a; 电脑&#xff1a;联想计算机-天逸510S-08IKL 系统&#xff1a;Windows 10 专业版 64位 内存&#xff1a;16G (sk 8G8G/2400MHz2667MHz DDR4) 问题描述&#xff1a; 系统开机不一会出现MEMORY_MANAGEMENT蓝屏&#xff0c;近期发生2次 解决方案&#xff1a…
阅读更多...
联想lenovo天逸510s mini台式机(10代)安装Win7系统

联想lenovo天逸510s mini台式机(10代)安装Win7系统

一小伙伴&#xff0c;在强东购买了 联想(Lenovo)天逸510S Mini台式机 酷睿版英特尔酷睿i5 1升电脑主机 (i5-10400 16G 512G SSD wifi6)单主机 打算搞个win7安装看看。 这玩意造型小巧&#xff0c; 别看小&#xff0c;配置&#xff1a;Intel 10代intel处理器&#xff0c;&…
阅读更多...
联想天逸510pro开机后滴滴两短声不能正常开机

联想天逸510pro开机后滴滴两短声不能正常开机

联想天逸510pro开机后滴滴两短声不能正常开机 咨询客服后了解到是CPU风扇报错导致&#xff0c;一般恢复BIOS设置就能解决&#xff0c;具体恢复方式如下 1.开机界面如下 2.F1进入设置界面 可以通过查看系统概述中的信息来判断是哪个位置出现问题&#xff1b; 3.F9进入载入最优…
阅读更多...
计算机管理关机在哪,电脑定时开关机在哪里设置

计算机管理关机在哪,电脑定时开关机在哪里设置

品牌型号&#xff1a;联想天逸510S 2020 系统&#xff1a;win10 1909 64位企业版 部分用户可能电脑型号不一样&#xff0c;但系统版本一致都适合该方法。 电脑定时开关机在哪里设置呢?给大家分享一下电脑怎么设置定时开关机。 可以在任务计划程序中设置 一、设置自动开机 1、鼠…
阅读更多...
台式电脑重装系统失败怎么办

台式电脑重装系统失败怎么办

当大家使用一键重装系统软件给自己电脑重装系统的时候,都可能会遇到一些故障问题造成台式电脑重装系统失败的情况发生.那么大家遇到台式电脑重装系统失败怎么办呢?现在小编就教下大家相关的方法教程&#xff0c;大家一起来看看吧。 工具/原料&#xff1a; 系统版本&#xff…
阅读更多...
最新文章

Copyright @ 2022~2023