Cpp五条

这个屌丝很懒，什么也没留下！

热门标签

【数据结构初阶】八、非线性表里的二叉树（二叉树的实现 -- C语言链式结构）

作者：Cpp五条 | 2024-02-21 08:15:56

踩

=========================================================================

相关代码gitee自取：

C语言学习日记: 加油努力 (gitee.com)

=========================================================================

接上期：

【数据结构初阶】七、非线性表里的二叉树（堆的实现 -- C语言顺序结构）-CSDN博客

=========================================================================

回顾

二叉树的概念及结构：

二叉树的概念

一棵二叉树是节点的一个有限集合，该集合满足以下条件：

或者为空
或者由一个根节点加上两棵别称为左子树和右子树的二叉树组成



二叉树的结构

二叉树不存在度大于2的节点
（所以节点的度可能是 0 即空树，也可能是 1 或 2 ）

二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

这次使用C语言链式结构实现二叉树，
要会把二叉树分为根、左子树 和 右子树 ，
把左子树（右子树）看成一个新的二叉树，再把其分为根、左子树 和 右子树 ，
依次分类下去……

图示：



注意

对于任意二叉树，都是由以下几种情况复合而成：





二叉树的存储结构（补充）

二叉树一般可以使用两种结构存储，
一种顺序结构，一种链式结构



链式结构

二叉树的链式存储结构，是指用链表来表示一棵二叉树，
即用链来表示元素的逻辑关系

通常的方法是：链表中每个节点由三个域组成，数据域和左右指针域，
左右指针分别用来给出该节点左孩子和右孩子所在的链节点的存储地址

链式结构又分为二叉链和三叉链，
初阶数据结构一般都是二叉链，高阶数据结构如红黑树等会用到三叉链

图示：

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

二叉树的遍历

递归结构遍历

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

引入一个概念 -- 深度优先遍历（DFS）
简单理解就是从某个位置开始遍历，往“深处”遍历到无路可退再往回遍历，
严格来说，在深度优先遍历时是先访问再往“深处”走，一般配合递归使用
（这里前序递归遍历是最符合深度优先遍历的）

有三种递归遍历方式：前序（先序）/ 中序 /  后序
如果按照递归的逻辑来说，这三种递归遍历方式都算是一种深度优先遍历，
它们都是往“深处”遍历，只是各自访问节点值的时机不一样



前序(先序) / 中序 / 后序的递归结构遍历

前序(先序)遍历(Preorder Traversal)——访问根节点的操作发生在遍历其左右子树之前
[即先访问根节点，再访问左子树，最后访问右子树]

中序遍历(Inorder Traversal)——访问根节点的操作发生在遍历其左右子树之中（间）
[即先访问左子树，再访问根节点，最后访问右子树]

后序遍历(Postorder Traversal)——访问根节点的操作发生在遍历其左右子树之后
[即先访问左子树，再访问右子树，最后访问根节点]

因为我们要不断的把二叉树分为根、左子树 和 右子树 ，
所以被访问的节点必是某子树的根，
于是有：
N（Node）-- 根节点
L（Left subtree）-- 根的左子树
R（Right subtree）-- 根的右子树
再安照上面的前序(先序) / 中序 / 后序的递归结构遍历，又有：
NLR -- 先根(序)遍历； LNR -- 中跟(序)遍历； LRN -- 后根(序)遍历

前序(先序)遍历图示：

中序遍历图示：

后序遍历图示：



层序遍历

除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历

设二叉树的根节点所在层数为第 1 层，层序遍历就是从所在二叉树的根节点出发，
首先访问第一层的树根节点，
然后访问左到右访问第 2 层上的节点，接着是第三层的节点
以此类推，自上而下，自左至右逐层访问树的节点的过程就是层序遍历

再引入一个概念 -- 广度优先遍历（BFS）
简单理解就是从当前“层”开始，一层一层进行遍历，和这里的层序遍历相似，
因为队列有“先进先出”的特点，所以进行广度优先遍历时常由队列进行配合

层序遍历图示：

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

链式二叉树的实现

（详细解释在图片的注释中，代码分文件放下一标题处）

实现具体功能前的准备工作

在链式二叉树头文件中包含之后所需头文件

定义链式二叉树节点将要存储的值的类型

创建链式二叉树节点类型（结构体）-- BTNode（重命名后）

因为之后要借助队列实现层序遍历，
所以要将之前写的队列头文件和队列函数实现文件复制一份放入指定文件夹，

在链式二叉树头文件BTNode类型下方包含复制的队列头文件，
（这样复制的队列头文件展开后才能找到BTNode类型并使用它）
在复制的队列头文件中也包含链式二叉树头文件

利用队列对链式二叉树进行层序遍历时，要将链式二叉树节点指针存放在队列中，
所以要将队列中数据域存储的数据类型改为链式二叉树节点指针类型 -- BTNode*

图示：





---------------------------------------------------------------------------------------------



BuyNode函数 -- 创建链式二叉树节点并对其初始化

开辟动态空间并检查空间是否开辟成功

将要放入节点的值x放入节点，
将节点的左右指针初始化为NULL

返回开辟的节点地址

图示：





---------------------------------------------------------------------------------------------



PrevOrder函数 -- 前序（先序）遍历函数

递归遍历到空指针NULL的话，打印当前为空节点，再返回到上层递归

