《数据结构初阶》【链式二叉树】

typedef int TDataType;

/**
 * @brief 树节点结构体定义（孩子-兄弟表示法）
 * @details 采用左孩子右兄弟表示法，将多叉树转换为二叉树形式存储
 *          每个节点包含数据域和两个指针域
 */
typedef struct TreeNode
{
    TDataType data;              // 节点中的数据域
    struct TreeNode* pfirstChild;   // 指向第一个孩子结点
    struct TreeNode* pNextBrother;  // 指向其下一个兄弟结点
}TNode;

//任务2：定义堆的结构体（存储类型）
typedef int HPDataType;
typedef struct Heap
{
	//核心思路：堆是完全二叉树所以使用数组实现比较好
	
	//1.记录数组的容量 ---> 一个int变量
	//2.记录当前数组中元素的数量 --> 一个int变量
	//3.使用数组存储堆中的节点 ---> 定义一个动态数组
	int capacity;
	int size;
	HPDataType* a;
	
}HP;

typedef int BTDataType;

typedef struct BinaryTreeNode
{
	//1.存储二叉树节点存储的值
	//2.存储节点的左孩子指针
	//3.存储节点的右孩子指针
	BTDataType data;
	struct BinaryTreeNode* left; //注意：这里还是要注意不要忘记使用struct
	struct BinaryTreeNode* right;
}BTNode;

typedef int BTDataType;

typedef struct BinaryTreeNode
 {
    BTDataType data;            // 当前结点值域
    
    struct BinTreeNode* parent; // 指向当前结点的双亲
    struct BinTreeNode* left;   // 指向当前结点左孩子
    struct BinTreeNode* right;  // 指向当前结点右孩子
}BTNode;

------------------------------BinaryTree.h------------------------------

#pragma once

//任务1：声明需要使用头文件
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "Queue.h"

//任务2：定义二叉树的存储结构体
typedef int BTDataType;

typedef struct BinaryTreeNode
{
	//1.存储二叉树节点存储的值
	//2.存储节点的左孩子指针
	//3.存储节点的右孩子指针
	BTDataType data;
	struct BinaryTreeNode* left; //注意：这里还是要注意不要忘记使用struct
	struct BinaryTreeNode* right;
}BTNode;

//任务3：声明二叉树的接口函数

//注意：初阶数据结构阶段的学习我们只会去实现一些简单的接口
//例如：二叉树的创建暂时并不涉及，初学阶段我们直接使用手动创建的二叉树来测试我们完成的简单的接口

/*------------------------------ 递归实现 ------------------------------*/
//0.二叉树的节点的创建 + 初始化

//1.二叉树的前序遍历
//2.二叉树的中序遍历
//3.二叉树的后序遍历


//4.二叉树的求树中节点的个数
//5.二叉树的求树中叶子节点的个数
//6.二叉树的求树的高度

//7.二叉树的求树中第K层节点的个数
//8.二叉树的寻找树中某个值
//9.二叉树的销毁
/*------------------------------ 非递归实现 ------------------------------*/
//10.二叉树的层序遍历 （需要使用数据结构：队列）
//11.二叉树的判断是否为完全二叉树 （需要使用数据结构：队列）


BTNode* BTCreatNode(int x);

void PrevOrder(BTNode* root);
void InOrder(BTNode* root);
void PostOrder(BTNode* root);


int BTSize(BTNode* root);
int BTLeafSize(BTNode* root);
int BTHeight(BTNode* root);

int BTLevelKSize(BTNode* root, int k);
BTNode* BTFind(BTNode* root, int x);
void BTDestroy(BTNode* root);

void LevelOrder(BTNode* root);
bool BTComplete(BTNode* root);

--------------------------------Queue.h--------------------------------
#pragma once

//任务1：声明需要使用的头文件
//任务2：定义队列的结构体
//任务3：声明队列的接口函数

//任务1：
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>

