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

news/2024/7/7 7:29:25

目录：

🍔前言

🍔二叉树链式结构的实现

🍟基本构架

😍代码：

🍔二叉树的遍历

🍟前序遍历

🍟中序遍历

🍟后序遍历

🍟层序遍历

🔴层序遍历的思路及代码

🍔 构建二叉树

 😍代码：

🍔二叉树销毁

😍代码：  

🍔二叉树节点个数

😍代码：

🍔二叉树叶子节点个数

😍代码：

🍔二叉树第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;
    }
    else
        return 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;
    }
    else
        return 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.niftyadmin.cn/n/393681.html

相关文章

SpringBoot+MyBatis 搭建项目基本框架

SpringBoot+MyBatis 搭建项目基本框架

参考资料:mall整合SpringBootMyBatis搭建基本骨架 一 背景 做的项目多了&#xff0c;就会发现&#xff0c;每次新项目起步&#xff0c;都是一样的。应该整理一个通用的模板来进行快速启动新项目。 二 使用到的框架简介 1.SpringBoot SpringBoot可以让你快速构建基于Spring…
阅读更多...
信息论与编码 SCUEC DDDD 期末复习

信息论与编码 SCUEC DDDD 期末复习

1.证明熵的可加性 2.假设一帧视频图像可以认为是由3*10的五次方个像素组成&#xff08;每像素均独立变化&#xff09;&#xff0c;如果每个像素可取128个不同的等概率亮度表示。请计算出每帧图像含多少信息量&#xff1f;若有一口述者在约12000个汉字的字汇中选400个字来口述此…
阅读更多...
C++——多态与虚表

C++——多态与虚表

目录 1.多态的实现 2.虚表 2.1虚函数重写是怎么实现的 2.2多态的原理 2.3静态绑定与动态绑定 3.单继承体系中的虚函数表 ​编辑4.多继承体系中的虚函数表 5.菱形继承的虚函数表 6.菱形虚拟继承的虚函数表 1.多态的实现 在C中&#xff0c;要想实现多态&#xff0c;必…
阅读更多...
mysql数据类型有哪几种

mysql数据类型有哪几种

Mysql支持的多种数据类型主要有&#xff1a;数值数据类型、日期/时间类型、字符串类型。 整数 浮点数&定点数 注&#xff1a;定点数以字符串形式存储&#xff0c;对精度要求高时使用decimal较好&#xff1b;尽量避免对浮点数进行减法和比较运算。 时间/日期类型 字符串类型…
阅读更多...
在编程中，代理、委托、回调、钩子、句柄、打桩的区别

在编程中，代理、委托、回调、钩子、句柄、打桩的区别

文章目录 代理委托委托与代理的区别 回调回调函数回调函数与普通函数的区别 钩子广义的钩子钩子与代理的区别钩子与委托的区别钩子与回调函数的区别 句柄句柄与钩子的区别 打桩打桩与代理的区别 代理 代理&#xff08;proxy&#xff09;&#xff1a;被代理类写好一套 API 的实现…
阅读更多...
chatgpt赋能python：Python取消合并单元格

chatgpt赋能python：Python取消合并单元格

Python取消合并单元格 在Excel中&#xff0c;合并单元格是一个非常常见的操作&#xff0c;它可以将多个单元格合并成一个单元格。这样可视化效果会更好&#xff0c;但是实际上会影响数据的计算和操作。如果你想取消这个操作&#xff0c;手工操作可能会非常费时间。不过&am…
阅读更多...
Linux账号管理与ACL权限设定（一）

Linux账号管理与ACL权限设定（一）

Linux的账号与群组 Linux系统中&#xff0c;关于账号和群组&#xff0c;实际记录的是UID和GID的数字&#xff1b; 关于账号有两个非常重要的文件&#xff1a;/etc/passwd 和 /etc/shadow &#xff1b; /etc/passwd 文件结构&#xff1a; 账号名称&#xff1a;密码&#xff…
阅读更多...
Git版本控制工具详解

Git版本控制工具详解

1 邂逅版本控制工具 2 集中式和分布式区别 3 Git的环境安装搭建 4 Git初始化本地仓库 6 Git远程仓库和验证 目录 content 5 Git记录更新变化过程 7 Git的标签tag用法 8 Git分支的使用过程 9 工作中的Git Flow 10 Git远程分支的管理 11 Git rebase的使用 12 Git常见命…
阅读更多...
最新文章

Copyright @ 2022~2023