进行前序遍历：
先访问根节点，再访问左子树，最后访问右子树

图示：

（配合这个图如果还是不能理解的话，可以看下TreeSize函数后面的递归步骤图了解递归）





---------------------------------------------------------------------------------------------



InOrder函数 -- 中序遍历函数

递归遍历到空指针NULL的话，打印当前为空节点，再返回到上层递归

进行中序遍历：
先访问左子树，再访问根节点，最后访问右子树

图示：





---------------------------------------------------------------------------------------------



PostOrder函数 -- 后序遍历函数

递归遍历到空指针NULL的话，打印当前为空节点，再返回到上层递归

进行后序遍历：
先访问左子树，再访问右子树，最后访问根节点

图示：





---------------------------------------------------------------------------------------------



TreeSize函数 -- 计算链式二叉树中的节点个数

使用三目操作符，如果根节点为空返回0（个节点），
如果不为空则返回 TreeSize(root->left) + TreeSize(root->right) + 1
即左子树节点的个数 + 右子树节点的个数 + 1（根节点） -- 后序遍历

图示：

该函数递归步骤图：





---------------------------------------------------------------------------------------------



TreeLeafSize函数 -- 计算链式二叉树中的叶子节点个数

先判断当前节点是不是空节点（是不是空树），是的话返回0（个叶子节点）

如果(递归后)当前节点的左子树(左孩子) 和右子树(右孩子) 都为空，
说明当前节点为叶子节点，返回1（个叶子节点）

如果(递归后)当前节点为分支节点（非空树非叶子）,
使用递归返回其左子树和右子树的叶子节点个数

图示：

该函数递归步骤图：





---------------------------------------------------------------------------------------------



TreeKLevel函数 -- 计算链式二叉树中第k层的节点个数

链式二叉树层数默认从第1层开始（根节点所在层数）
assert断言接收的要求链式二叉树的层数应大于0

（递归时）遇到空节点就返回上一层递归，返回0（个节点）

到达目标层数后如果节点不为空，返回1（个当层节点）

运用“相对层数”：
当前树的第k层 = 左子树的第k-1层 + 右子树的第k-1层
进行递归遍历并统计第k层的节点个数

图示：

该函数递归步骤图：





---------------------------------------------------------------------------------------------



TreeDestory函数 -- 对链式二叉树类型进行销毁

递归遍历销毁链式二叉树时，
如果遇到空树或递归到叶子节点的“左右NULL节点”，
则返回结束函数或返回上层递归

使用后序递归遍历销毁链式二叉树，
先遍历销毁当前左子树，再遍历销毁当前右子树，最后销毁当前节点
（置空操作放在调用该函数后手动进行）

图示：

该函数递归步骤图：





---------------------------------------------------------------------------------------------



TreeFind函数 -- 在链式二叉树中查找值为x的节点

递归遍历对链式二叉树中节点进行查找时，
如果遇到空树或递归到叶子节点的“左右NULL节点”，
则返回结束函数或返回上层递归

如果递归遍历过程中找到对应节点了，就返回该节点

为了防止找到对应节点后递归还未结束继续查找，
要创建一个链式二叉树节点类型指针变量（ret），存放递归时的返回值

先使用递归遍历当前左子树进行查找，左子树查找完后检查ret情况看是否已经找到
未找到的话再对当前右子树进行相同操作，如果都未找到则返回空NULL

图示：

该函数递归步骤图：





---------------------------------------------------------------------------------------------



LevelOrder函数 -- 对链式二叉树进行层序遍历

先创建一个队列类型，并对其进行初始化，
再将链式二叉树结点指针放入队列中

使用while循环进行层序遍历

（在while循环中：）
先创建一个节点类型指针变量front存放队列中的当前节点地址，
再通过变量front打印当前节点值

（在while循环中：）
然后再分别将当前节点的左右孩子录入队列中，
最后执行出队操作，出队已打印的当前节点值，
这样一遍循环下来就遍历了一个节点并从左往右存储其两个子节点

层序遍历完成后进行换行并销毁队列

图示：





---------------------------------------------------------------------------------------------



TreeComplete函数 -- 判断该链式二叉树是不是完全二叉树

先创建一个队列类型，并对其进行初始化，
再将链式二叉树结点指针放入队列中

使用while循环进行层序遍历：
先创建一个节点类型指针变量front存放队列中的当前节点地址，
再判断当前节点是不是空节点，是就终止循环，
然后再分别将当前节点的左右孩子录入队列中，
最后执行出队操作，出队已判断的当前节点值

再使用一个while循环继续进行遍历：
先创建一个节点类型指针变量front存放队列中的当前节点地址，
再对上个while循环中找到的空节点进行出队，
这时如果队列之后如果还有非空节点，
说明该链式二叉树不是连续的，不是完全二叉树，返回false

如果第二个while循环能够顺利循环结束，
说明该链式二叉树的非空节点是连续的，是完全二叉树，返回true

图示：





---------------------------------------------------------------------------------------------



TreeHeight函数 -- 计算当前链式二叉树的高度

先判断当前节点是不是空节点，是的话返回0（层）

使用递归分别计算左右子树的高度并记录，再返回树的高度

再使用三目操作符判断出较高树并返回树的高度
（树的高度 = 左右子树中较高树的高度 + 1）

图示：





---------------------------------------------------------------------------------------------



总体测试：

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

对应代码

