[数据结构与算法]【普通二叉树（链式结构）各个接口实现-C语言】

前言

本文总结学习普通二叉树（链式结构）接口实现-C语言。

一、普通二叉树（链式结构）基本结构构建

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

// 该头文件的包含相当于将Queue.h的代码全部复制到此处，后续二叉树层序遍历和判断完全二叉树用到
#include "Queue.h"


// 普通二叉树链式结构的实现

// 说明：普通二叉树增删查改没有价值，如果是为了单纯存放数据，不如使用线性表


typedef int BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;


// 创建结点
BTNode* BuyBTNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	assert(newnode);

	newnode->data = x;
	newnode->left = NULL;
	newnode->right = NULL;

	return newnode;
}


// 构建一颗二叉树
BTNode* CreatBinaryTree()
{
	BTNode* node1 = BuyBTNode(1);
	BTNode* node2 = BuyBTNode(2);
	BTNode* node3 = BuyBTNode(3);
	BTNode* node4 = BuyBTNode(4);
	BTNode* node5 = BuyBTNode(5);
	BTNode* node6 = BuyBTNode(6);
	BTNode* test = BuyBTNode(99);

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

	return node1;
}

二、前序遍历（先根遍历）

// 前序遍历（先根遍历）
void PreOrder(BTNode* root)
{
	if (NULL == root)
	{
		printf("NULL ");
		return;
	}

	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}

三、中序遍历

