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

news/2024/4/19 0:07:38

目录:

🍔前言

🍔二叉树链式结构的实现

🍟基本构架

😍代码:

🍔二叉树的遍历

🍟前序遍历

🍟中序遍历

🍟后序遍历

🍟层序遍历

🔴层序遍历的思路及代码

🍔 构建二叉树

 😍代码:

🍔二叉树销毁

😍代码:  

🍔二叉树节点个数

😍代码:

🍔二叉树叶子节点个数

😍代码:

🍔二叉树第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;
}


https://dhexx.cn/news/show-4628078.html

相关文章

python学习-进阶基本知识点总结

&#xff08;一&#xff09;正则表达式 1、正则表达式 字符类 [abc]&#xff1a;匹配 “a”、“b” 或 “c” 中的任意一个字符。abc&#xff1a;除了 “a”、“b” 和 “c” 以外的任何字符。[a-z]&#xff1a;匹配任何小写字母。[A-Z]&#xff1a;匹配任何大写字母。[0-9]&…

大数据Doris(三十四):Doris配置Spark与Yarn

文章目录 Doris配置Spark与Yarn 一、Doris配置Spark 1、配置 SPARK_HOME 环境变量 2、配置SPARK 依赖包

“吴军讲ChatGPT“课程的个人总结

人工智能时代, ChatGPT如此火热, 大家恐慌, 焦虑, 大家最关注的是两个问题 我会不会被取代?我有没有机会? 吴军老师(浪潮之巅, 数学之美等), 有门课程, <吴军讲ChatGPT>, 用通俗易懂的语言, 讲解了人工智能的技术原理前世今生,以及当下火热的ChatGPT的可以做什么, 那…

Java数据驱动:CData JDBC Drivers 2022 Crack

JDBC 驱动程序 易于使用的 JDBC 驱动程序&#xff0c;具有强大的企业级功能 无与伦比的性能和可扩展性。 对实时数据的简单 JDBC/SQL 访问。 从流行的 BI 工具访问实时数据。 集成到流行的 IDE 中。 CData JDBC Drivers Software 是领先的数据访问和连接解决方​​案提供商。我…

计算机网络第一章——计算机系统结构(下)

提示&#xff1a;总角之宴&#xff0c;言笑晏晏。信誓旦旦&#xff0c;不思其反。反是不思&#xff0c;亦已焉哉。 文章目录 1.2.1 分层结构&#xff0c;协议&#xff0c;接口和服务为什么要有分层&#xff1f;怎么分层正式认识分层结构概念总结 1.2.2 OSI 参考模型ISO参考模型…

解决record on line 2: wrong number of fields

背景 基于"encoding/csv"库解析。 共解析多个文档&#xff0c;只有这一个解析有问题&#xff0c;所用代码一致&#xff0c;进行比较后 发现该文档和其它文档不同&#xff0c;其它文档是第一行就是列名&#xff0c;下面都是数据&#xff1b; 而这个文档前两行有数据且…

C#,码海拾贝(33)——约化“一般实矩阵”为“赫申伯格矩阵”的“初等相似变换法”之C#源代码,《C#数值计算算法编程》源代码升级改进版

using System; namespace Zhou.CSharp.Algorithm { /// <summary> /// 矩阵类 /// 作者&#xff1a;周长发 /// 改进&#xff1a;深度混淆 /// https://blog.csdn.net/beijinghorn /// </summary> public partial class Matrix {…

【owt】WebrtcNode, subscribe流程

subscribe流程 1. AmqpClient - New message received 2023-04-26T21:54:18.415 - DEBUG: AmqpClient - RpcServer New message received {method: subscribe,args: [b149e44bb10d4e91bd162a8c6806ae7b,webrtc,{transportId: b149e44bb10d4e91bd162a8c6806ae7b,tracks: [Arr…

前端045_单点登录SSO_实现流程

单点登录SSO_实现流程 1、背景2、基于同域下 Cookie 实现 SSO1、背景 在企业发展初期,企业使用的系统很少,通常一个或者两个,每个系统都有自己的登录模块,运营人员每天用自己的账号登录,很方便。 但随着企业的发展,用到的系统随之增多,运营人员在操作不同的系统时,需要…

【ARMv8 SIMD和浮点指令编程】NEON 减法指令——减法也好几种

向量减法包括常见的普通加指令&#xff0c;还包括长减、宽减、半减、饱和减、按对减、按对加并累加、选择高半部分结果加、全部元素加等。 1 SUB 减法&#xff08;向量&#xff09;&#xff0c;该指令从第一个源 SIMD&FP 寄存器中的相应向量元素中减去第二个源 SIMD&…