BinaryTree.h


#pragma once
 
//包含之后所需的头文件：
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
 
 
//二叉树的增删查改操作并不重要，应该重点了解二叉树的结构
// 为后面了解高阶数据结构做铺垫
//（之后高阶数据结构的搜索二叉树、AVL和红黑树才是专业的）
 
//指定二叉树节点存储数据的类型：
typedef int BTDataType;
 
//创建二叉树节点类型：
typedef struct BinaryTreeNode
{
	//左指针：指向该节点的左孩子
	struct BinaryTreeNode* left;
 
	//该节点存储的值：
	BTDataType val;
 
	//右指针：指向该节点的右孩子
	struct BinaryTreeNode* right;
 
}BTNode; //从命名为BTNode
 
//包含之前写的队列头文件
//（层序遍历需要用到队列）
#include "Queue_BT.h"
//（要包含在二叉树节点类型BTNode下方）
//（这样队列头文件展开后才能
//找到要存储的链式二叉树节点类型）
 
 
//创建节点函数 -- 创建链式二叉树节点并对其初始化
//接收要放入节点中的值（x）
BTNode* BuyNode(int x);
 
 
//递归结构遍历 -- 前序（先序）遍历函数
//先访问根节点 - 再访问左子树 - 最后访问右子树
//接收二叉树根节点地址（root）
void PrevOrder(BTNode* root);
 
 
//递归结构遍历 -- 中序遍历函数
//先访问左子树 - 再访问根节点 - 最后访问右子树
//接收二叉树根节点地址（root）
void InOrder(BTNode* root);
 
 
//递归结构遍历 -- 后序遍历函数
//先访问左子树 - 再访问右子树 - 最后访问根节点
//接收二叉树根节点地址（root）
void PostOrder(BTNode* root);
 
 
//节点数函数 -- 计算二叉树中的节点个数
//接收二叉树根节点地址（root）
int TreeSize(BTNode* root);
 
 
//叶子节点数函数 -- 计算二叉树中的叶子节点个数
//接收二叉树根节点地址（root）
int TreeLeafSize(BTNode* root);
 
 
//第k层节点数函数 -- 计算二叉树中第k层的节点个数
//接收二叉树根节点地址（root）和层数（k）
int TreeKLevel(BTNode* root, int k);
 
 
//二叉树销毁函数 -- 对二叉树类型进行销毁
//接收二叉树根节点地址（root）
void TreeDestory(BTNode* root);
 
 
//查找指定节点值函数 -- 在二叉树中查找值为x的节点
//接收二叉树根节点地址（root）和 要查找的节点值（x）
BTNode* TreeFind(BTNode* root, BTDataType x);
 
 
//层序遍历函数 -- 对二叉树进行层序遍历
//接收二叉树根节点地址（root）
void LevelOrder(BTNode* root);
 
 
//判断完全二叉树函数 -- 
//判断该树是不是完全二叉树
//接收二叉树根节点地址（root）
int TreeComplete(BTNode* root);
 
 
//计算高度函数 -- 计算当前链式二叉树的高度
//接收二叉树根节点地址（root）
int TreeHeight(BTNode* root);

---------------------------------------------------------------------------------------------

Queue_BT.h


#pragma once
 
//包含之后需要的头文件：
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
 
	//包含链式二叉树头文件：
#include "BinaryTree.h"
 
 
//以链表（链式结构）实现队列：
//双向+循环 的链表可以解决找尾结点的问题，
//定义一个尾指针也可以解决该问题，
//哨兵位 可以解决二级指针的问题，
//且尾插时可以少一层判断，但还有方法可以解决
 
 
//定义队列(链式结构)中数据域存储的数据类型：
typedef BTNode* QDataType;
//因为要将队列应用到存储链式二叉树节点指针上
//（直接存储其节点太费空间，所以存储其节点指针）
//所以要把队列存储的数据类型改掉
//改为和二叉树节点指针一致 -- BTNode*
 
//定义队列(链式结构)结点类型：
typedef struct QueueNode
{
	//队列指针域：
	struct QueueNode* next;
 
	//队列数据域：
	QDataType data;
 
}QNode; //将类型重命名为Qnode
 
 
//定义队列类型：
typedef struct Queue
{
	//因为用链表尾插实现入队，
	//用链表头删实现出队，
	//那么就需要头结点和尾结点的指针，
	//所以可以直接将这两个指针封装为一个类型，
	//队列类型：
 
	//头结点指针：
	QNode* head;
 
	//尾结点指针：
	QNode* tail;
 
	//记录队列结点(元素)个数：
	int size; 
 
	//这样之后在出队和入队操作时，
	//就不需要用到二级指针，
	//直接接收这个结构体指针，
	//通过结构体指针运用结构体里的头尾结点指针，
	//再用头尾结点指针定义头尾结点
	//来实现 二级指针、带哨兵位头结点 和 返回值 的作用
	//所以现在已知的通过指针定义结点的方法就有4种：
	//		1. 结构体包含结点指针
	//		2. 二级指针调用结点指针
	//		3. 哨兵位头结点指针域next指向结点地址
	//		4. 返回值返回改变的结点指针
 
}Que; //重命名为Que
 
 
//队列初始化函数 -- 将队列进行初始化
//接收队列类型指针(包含链表头尾结点) 
void QueueInit(Que* pq);
 