// 中序遍历
void InOrder(BTNode* root)
{
	if (NULL == root)
	{
		printf("NULL ");
		return;
	}

	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

四、后序遍历

// 后序遍历
void PostOrder(BTNode* root)
{
	if (NULL == root)
	{
		printf("NULL ");
		return;
	}

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

五、二叉树结点个数

// 二叉树结点个数

// 方法1：
// 思路：（子问题）
// 1.空树，最小规模子问题，结点个数为0，返回0
// 2.非空树，左子树结点个数+右子树结点个数+1（自己）

// 分治：把复杂的问题，分成更小规模的子问题，子问题再分成更小规模的子问题。。。直到子问题不可再分割，直接能出结果
// （校长->院长->班长->舍长）

int BTreeSize(BTNode* root)
{
	return (NULL == root) ? 0 : \
		1 + BTreeSize(root->left) + \
		BTreeSize(root->right);
}

// 方法2：（main函数创建一个变量，传它的地址进来）（思路：遍历+计数，最优）
//void BTreeSize(BTNode* root, int* num)
//{
//	if (NULL == root)
//	{
//		return 0;
//	}
//	else
//	{
//		(*num)++;// 顺序无所谓，因为只是先加后加的问题
//		BTreeSize(root->left, num);
//		BTreeSize(root->right, num);
//	}
//}

// 方法3：（每次调用函数都需要提前将全局变量num置零）
// 不好！！！线程安全的问题，学linux就知道了，
// 多线程都在调用这个函数，你在调用我在调用，同时去执行，对同一个变量加加会错乱
//int num = 0;
//void BTreeSize(BTNode* root)
//{
//	if (NULL == root)
//	{
//		return;
//	}
//	else
//	{
//		num++;// 顺序无所谓，因为只是先加后加的问题
//		BTreeSize(root->left);
//		BTreeSize(root->right);
//	}
//}

// 方法4：（每次调用函数都需要提前将全局变量num置零，但是在main函数无法置零，所以这个方法错误！！！！！）
//int BTreeSize(BTNode* root)
//{
//	static int num = 0; //每次调用时,初始化只会执行一次
//
//	if (NULL == root)
//	{
//		return 0;
//	}
//	else
//	{
//		num++;// 顺序无所谓，因为只是先加后加的问题
//		BTreeSize(root->left);
//		BTreeSize(root->right);
//		return num;
//	}
//}

六、二叉树叶子结点个数

// 二叉树叶子结点个数(思路1：遍历+计数；思路2：分治)
// 分治思想
int BTreeLeafSize(BTNode* root)
{
	if (NULL == root)
	{
		return 0;
	}
	return (NULL == root->left && NULL == root->right) ? 1 : \
		BTreeLeafSize(root->left) + BTreeLeafSize(root->right);
}

七、二叉树第k层结点个数（k >= 1）

// 二叉树第k层结点个数（k >= 1）
// 分治思想
// 空树：返回0
// 非空且k==1，返回1
// 非空且k>1，返回左子树的k-1层结点数+右子树的k-1层结点数
int BTreeLevelSize(BTNode* root, int k)
{
	assert(k >= 1);

	if (NULL == root)
	{
		return 0;
	}
	return (1 == k) ? 1 : \
		BTreeLevelSize(root->left, k - 1) + \
		BTreeLevelSize(root->right, k - 1);
}

八、求二叉树高度

// 求二叉树高度
// 分治思想：
// 空树，高度为0
// 非空树，左子树高度和右子树高度大的那个+1
int BTreeDepth(BTNode* root)
{
	if (NULL == root)
	{
		return 0;
	}
	else
	{
		int leftDepth = BTreeDepth(root->left);
		int rightDepth = BTreeDepth(root->right);
		return (leftDepth > rightDepth) ? \
			1 + leftDepth : 1 + rightDepth;
	}
}

九、二叉树查找值为x的结点

// 二叉树查找值为x的结点
BTNode* BTreeFind(BTNode* root, BTDataType x)
{
	// 类似于先序查找
	if (NULL == root)
	{
		return NULL;
	}

	if (x == root->data)
	{
		return root;
	}

	BTNode* ret1 = BTreeFind(root->left, x);
	if (NULL != ret1)
	{
		return ret1;
	}
	// 可简化为：
	// return BTreeFind(root->left, x);// 不推荐，不容易看懂，逻辑不清晰

	BTNode* ret2 = BTreeFind(root->right, x);
	if (NULL != ret2)
	{
		return ret2;
	}
	// 可简化为：
	// return BTreeFind(root->right, x);// 不推荐，不容易看懂，逻辑不清晰

	return NULL; // 别忘记了！！！！
}

十、二叉树销毁

// 二叉树销毁
void BTreeDestory(BTNode** proot)
{
	if (NULL == *proot)
	{
		return;
	}

	// 类似于后序销毁
	BTreeDestory(&((*proot)->left));
	BTreeDestory(&((*proot)->right));

	free(*proot);
	*proot = NULL;
}
// 或者写为：
//void BTreeDestory(BTNode* root)
//{
//	if (NULL == root)
//	{
//		return;
//	}
//
//	// 类似于后序销毁
//	BTreeDestory(root->left);
//	BTreeDestory(root->right);
//
//	free(root);
//	// root = NULL; 在main中调用完处置空
//}

十一、二叉树层序遍历(需要借助队列)

借助的队列代码_Queue.c：

#define _CRT_SECURE_NO_WARNINGS 1

#include "Queue.h"


// 初始化队列
void QueueInit(Queue* pq) // point queue简写
{
	assert(pq);

	pq->head = NULL;
	pq->tail = NULL;
}


// 销毁队列
void QueueDestroy(Queue* pq)
{
	assert(pq);

	// 遍历链表，将每个结点释放掉，最后将头尾指针也置空
	QNode* cur = pq->head;
	while (NULL != cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}

	pq->head = NULL;
	pq->tail = NULL;

	// free(pq); 为啥不用？？？？？？？？？？？？？？因为初始状态是结构体，而不是结构体指针
}


// 队尾入队列
void QueuePush(Queue* pq, QDataType val)
{
	assert(pq);

	// 创建一个新结点，因为所有接口函数只有此函数需要，所以无需单独创建函数
	QNode* newnode = (QNode*)malloc(sizeof(QNode));

	if (NULL == newnode) // 或者assert也可以
	{
		printf("malloc fail\n");
		exit(-1);
	}
	else
	{
		// 初始化新结点！！！！！！！！别忘记
		newnode->next = NULL;
		newnode->val = val;

		if (NULL == pq->tail)
		{
			//assert(pq->head == NULL); //没必要，原因见下:
			// 当该链表的尾结点指针为NULL，此时头结点也一定为NULL时，将该结点作为头尾结点
			pq->head = newnode;
			pq->tail = newnode;
		}
		else
		{
			// 连接新尾结点
			pq->tail->next = newnode;

			// 更新尾结点指针
			pq->tail = newnode;
		}
	}
}


// 队头出队列
void QueuePop(Queue* pq)
{
	assert(pq);

	assert(pq->head && pq->tail);

	// 易错！！！！！！不加下面语句的代码会出现：
	// 当最后一个结点出队列后，head为NULL，而tail仍为尾结点，且改该尾结点已经被free了，此时tail为野指针
	// 补充代码：
	if (NULL == pq->head->next)
	{
		free(pq->head);
		pq->head = NULL;
		pq->tail = NULL;
	}
	else
	{
		// 记录头结点下一个位置
		QNode* next = pq->head->next;

		free(pq->head);
		// 更新头结点指针
		pq->head = next;
	}
}


// 检测队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	
	// 注：当仅剩一个结点时，二者相等，但是不为空，所以二者相等不能用来判定空

	return NULL == pq->tail;// 当尾结点指针为空时，头结点指针也必定为空；当头结点指针为空时，尾结点指针也必定为空
}


// 获取队列中有效元素个数
size_t QueueSize(Queue* pq)
{
	assert(pq);

	// 不能使用指针相减来求，因为链表的物理结构不连续!!!!!!
	
	// 方法1，在初始的队列结构中新增一个size变量，每次更新size来获取元素个数

	// 方法2，数数
	size_t num = 0;
	QNode* cur = pq->head;
	while (NULL != cur) // 或while(cur)
	{
		num++;
		cur = cur->next;
	}

	return num;
}


// 获取队列头部元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);

	assert(pq->head);

	return pq->head->val;
}