//任务2：
typedef struct BinaryTreeNode* QDateType; //使用typedf重新定义队列中的变量的数据类型，方便后续进行修改

//队列节点的结构体
typedef struct QueueNode
{
	//1.队列节点中存储的数据 ---> 一个int变量
	//2.队列节点中存储下一个节点的位置 ---> 一个指针

	QDateType val;
	struct QueueNode* next; //注意这里next的类型可千万不要使用QNode哦，因为这时你还没有定义QNode，也不要使用QueueNode进行代替
}QNode;

//队列的结构体（使用带头尾指针的结构）
typedef struct Queue
{
	//1.记录当前队列中元素的个数 ---> 一个int变量
	//2.指向头部的指针 ---> （用于：头删/取队头的元素）
	//3.指向尾部的指针 ---> （用于：尾插/取队尾的元素）
	int size;
	QNode* queHead;
	QNode* queTail;
}Que;


//任务3：
//1.队列的初始化
//2.队列的销毁

//3.队列的入队
//4.队列的出队

//5.队列的取队头元素
//6.队列的取队尾元素


//7.队列的判空
//8.队列的求队列中元素的数量


void QueInit(Que* pque);
void QueDestroy(Que* pque);

void QuePush(Que* pque, QDateType x);
void QuePop(Que* pque);

QDateType QueFront(Que* pque);
QDateType QueBack(Que* pque);

bool QueEmpty(Que* pque);
int QueSize(Que* pque);

------------------------------BinaryTree.c------------------------------

#define _CRT_SECURE_NO_WARNINGS 1

#include "BinaryTree.h"

//0.实现：“二叉树的节点的创建 + 初始化”操作
/*****************************************************************
 * @brief 动态创建二叉树节点
 * @param x 节点要存储的数据值
 * @return 成功返回节点指针，失败返回NULL
 * @note 使用malloc动态分配内存
 *       典型错误处理：
 *       1. 内存分配失败时打印错误信息
 *       2. 新节点的左右指针初始化为NULL
 *****************************************************************/
BTNode* BTCreatNode(int x)
{
	/*--------第一阶段：动态申请节点的内存空间--------*/
	//1.使用malloc进行动态的内存分配
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	//2.检查内存是否开辟成功
	if (node == NULL)
	{
		perror("malloc fail");
		return NULL;
	}

	/*--------第二阶段：初始化节点的数据--------*/
	node->data = x;
	node->left = NULL;
	node->right = NULL;


	/*--------第二阶段：返回开辟的二叉树节点的内存地址--------*/
	return node;
}




//1.实现：“二叉树的前序遍历”操作
/*****************************************************************
 * @brief 二叉树前序遍历（递归实现）
 * @param root 当前遍历的子树根节点
 * @note 遍历顺序：根节点->左子树->右子树
 *       输出格式：非空节点输出数据，空节点输出"N "
 *       示例输出：1 2 3 N N N 4 5 N 6 N N 6 N N
 *****************************************************************/