//队列销毁函数 -- 将队列销毁
//接收队列类型指针(包含链表头尾结点) 
void QueueDestroy(Que* pq);
 
//队列入队函数 -- 用链表的尾插操作实现入队
//接收队列类型指针(包含链表头尾结点) 、尾插值
void QueuePush(Que* pq, QDataType x);
 
//队列出队函数 -- 用链表的头删操作实现出队
//接收队列类型指针(包含链表头尾结点) 
void QueuePop(Que* pq);
 
//队头函数 -- 返回队头结点的数据域数据
//接收队列类型指针(包含链表头尾结点) 
QDataType QueueFront(Que* pq);
 
//队尾函数 -- 返回队尾结点的数据域数据
//接收队列类型指针(包含链表头尾结点) 
QDataType QueueBack(Que* pq);
 
//判空函数 -- 判断队列是否为空
//接收队列类型指针(包含链表头尾结点) 
bool QueueEmpty(Que* pq);
 
//队列大小函数 -- 判断队列结点(元素)个数
//接收队列类型指针(包含链表头尾结点) 
int QueueSize(Que* pq);

---------------------------------------------------------------------------------------------

BinaryTree.c


#define _CRT_SECURE_NO_WARNINGS 1
 
//包含二叉树头文件：
#include "BinaryTree.h"
 
 
//创建节点函数 -- 创建链式二叉树节点并对其初始化
//接收要放入节点中的值（x）
BTNode* BuyNode(int x)
{
	//开辟动态空间：
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	//检查是否开辟成功：
	if (node == NULL)
	{
		//开辟失败则打印错误信息：
		perror("malloc fail");
		//终止程序：
		exit(-1);
	}
 
	//将要放入节点的值x放入节点：
	node->val = x;
	//将节点的左右指针初始化为NULL：
	node->left = NULL;
	node->right = NULL;
 
	//返回开辟的节点地址：
	return node;
}
 
 
 
//递归结构遍历 -- 前序（先序）遍历
//先访问根节点 - 再访问左子树 - 最后访问右子树
//接收二叉树根节点地址（root）
void PrevOrder(BTNode* root)
{
	//递归遍历到空指针NULL（或空树）：
	if (root == NULL)
	{
		//打印当前为空节点：
		printf("NULL  ");
 
		//返回结束当前递归：
		return;
	}
 
	//进行前序遍历：
	//先访问根节点 -- 打印当前节点的值：
	printf("%d  ", root->val);
 
	//再访问左子树 -- 使用递归打印左子树：
	PrevOrder(root->left);
 
	//最后访问右子树 -- 使用递归打印右子树：
	PrevOrder(root->right);
}
 
 
 
//递归结构遍历 -- 中序遍历
//先访问左子树 - 再访问根节点 - 最后访问右子树
//接收二叉树根节点地址（root）
void InOrder(BTNode* root)
{
	//递归遍历到空指针NULL：
	if (root == NULL)
	{
		//打印当前为空节点：
		printf("NULL  ");
 
		//返回结束当前递归：
		return;
	}
 
	//进行中序遍历：
	//先访问左子树 -- 使用递归打印左子树：
	InOrder(root->left);
 
	//再访问根节点 -- 打印当前节点的值：
	printf("%d  ", root->val);
 
	//最后访问右子树 -- 使用递归打印右子树：
	InOrder(root->right);
}
 
 
 
//递归结构遍历 -- 后序遍历
//先访问左子树 - 再访问右子树 - 最后访问根节点
//接收二叉树根节点地址（root）
void PostOrder(BTNode* root)
{
	//递归遍历到空指针NULL：
	if (root == NULL)
	{
		//打印当前为空节点：
		printf("NULL  ");
 
		//返回结束当前递归：
		return;
	}
 
	//进行后序遍历：
	//先访问左子树 -- 使用递归打印左子树：
	PostOrder(root->left);
 
	//再访问右子树 -- 使用递归打印右子树：
	PostOrder(root->right);
 
	//最后访问根节点 -- 打印当前节点的值：
	printf("%d  ", root->val);
}
 
 
 
//节点数函数 -- 计算二叉树中的节点个数
//接收二叉树根节点地址（root）
int TreeSize(BTNode* root)
{
	//第二种方法：“分治”思想
	return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
	//使用三目操作符，如果根节点为空返回0（个节点）
	//如果不为空则返回 TreeSize(root->left) + TreeSize(root->right) + 1
	//即 左子树节点的个数 + 右子树节点的个数 + 1（根节点） --  后序遍历
}
 
 
 