// 获取队列尾部元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);

	assert(pq->tail);

	return pq->tail->val;
}

借助的队列代码_Queue.h:

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>


// 当队列的数值不为int类型时，方便修改，当层序遍历二叉树时，作用就体现出来了

// 前置声明（类似函数声明），在此处用到该结构体指针，且在链式二叉树源文件中，此处需要向上找struct BinaryTreeNode的定义
// 所以需要前置声明，告诉编译器定义在后面找
struct BinaryTreeNode;// 声明类型，而不是全局变量（用到extern）

typedef struct BinaryTreeNode* QDataType;// 在链式二叉树源文件中，此处需要向上找struct BinaryTreeNode的定义


// 单链表结构（表示队列，定义结点）
typedef struct QListNode
{
	struct QListNode* next;
	QDataType val;
}QNode;


// 队列的结构（定义头尾指针，方便出入队列）
typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;


// 初始化队列
void QueueInit(Queue* pq);

// 销毁队列
void QueueDestroy(Queue* pq);

// 队尾入队列
void QueuePush(Queue* pq, QDataType val);

// 队头出队列
void QueuePop(Queue* pq);

// 检测队列是否为空
bool QueueEmpty(Queue* pq);

// 获取队列中有效元素个数
size_t QueueSize(Queue* pq);

// 获取队列头部元素
QDataType QueueFront(Queue* pq);

// 获取队列尾部元素
QDataType QueueBack(Queue* pq);

层序遍历代码：

// 二叉树的层序遍历(需要借助队列)
void LevelOrder(BTNode* root)
{
	// 先把根入队列，借助队列先进先出的性质，上一层结点出队列时带自己的两个子结点入队列，直到队列为空
	//（所以把结点指针或者结点入队列才能找到对应子结点，但是结点指针占空间小，所以传结点指针）

	if (NULL == root)
	{
		printf("root NULL\n");
		return;
	}

	Queue q = { 0 };
	QueueInit(&q);

	// 根结点不为空，入根结点
	QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		// 每轮循环会自动更新至队列的下一个元素
		BTNode* front = QueueFront(&q);// 记录该非空结点（QueuePop(&q);之后仍然可以调用它的左右子结点）

		printf("%d ", front->data);

		// 也可以放在最后
		QueuePop(&q);
		if (front->left)
		{
			QueuePush(&q, front->left);
		}
		if (front->right)
		{
			QueuePush(&q, front->right);
		}
	}

	QueueDestroy(&q);
}

十二、判断二叉树是否为完全二叉树（需要借助队列）

借助队列同十一章节队列