void PrevOrder(BTNode* root)
{
	//1.递归结束的出口
	if (root == NULL)
	{
		printf("N "); //也可以不写，只是为了方便初学者能更好的理解前序遍历而添加的
		return;
	}

	//2.按照：根节点 ---> 左子树 ---> 右子树 的顺序进行递归遍历
	printf("%d ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}



//2.实现：“二叉树的中序遍历”操作
/*****************************************************************
 * @brief 二叉树中序遍历（递归实现）
 * @param root 当前遍历的子树根节点
 * @note 遍历顺序：左子树->根节点->右子树
 *       输出格式同前序遍历
 *       示例输出：N 3 N 2 N 1 N 5 N 6 N 4 N 6 N
 *****************************************************************/

void InOrder(BTNode* root)
{
	//1.递归结束的出口
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	//按照：左子树 ---> 根节点 ---> 右子树 的顺序进行递归遍历
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}



//3.实现：“二叉树的后序遍历”操作
/*****************************************************************
 * @brief 二叉树后序遍历（递归实现）
 * @param root 当前遍历的子树根节点
 * @note 遍历顺序：左子树->右子树->根节点
 *       输出格式同前序遍历
 *       示例输出：N N 3 N 2 N N 6 5 N N 6 4 1
 *****************************************************************/

void PostOrder(BTNode* root)
{
	//1.递归结束的出口
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	//2.按照：左子树 ---> 右子树  ---> 根节点 的顺序进行递归遍历
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}


//4.实现：“二叉树的求树中节点的个数”操作
/*****************************************************************
 * @brief 计算二叉树节点总数（递归）
 * @param root 当前子树根节点
 * @return 以root为根的树的节点总数
 * @note 计算公式：
 *       空树：0
 *       非空树：左子树节点数 + 右子树节点数 + 1(当前节点)
 *****************************************************************/

int BTSize(BTNode* root)
{
	//1.处理：空树 + 空节点 的情况（同样是递归结束的条件）
	if (root == NULL) return 0;
	else
	{
		return BTSize(root->left) + BTSize(root->right) + 1;
	}



	//跟简洁的写法：
	//return root == NULL ? 0 : BTSize(root->left) + BTSize(root->right) + 1;
}


//5.实现：“二叉树的求树中叶子节点的个数”操作
/*****************************************************************
 * @brief 计算二叉树叶子节点数（递归）
 * @param root 当前子树根节点
 * @return 以root为根的树的叶子节点数
 * @note 叶子节点定义：无左右子树的节点
 *       计算公式：
 *       空树：0
 *       叶子节点：1
 *       非叶子节点：左子树叶子数 + 右子树叶子数
 *****************************************************************/

int BTLeafSize(BTNode* root)
{
	//1.处理：空树 + 一度节点 的情况 （同样是递归结束的条件）
	if (root == NULL) return 0;

	//2.使用if判断如果：当前遍历到的节点是叶子节点 （同样是递归结束的条件）
	if (root->left == NULL && root->right == NULL) return 1;
	else
	{
		return BTLeafSize(root->left) + BTLeafSize(root->right);
	}

}



//6.实现：“二叉树的求树的高度”操作
/*****************************************************************
 * @brief 计算二叉树高度/深度（递归）
 * @param root 当前子树根节点
 * @return 以root为根的树的高度
 * @note 高度定义：
 *       空树高度为0
 *       非空树高度为max(左子树高, 右子树高) + 1
 *       优化：避免重复计算左右子树高度
 *****************************************************************/

int BTHeight(BTNode* root)
{
	//1.处理：空树 +
	if (root == NULL) return 0;

	//2.计算非空树的高度
	//2.1：递归计算左子树和右子树的高度  --->  进行优化（这里先将结果计算出来，避免进行重复的计算）
	int leftHeight = BTHeight(root->left);
	int rightHeight = BTHeight(root->right);

	//2.2：返回非空树的高度
	return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}



//7.实现：“二叉树的求树中第K层节点的个数”操作
/*****************************************************************
 * @brief 计算二叉树第k层节点数（递归）
 * @param root 当前子树根节点
 * @param k 目标层数（从1开始计数）
 * @return 第k层节点数
 * @note 计算公式：
 *       空树或k<1：0
 *       k==1：1（当前节点）
 *       其他：左子树k-1层节点数 + 右子树k-1层节点数
 *****************************************************************/

int BTLevelKSize(BTNode* root, int k)
{
	//1. 处理：空树 + 一度节点 情况
	if (root == NULL) return 0;

	//2.使用if判断：如果当前K值为1
	if (k == 1)  return 1;

	//3.递归计算左右子树的第K层
	return BTLevelKSize(root->left, k - 1) + BTLevelKSize(root->right, k - 1);
}


//8.实现：“二叉树的寻找树中的某个节点的位置”操作
/*****************************************************************
 * @brief 在二叉树中查找值为x的节点（递归）
 * @param root 当前子树根节点
 * @param x 要查找的值
 * @return 找到的节点指针，未找到返回NULL
 * @note 查找顺序：
 *       1. 检查当前节点
 *       2. 递归查找左子树
 *       3. 若左子树未找到，递归查找右子树
 *       注意：如果树中存在多个x，返回最先找到的节点
 *****************************************************************/
BTNode* BTFind(BTNode* root, int x)
{
	//1.处理：“空树 + 遍历到空节点”的情况
	if (root == NULL) return NULL;

	//2.使用if判断：如果遍历到的节点的值是x
	if (root->data == x) return root;

	//3.进行递归查找
	//3.1：先在左子树中进行递归查找
	BTNode* ret = BTFind(root->left, x);
	if (ret) return ret;

	//3.2：再在右子树中进行递归操作
	ret = BTFind(root->right, x);
	if (ret) return ret;

	//4.返回空指针标志未找到
	return NULL;


	//可以将“在右子树寻找 + 未找到”的情况进行合并简化
	//原因：在右子树中没有找到：（代表整棵树中真的没有你想找的这个值）
	//return BTFind(root->right, x);
}


//9.实现：“二叉树的销毁”操作
/**
 * @brief 销毁二叉树（后序遍历方式）
 * @param root 二叉树根节点指针
 * @note 递归释放所有节点内存
 *       采用后序遍历顺序：先销毁左子树，再销毁右子树，最后释放当前节点
 */
void BTDestroy(BTNode* root)
{
	//1.处理：“空树 + 遍历到空节点”的情况
	if (root == NULL)  return;

	//2.使用后序遍历的方式进行递归的销毁
	BTDestroy(root->left);
	BTDestroy(root->right);
	free(root);
}



//10.实现：“二叉树的层序遍历”操作
/**
 * @brief 二叉树层序遍历（广度优先遍历）
 * @param root 二叉树根节点指针
 * @note 使用队列辅助实现：
 *       1. 根节点入队
 *       2. 循环取出队首元素并处理
 *       3. 将其左右子节点入队
 *       时间复杂度：O(n)，空间复杂度：O(n)
 */
void LevelOrder(BTNode* root)
{
	//1.创建队列 + 初始化队列
	Que que;
	QueInit(&que);

	//2.将二叉树的根节点入队
	if (root)
	{
		QuePush(&que, root);
	}

	//3.遍历队列来实现树的层序遍历
	while (!QueEmpty(&que))
	{
		//3.1：将队头元素：“记录 + 出队 + 输出”
		BTNode* front = QueFront(&que);
		QuePop(&que);
		printf("%d ", front->data);

		//3.2：将队头的二叉树的节点的左孩子和右孩子添加到队列中
		if (front->left) QuePush(&que, front->left); //注意：这里是（front->left而不是root->left）
		if (front->right) QuePush(&que, front->right);
	}


	//4.销毁队列
	QueDestroy(&que);
}


//11.实现：“二叉树的判断其是否是一棵完全二叉树”操作
/**
 * @brief 判断是否是完全二叉树
 * @param root 二叉树根节点指针
 * @return true-是完全二叉树，false-不是完全二叉树
 * @note 完全二叉树判定条件：
 *       1. 层序遍历遇到第一个NULL节点后，后续不应再有非NULL节点
 *       2. 使用队列辅助实现，NULL节点也入队
 *       时间复杂度：O(n)，空间复杂度：O(n)
 */
bool BTComplete(BTNode* root)
{
	//1.创建队列 + 初始化队列
	Que que;
	QueInit(&que);

	//2.将二叉树的根节点入队
	if (root) QuePush(&que, root);

	//3.按照层序遍历：“找到层序遍历的第一个空节点的位置”
	while (!QueEmpty(&que))
	{
		//3.1：将队头元素：“记录 + 出队 + 判断”
		BTNode* front = QueFront(&que);
		QuePop(&que);
		if (front == NULL) break;


		//3.2：将队头的二叉树的节点的左孩子和右孩子添加到队列中 
		QuePush(&que, front->left); //注意：这里是无论子节点是否为空都将其入队
		QuePush(&que, front->right);
	}



	//4.按照层序遍历：“检查剩余节点是否有非空节点”
	while (!QueEmpty(&que))
	{
		//3.1：将队头元素：“记录 + 出队 + 判断”
		BTNode* front = QueFront(&que);
		QuePop(&que);
		if (front != NULL)
		{
			QueDestroy(&que);
			return false;
		}
	}

	QueDestroy(&que);
	return true;
}

------------------------------Queue.c------------------------------
#include "Queue.h"

//1.实现：“队列的初始化”操作
void QueInit(Que* pque)
{
	assert(pque);

	//1.将队列结构体中“元素的数量”置为0
	pque->size = 0;
	//2.将队列结构体中“指向队头/队尾的指针”置为空指针
	pque->queHead = NULL;
	pque->queTail = NULL;
}

//2.实现：“队列的销毁”操作
void QueDestroy(Que* pque)
{
	assert(pque);

	//1.将队列结构体中“元素的数量”置为0
	pque->size = 0;

	//2.将队列中的所有的节点都释放掉
	//1）创建临时指针代替queHead进行遍历队列的节点
	QNode* tmp = pque->queHead;
	//2）使用tmp遍历所有的节点
	while (tmp != NULL)
	{
		//3）创建后继指针存储当前遍历到的节点的下一位置
		QNode* next = tmp->next;
		//4)释放当前遍历到的节点
		free(tmp);
		//5)更新tmp指针
		tmp = next;
	}
	//将队列结构体中“指向队列头部/尾部的指针”置为空指针
	pque->queHead = NULL;
	pque->queTail = NULL;
}


//3.实现：“队列的入队”操作
void QuePush(Que* pque, QDateType x)
{
	assert(pque);
	//思路：使用链表的尾插法实现入队的操作

	//1）先创建出来一个队列的节点
	QNode* newNode = (QNode*)malloc(sizeof(QNode));
	//1.1:判断新开辟的空间是否开辟成功哦
	if (newNode == NULL)
	{
		perror("malloc fail");
		return;
	}
	//2）为这个节点进行赋值
	newNode->val = x;
	//3）将这个节点链接到队列链表的后面
	//3.1：将新开辟的节点的next指针域置空
	newNode->next = NULL;
	//3.2：将新开辟的节点链接到队列链表的尾部
	//3.3.1：如果当前的队列链表中没有节点
	if (pque->queTail == NULL)
	{
		pque->queHead = pque->queTail = newNode;
	}
	//3.3.2：如果当前的队列链表中有节点
	else
	{
		pque->queTail->next = newNode;
		pque->queTail = newNode;
	}

	//4）队列中的元素的数量增加
	pque->size++;
}

//4.实现：“队列的出队”操作
void QuePop(Que* pque)
{
	assert(pque);
	assert(pque->size > 0);//注意：当我们：1.删除某个数据结构中的元素时 2.从某个数据结构中取出元素的时
	//---> 需要判断当前的数据结构中是否还有元素
	//思路：使用链表的头删法实现出队操作

	//1）如果当前队列中只有一个元素
	if (pque->queHead->next == NULL)
	{
		//1.1：将这一个节点删除掉
		free(pque->queHead);
		//1.2：将指向队头和队尾的指针都置为空
		pque->queHead = NULL;
		pque->queTail = NULL;
	}
	//2）如果队列中的元素有多个
	else
	{
		//2.1：创建一个临时的指针来存放queHead指针的下一个位置
		QNode* next = pque->queHead->next;
		//2.2：释放掉queHead指针指向的节点
		free(pque->queHead);
		//2.3：将queHead指针移动到下一个节点的位置
		pque->queHead = next;
	}
	//3）队列中的元素的数量减少
	pque->size--;
}


//5.实现：“队列的取出队头元素”操作
QDateType QueFront(Que* pque)
{
	assert(pque);
	assert(pque->size > 0);

	return pque->queHead->val;
}

//6.实现：“队列的取出队尾元素”操作
QDateType QueBack(Que* pque)
{
	assert(pque);
	assert(pque->size > 0);

	return pque->queTail->val;
}


//7.实现：“队列的判空”
bool QueEmpty(Que* pque)
{
	assert(pque);

	return pque->size == 0; //队列中没有元素返回真；队列中有元素返回假
}


//8.实现：“队列的求出队列中元素的个数”操作
int QueSize(Que* pque)
{
	assert(pque);

	return pque->size;
}

------------------------------Test.c------------------------------
#include "BinaryTree.h"

int main()
{
	/*****************************************************************
	* @brief 创建固定结构的二叉树（示例）
	* @return 返回构建好的二叉树根节点指针
	* @note 构建的二叉树结构：
	*         1
	*        / \
	*       2   4
	*      /   / \
	*     3   5   6
	*          \
	*           6
	* 注意：实际应用中应该从输入构建树，这里为演示硬编码
	*****************************************************************/
	/*--------第一阶段：创建二叉树的节点--------*/
	BTNode* node1 = BTCreatNode(1);
	BTNode* node2 = BTCreatNode(2);
	BTNode* node3 = BTCreatNode(3);
	BTNode* node4 = BTCreatNode(4);
	BTNode* node5 = BTCreatNode(5);
	BTNode* node6 = BTCreatNode(6);
	BTNode* node7 = BTCreatNode(6);



	/*--------第二阶段：构建二叉树的结构--------*/
	node1->left = node2;
	node1->right = node4;

	node2->left = node3;
	node4->left = node5;
	node4->right = node6;

	node5->right = node7;

	/*--------第三阶段：测试二叉树的接口函数--------*/
	//1.测试遍历算法 
	printf("前序遍历: ");
	PrevOrder(node1);		// 预期输出：1 2 3 N N N 4 5 N 6 N N 6 N N
	printf("\n");

	printf("中序遍历: ");
	InOrder(node1);		    // 预期输出：N 3 N 2 N 1 N 5 N 6 N 4 N 6 N
	printf("\n");

	printf("后序遍历: ");
	PostOrder(node1);       // 预期输出：N N 3 N 2 N N N 6 5 N N 6 4 1
	printf("\n");
	
	//2.测试树属性计算
	printf("节点总数: %d\n", BTSize(node1));       // 预期：7
	printf("叶子节点数: %d\n", BTLeafSize(node1)); // 预期：3（节点3、6、6）
	printf("树高度: %d\n", BTHeight(node1));       // 预期：4
	printf("第3层节点数: %d\n", BTLevelKSize(node1, 3)); // 预期：3（节点3、5、6）
	printf("第4层节点数: %d\n", BTLevelKSize(node1, 4)); // 预期：1（节点6）



	//3.测试查找功能 
	int target = 6;
	BTNode* found = BTFind(node1, target);
	if (found) 	printf("找到节点%d\n", target);
	else 	printf("未找到节点%d\n", target);


	//4.测试层序遍历
	printf("层序遍历: ");
	LevelOrder(node1);  // 预期输出：1 2 4 3 5 6 6
	printf("\n");

	//5.测试判断是否为完全二叉树
	if (BTComplete(node1))
		printf("该二叉树是完全二叉树\n");
	else
		printf("该二叉树不是完全二叉树\n");

	//6.测试二叉树销毁
	BTDestroy(node1);
	printf("二叉树已销毁\n");

	return 0;
}