//第一种方法：递归遍历统计二叉树节点个数
/*
//节点数函数 -- 计算二叉树中的节点个数
//接收二叉树根节点地址（root）
int TreeSize(BTNode* root)
{
	//递归时每递归一次就会创建一次栈帧，
	//如果有初始化普通变量，每递归一次就会初始化一次，
	//所以要赋予普通变量常属性，使其成为静态成员变量，
	//局部的静态成员变量只会被初始化一次：
	static int size = 0;
	//但是这样该函数就只能调用一次，因为调用一次后，
	//该变量不会再初始化为0，直到程序结束才被销毁
	//那么可以把size定义为全局变量，
	//在主函数调用该函数前就要先将size初始化为0
	if (root == NULL)
		//如果根节点为空：
	{
		return 0; //返回0表0个节点
	}
	else
	{
		++size; //root不为空则个数++
	}
	//使用递归遍历计算（类似前序遍历）：
	TreeSize(root->left); //先遍历左子树
	TreeSize(root->right); //再遍历右子树
	//返回二叉树中节点个数：
	return size;
	
}
*/
 
 
 
 
//叶子节点数函数 -- 计算二叉树中的叶子节点个数
//接收二叉树根节点地址（root）
int TreeLeafSize(BTNode* root)
{
	if (root == NULL)
		//如果当前根节点为空：
		//（当前为空树）
	{
		//返回0 -- 无叶子节点：
		return 0;
	}
 
	if (root->left == NULL && root->right == NULL)
		//如果当前节点的左子树(左孩子)和右子树(右孩子)都为空：
	{
		//说明当前节点为叶子节点，左右指针都指向NULL：
		return 1; //返回1
	}
 
	//能执行到这说明当前节点为非空树非叶子节点 -- 分支节点
 
	//如果递归后当前节点为分支节点（非空树非叶子）,
	//使用递归返回其左子树和右子树的叶子节点个数：
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}
 
 
 
 
//第k层节点数函数 -- 计算二叉树中第k层的节点个数
//接收二叉树根节点地址（root）和层数（k）
int TreeKLevel(BTNode* root, int k)
{
	//层数默认从第1层开始（根节点所在层数）
	//assert断言二叉树的层数大于0:
	assert(k > 0);
 
	//（递归时）遍历过程遇到空节点：
	if (root == NULL)
	{
		//已经遇到空节点就返回上一层递归
		return 0;
	}
 
	//到达目标层数后如果节点不为空：
	if (k == 1)
	{
		//返回1个当层节点：
		return 1;
	}
 
	//需知：“相对层数”
	//我们说的第k层是以根节点（第1层）为准的
	// "第一层的第三层 等于 第二层的第二层 等于 第三层的第一层"
	// 爷爷找孙子，可以先找孙子的爸爸，再让爸爸找儿子（爷爷的孙子）
	//所以有：当前树的第k层 = 左子树的第k-1层 + 右子树的第k-1层 
	//					（递归的降级）
	
	//当前树的第k层 = 左子树的第k-1层 + 右子树的第k-1层 ：
	return TreeKLevel(root->left, k - 1)
		 + TreeKLevel(root->right, k - 1);
}
 
 
 
//二叉树销毁函数 -- 对二叉树类型进行销毁
//接收二叉树根节点地址（root）
void TreeDestory(BTNode* root)
{
	//分三部分进行销毁：
	//当前节点、左子树、右子树
	
	//使用后序销毁二叉树：
	//最后才销毁根节点，
	//防止先销毁根节点后找不到左右子树，
	//导致最后不能销毁左右1子树
 
	if (root == NULL)
		//如果遇到空树，
		//或者递归到叶子节点的“左右NULL节点”：
	{
		//直接返回：
		return;
	}
	
	//使用后序遍历：
	//先遍历销毁当前左子树：
	TreeDestory(root->left);
	//再遍历销毁当前右子树：
	TreeDestory(root->right);
	//最后销毁当前节点：
	free(root);
 
	//置空操作放在调用该函数后手动进行
}
 
 
 
//查找指定节点值函数 -- 在二叉树中查找值为x的节点
//接收二叉树根节点地址（root）和 要查找的节点值（x）
BTNode* TreeFind(BTNode* root, BTDataType x)
{
	//如果是空树（或“左右NULL子树”）：
	if (root == NULL)
	{
		//那就不用找了，直接返回空：
		return NULL;
	}
	
	//递归过程中找到对应节点了：
	if (root->val == x)
	{
		//返回该节点指针：
		return root;
	}
 
	//为了防止找到后往回递归又返回
	//覆盖掉了找到的节点指针，
	//所以要创建一个变量存储找到的节点指针
	//方便最终返回该指针：
	
	//创建二叉树节点类型指针变量：
	BTNode* ret = NULL;
 
	//进行递归并用变量ret存储：
	//（如果在左子树中找到）
	ret = TreeFind(root->left, x);
	//如果找到了就不用再递归遍历右子树了，
	//判断并返回在左子树中找到的对应节点地址：
	if (ret != NULL)
		//ret不为空说明已经在左子树中找到了对应节点：
	{
		//进行返回，不在进行下面的右子树遍历：
		return ret;
	}
	
	//执行到这里说明左子树中未找到相应节点，
	//需再遍历右子树进行查找：
	ret = TreeFind(root->right, x);
	//如果在右边找到了：
	if (ret != NULL)
		//此时ret不为空，
		//说明在右子树中找到了对应节点：
	{
		//返回找到的节点地址：
		return ret;
	}
 
	//如果能执行到这，说明二叉树中没有该节点：
	return NULL; //返回空
}
 
 
 