// 判断二叉树是否为完全二叉树（需要借助队列）
bool BTreeComplete(BTNode* root)
{
	// 首先模仿层序遍历（NULL结点也如入队列），直到队头元素为NULL（出到空结点时）时，退出循环
	// 从出到的空结点起开始向后出队列现存的所有数据，如果全为空：则说明是完全二叉树；否则一旦遇到非空元素，则说明不是

	Queue q = { 0 };
	QueueInit(&q);

	if (NULL == root) // 空树也为完全二叉树，向下执行，直到最后返回true ！！！！！！！！！！！
	{
		// 根非空，入队列
		QueuePush(&q, root);
	}

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		if (NULL == front)
		{
			// 队头数据（出到的数据）为空直接退出循环
			// 如果是非完全二叉树：有没有将所有数据入队列完不重要，因为上一层的父节点出队列必然会将左右子结点带入队列，
			// 所以即使左子树很小，很快就出到NULL，但是非完全树，它右边的兄弟或表兄弟结点肯定有不为空的结点已经在队列的NULL后面
			// 如果是完全二叉树：那么所有（包括空结点）必然全部已经入队列 ！！！！！！！！！
			break;
		}
		else
		{
			// 无需考虑空或非空，直接入队列
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}
	}

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);// 刚刚判断了队列不为空，所以此处必不为空
		QueuePop(&q);

		if (front)
		{
			// 好习惯：先销毁（防止内存泄漏）！！！！！！！！！！
			QueueDestroy(&q);
			// 队头数据（出到的数据）为非空直接返回false
			return false;
		}
		// 为空，继续执行下一轮循环（会自动更新到下一个结点) ！！！！！！！！！！！
	}

	// 好习惯：先销毁（防止内存泄漏）
	QueueDestroy(&q);
	return true;

	//while (!QueueEmpty(&q))
	//{
	//	if (front)// front数据不为空
	//	{
	//		// 不是完全二叉树，直接返回false
	//		return false;
	//	}
	//	else
	//	{
	//		// 更新front（无须继续入队列）
	//		QueuePop(&q);
	//		if (!QueueEmpty(&q))// 防止QueueFront(&q);中报错  // 写法不好。更新见上！！！！！！！！！！！
	//		{
	//			front = QueueFront(&q);
	//		}
	//	}
	//}

	
}

十三、测试代码：

int main()
{
	BTNode* tree = CreatBinaryTree();//或者起名root

	// 前序遍历（先根遍历）
	PreOrder(tree);
	printf("\n");

	// 中序遍历
	InOrder(tree);
	printf("\n");

	// 后序遍历
	PostOrder(tree);
	printf("\n");

	// 二叉树结点个数
	printf("Size:%d\n", BTreeSize(tree));

	// 二叉树叶子结点个数
	printf("LeafSize:%d\n", BTreeLeafSize(tree));

	// 二叉树第k层结点个数（k >= 1）
	printf("LevelSize:%d\n", BTreeLevelSize(tree, 3));

	// 求二叉树高度
	printf("Depth:%d\n", BTreeDepth(tree));

	// 二叉树查找值为x的结点（可结合修改，再次排序来使用）
	// 测试查找所有值，包括测试查找不存在的值
	for (int i = 1; i <= 7; i++)
	{
		BTNode* ret = BTreeFind(tree, i);
		printf("BTreeFind:%d %p\n", i, ret); // 测试地址，因为如果测试7时，ret为NULL，去访问它的值就会形成非法访问
	}

	// 二叉树层序遍历
	LevelOrder(tree);
	printf("\n");

	// 判断二叉树是否为完全二叉树（需要借助队列）
	if (BTreeComplete(tree))
	{
		printf("该树是完全二叉树\n");
	}
	else
	{
		printf("该树不是完全二叉树\n");
	}

	// 二叉树销毁
	BTreeDestory(&tree);

	return 0;
}

总结

这里对文章进行总结：
以上就是今天总结的内容，本文包括了C语言实现普通二叉树（链式结构）各个接口，分享给大家。
真💙欢迎各位给予我更好的建议，欢迎访问！！！小编创作不易，觉得有用可以一键三连哦，感谢大家。peace
希望大家一起坚持学习，共同进步。梦想一旦被付诸行动，就会变得神圣。

欢迎各位大佬批评建议，分享更好的方法！！！🙊🙊🙊

创作挑战赛

新人创作奖励来咯，坚持创作打卡瓜分现金大奖