//层序遍历函数 -- 对二叉树进行层序遍历
//接收二叉树根节点地址（root）
void LevelOrder(BTNode* root)
{
	//使用 队列 存储二叉树：“上一层带下一层”
	//（从上到下、从左到右存储二叉树）
 
	//先创建一个队列类型：
	Que q;
		
	//对队列进行初始化：
	QueueInit(&q);
 
	//先将二叉树根节点root放入队列中：
	if (root != NULL)
		//二叉树根节点不为空才能放入队列：
	{
		//使用队列入队函数QueuePush将根节点（指针）录入：
		QueuePush(&q, root);
	}
	
	//之后再使用while循环，进行层序遍历：
	while (QueueEmpty(&q) != true)
		//只要当前队列不为空（队列中还有节点指针）就继续层序遍历：
	{
		//使用队列的队头函数QueueFront获取队头的节点指针：
		BTNode* front = QueueFront(&q);
 
		//打印当前队头节点值：
		printf("%d ", front->val);
		
		//先录入当前节点左孩子：
		//如果当前节点左孩子不为空，就将其左孩子录入队列：
		if (front->left != NULL)
		{
			//使用队列入队函数QueuePush将当前左孩子录入队列：
			QueuePush(&q, front->left);
		}
 
		//再录入当前节点右孩子：
		//如果当前节点右孩子不为空，就将其右孩子录入队列：
		if (front->right != NULL)
		{
			//使用队列入队函数QueuePush将当前右孩子录入队列：
			QueuePush(&q, front->right);
		}
 
		//打印当前节点值 且 录入新左后节点指针 后，
		//将当前节点出队(队列出队函数QueuePop)，
		//对下个队头二叉树节点指针进行相同操作：
		QueuePop(&q);
 
		//（完成“上一层带下一层”，从上到下、从左到右存储二叉树）
	}
 
	//层序遍历完成后换行：
	printf("\n");
 
	//使用队列对二叉树遍历完成后，销毁队列：
	QueueDestroy(&q);
}
 
 
 
//判断完全二叉树函数 -- 判断该树是不是完全二叉树
//接收二叉树根节点地址（root）
int TreeComplete(BTNode* root)
{
	/*
	思路：利用层序遍历的特征进行判断
	遍历时如果有空节点，将空节点也进行遍历，
	看最终空节点的分布情况就能判断是不是完全二叉树
	1、遍历时如果非空节点是连续的，就是完全二叉树
	2、遍历时如果非空节点不连续，遍历时中间右出现空节点，就是非完全二叉树
	*/
	//先创建一个队列类型：
	Que q;
	//对队列进行初始化：
	QueueInit(&q);
 
	//先将二叉树根节点root放入队列中：
	if (root != NULL)
		//二叉树根节点不为空才能放入队列：
	{
		//使用队列入队函数QueuePush将根节点（指针）录入：
		QueuePush(&q, root);
	}
 
	//之后再使用while循环，进行层序遍历：
	while (QueueEmpty(&q) != true)
		//只要当前队列不为空（队列中还有节点指针）就继续层序遍历：
	{
		//使用队列的队头函数QueueFront获取队头的节点指针：
		BTNode* front = QueueFront(&q);
 
		//循环遍历过程中如果遇到空节点就终止循环：
		if (front == NULL)
			//front为空节点：
		{
			break; //终止循环
		}
 
		//使用队列入队函数QueuePush将当前左孩子录入队列：
		QueuePush(&q, front->left);
		//使用队列入队函数QueuePush将当前右孩子录入队列：
		QueuePush(&q, front->right);
		//将当前队头的节点类型出队，判断下个节点：
		QueuePop(&q);
	}
 
	/*
	执行到这时，队列中队头节点即空节点（NULL）
	这时再看该空节点 后面的所有节点 还有没有非空节点，
	后面的所有节点还有 非空节点 的话 -- 说明该二叉树不是连续的，不是完全二叉树
	后面的所有节点没有 非空节点 的话 -- 说明该树非空节点都是连续的，是完全二叉树
	*/
 
	//同样使用while循环进行操作：
	while (QueueEmpty(&q) != true)
		//只要当前队列不为空（队列中还有节点指针）就继续循环判断：
	{
		//使用队列的队头函数QueueFront获取队头的节点指针：
		BTNode* front = QueueFront(&q);
 
		//使用出队函数QueuePop进行出队操作：
		//（第一次出队时将队头的空节点NULL出队）
		QueuePop(&q);
		/*
		出队后如果当前队头节点为非空节点的话，
		说明该二叉树不是连续的，不是完全二叉树，
		则销毁队列并返回false:
		*/
		if (front != NULL)
			//当前队头节点为非空节点：
		{
			//销毁队列：
			QueueDestroy(&q);
 
			//返回false：
			return false;
		}
	}
 
	/*
	执行到这，说明之后已经没有非空节点了
	说明该树非空节点都是连续的，是完全二叉树，
	则销毁队列并返回true:
	*/
	//销毁队列：
	QueueDestroy(&q);
	//返回true：
	return true;
	//（ true 以int类型返回 -- 1）
	//（ false 以int类型返回 -- 0）
}
 
 
 
//计算高度函数 -- 计算当前链式二叉树的高度
//接收二叉树根节点地址（root）
int TreeHeight(BTNode* root)
{
	//思路：树的高度 = 左右子树中较高树的高度 + 1(根节点)
 
	//如果该树是空树，返回 0（层）：
	if (root == NULL)
		//根节点为空：
	{
		//返回 0（层）：
		return 0;
	}
 
	//方法二：使用递归计算左右子树高度并记录，再返回树的高度
	//递归计算左子树高度：
	int leftHeight = TreeHeight(root->left);
	//递归计算右子树高度：
	int rightHeight = TreeHeight(root->right);
 
	//再使用三目操作符判断后返回树的高度：
	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	//树的高度 = 左右子树中较高树的高度 + 1(根节点)
 
 
	/*
	//方法一：使用三目操作符返回树的高度
	return TreeHeight(root->left) > TreeHeight(root->right)
		? TreeHeight(root->left) + 1 : TreeHeight(root->right) + 1;
	//三目操作符选出较高树，再 计算其高度 + 1 = 树的高度
	*/
	/*
	这样可以计算出该树的高度，但是其中含有大量的重复计算，
	判断较高树时已经递归求了左右子树的高度，
	在返回树的高度时又重新计算了一遍左右子树的高度，
	是极其不好的代码
	*/
}

---------------------------------------------------------------------------------------------

Queue_BT.c


#define _CRT_SECURE_NO_WARNINGS 1
 
//包含队列头文件：
#include "Queue_BT.h"
 
//队列初始化函数 -- 将队列进行初始化
//接收队列类型指针(包含链表头尾结点) 
void QueueInit(Que* pq)
{
	//assert断言队列类型指针不为空：
	assert(pq != NULL);
 
	//将队头结点置为空：
	pq->head = NULL;
 
	//将队尾结点置为空：
	pq->tail = NULL;
 
	//队列结点(元素)个数置为0：
	pq->size = 0;
}
 
 
 
//队列销毁函数 -- 将队列销毁
//接收队列类型指针(包含链表头尾结点) 
void QueueDestroy(Que* pq)
{
	//assert断言队列类型指针不为空：
	assert(pq != NULL);
 
	//释放队列跟单链表的释放一样
	//先创建一个在队列进行遍历的指针：
	QNode* cur = pq->head; //从队头结点开始
 
	//使用while循环进行遍历释放队列结点：
	while (cur != NULL)	
	{
		//先保存下个结点：
		QNode* next = cur->next;
 
		//再释放当前结点：
		free(cur);
 
		//再指向下个结点：
		cur = next;
	}
 
	//结点都释放后，把队头队尾指针都置空：
	pq->head = NULL;
	pq->tail = NULL;
 
	//再把队列结点(元素)个数置为0：
	pq->size = 0;
}
 
 
 
//队列入队函数 -- 用链表的尾插操作实现入队
//接收队列类型指针(包含链表头尾结点) 、尾插值
void QueuePush(Que* pq, QDataType x)
{
	//assert断言队列类型指针不为空：
	assert(pq != NULL);
 
	//入队放入元素需要空间，
	//所以要先为队列结点开辟动态空间：
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	//检查是否开辟成功：
	if (newnode == NULL)
	{
		//开辟失败则打印错误信息：
		perror("malloc fail");
		//终止程序：
		exit(-1);
	}
 
	//队列结点完成后将尾插值(x)
	//赋给队列结点数据域：
	newnode->data = x;
	//指针域指向空：
	newnode->next = NULL;
 
	//空间开辟后进行尾插：
	if (pq->tail == NULL)
		//如果队列刚初始化，队列为空，
		//头结点指针和尾结点指针都为空：
	{
		//那么将刚开辟的结点newnode地址
		//赋给头结点指针和尾结点指针
		pq->head = newnode;
		pq->tail = newnode;
	}
	else
		//队列不为空，进行尾插：
	{
		//将目前队尾结点指针域next指向尾插结点：
		pq->tail->next = newnode;
		//然后再指向尾插结点，成为新队尾结点：
		pq->tail = newnode;
	}
 
	//插入数据后队列结点(元素)个数++：
	pq->size++;
}
 
 
 
//队列出队函数 -- 用链表的头删操作实现出队
//接收队列类型指针(包含链表头尾结点) 
void QueuePop(Que* pq)
{
	//assert断言队列类型指针不为空：
	assert(pq != NULL);
	//assert断言队列不为空，没数据不能删除：  
	assert(QueueEmpty != true); //不为空就继续程序
 
	//如果队列中只剩一个结点：
	if (pq->head->next == NULL)
		//队头指针指向空，说明只剩一个结点，
		//只剩一个结点说明队头队尾指针都指向这一个结点，
		//所以这时头删后头指针移动，尾指针也要移动
	{
		//先释放("删除")队列目前头结点：
		free(pq->head);
 
		//删除后将队头队尾指针都置为空：
		pq->head = NULL;
		pq->tail = NULL;
	}
	else
		//队列不止一个结点，则头删后只需移动队头结点：
	{
		//用链表的头删操作实现出队,
		//先保存第二个结点地址：
		QNode* next = pq->head->next;
 
		//释放("删除")队列目前头结点：
		free(pq->head);
 
		//再将队头结点指针指向原本第二个结点next，
		//让其成为新的队头结点：
		pq->head = next;
	}
 
	//“删除”后队列结点(元素)个数--：
	pq->size--; 
}
 
 
 
//队头函数 -- 返回队头结点的数据域数据
//接收队列类型指针(包含链表头尾结点) 
QDataType QueueFront(Que* pq)
{
	//assert断言队列类型指针不为空：
	assert(pq != NULL);
	//assert断言队列不为空，没数据不能查找：  
	assert(QueueEmpty != true); //不为空就继续程序
 
	//队列有数据，则直接返回队头结点数据域数据：
	return pq->head->data;
}
 
 
 
//队尾函数 -- 返回队尾结点的数据域数据
//接收队列类型指针(包含链表头尾结点) 
QDataType QueueBack(Que* pq)
{
	//assert断言队列类型指针不为空：
	assert(pq != NULL);
	//assert断言队列不为空，没数据不能查找：  
	assert(QueueEmpty != true); //不为空就继续程序
 
	//队列有数据，则直接返回队尾结点数据域数据：
	return pq->tail->data;
}
 
 
 
//判空函数 -- 判断队列是否为空
//接收队列类型指针(包含链表头尾结点) 
bool QueueEmpty(Que* pq)
{
	//assert断言队列类型指针不为空：
	assert(pq != NULL);
 
	//直接判断队头结点指向的下个结点是否为空：
	return pq->head == NULL; 
	//是则返回true -- 队列为空
	//是则返回false -- 队列不为空
}
 
 
//队列大小函数 -- 判断队列结点(元素)个数
//接收队列类型指针(包含链表头尾结点) 
int QueueSize(Que* pq)
{
	//assert断言队列类型指针不为空：
	assert(pq != NULL);
 
	//直接返回size队列结点(元素)个数：
	return pq->size;
}

---------------------------------------------------------------------------------------------

Test.c


#define _CRT_SECURE_NO_WARNINGS 1
 
//包含二叉树头文件：
#include "BinaryTree.h"
 
 
 
//测试函数 -- 链式二叉树：
void Test()
{
	//手动创建多个链式二叉树节点：
	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; //节点1的左指针指向节点2
	node1->right = node3; //节点1的右指针指向节点3
	node2->left = node4; //节点2的左指针指向节点4
	node3->left = node5; //节点3的左指针指向节点5
	node3->right = node6; //节点3的右指针指向节点6
 
	//使用PrevOrder函数进行前序（先序）遍历：
	printf("对当前二叉树进行先序遍历:> ");
	PrevOrder(node1); //接收根节点
	printf("\n\n");
 
	//使用InOrder函数进行中序遍历：
	printf("对当前二叉树进行中序遍历:> ");
	InOrder(node1); //接收根节点
	printf("\n\n");
 
	//使用PostOrder函数进行后序遍历：
	printf("对当前二叉树进行后序遍历:> ");
	PostOrder(node1); //接收根节点
	printf("\n\n");
	
 
	//使用TreeSize计算当前二叉树节点数： 
	printf("当前二叉树节点个数为:> %d\n", TreeSize(node1));
	printf("\n");
 
	//使用TreeLeafSize计算当前二叉树节点数：
	printf("当前二叉树的叶子节点个数为:> %d\n", TreeLeafSize(node1));
	printf("\n");
 
	//使用TreeKLevel计算二叉树中第k层的节点个数：
	printf("当前二叉树中第3层的节点个数为:> %d\n", TreeKLevel(node1, 3));
	printf("\n");
 
	//使用LevelOrder使用队列进行层序遍历：
	printf("使用层序遍历遍历打印当前二叉树:> ");
	LevelOrder(node1);
	printf("\n");
 
	//使用TreeComplete判断当前链式二叉树是不是完全二叉树：
	printf("当前二叉树是不是完全二叉树:> %d\n", TreeComplete(node1));
	printf("\n");
 
	//使用TreeHeight函数计算当前二叉树的高度：
	printf("当前二叉树的高度为:> %d\n", TreeHeight(node1));
	printf("\n");
 
	//销毁二叉树类型：
	TreeDestory(node1);
	//销毁后将其置为空：
	node1 = NULL;
}
 
 
 
//主函数：
int main()
{
	Test();
 
	return 0;
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Cpp五条/article/detail/121918

【数据结构初阶】八、非线性表里的二叉树（二叉树的实现 -- C语言链式结构）

回顾

二叉树的概念及结构：

二叉树的概念

二叉树的结构

图示：

注意

二叉树的存储结构（补充）

链式结构

图示：

二叉树的遍历

递归结构遍历

前序(先序) / 中序 / 后序 的递归结构遍历

前序(先序)遍历图示：

中序遍历图示：

后序遍历图示：

层序遍历

层序遍历图示：

链式二叉树的实现

（详细解释在图片的注释中，代码分文件放下一标题处）

实现具体功能前的准备工作

图示：

BuyNode函数 -- 创建链式二叉树节点并对其初始化

图示：

PrevOrder函数 -- 前序（先序）遍历函数

图示：

InOrder函数 -- 中序遍历函数

图示：

PostOrder函数 -- 后序遍历函数

图示：

TreeSize函数 -- 计算链式二叉树中的节点个数

图示：

该函数递归步骤图：

TreeLeafSize函数 -- 计算链式二叉树中的叶子节点个数

图示：

该函数递归步骤图：

TreeKLevel函数 -- 计算链式二叉树中第k层的节点个数

图示：

该函数递归步骤图：

TreeDestory函数 -- 对链式二叉树类型进行销毁

图示：

该函数递归步骤图：

TreeFind函数 -- 在链式二叉树中查找值为x的节点

图示：

该函数递归步骤图：

LevelOrder函数 -- 对链式二叉树进行层序遍历

图示：

TreeComplete函数 -- 判断该链式二叉树是不是完全二叉树

图示：

TreeHeight函数 -- 计算当前链式二叉树的高度

图示：

总体测试：

对应代码

BinaryTree.h

Queue_BT.h

BinaryTree.c

Queue_BT.c

Test.c

前序(先序) / 中序 / 后序的递归结构遍历