【数据结构与算法】数据结构初阶：详解二叉树（五）——链式结构二叉树（下）：二叉树的链式结构的实现

艾莉丝努力练剑

发布于 2025-11-12 19:04:33

1920

文章被收录于专栏：C / C++C / C++

前言：本篇文章，我们继续来看二叉树相关的知识点，在初阶的数据结构与算法阶段，我们把知识点分成三部分，复杂度作为第一部分，顺序表和链表、栈和队列、二叉树为第二部分，排序为第二部分，我们之前已经介绍完了第一部分：算法复杂度，本文我们将正式开始学习第二部分中的二叉树部分内容啦。注意，二叉树的学习需要一定的基础，涉及到【函数栈帧的创建与销毁】，而且二叉树尤其是链式结构二叉树基本上是递归算法的暴力美学。

【掌握递归】函数递归思想的形成及其应用

正文

这里博主补充一点二叉树的性质：

我们接下来证明一下上述的这条性质：

四、二叉树的链式结构

（三）链式结构的实现

3、二叉树结点个数

（1）思路1：size是局部变量

如果我每次都定义一个size，我在递归的过程中，每一个函数栈帧中都有一个局部变量size：

Tree.c：

局部变量行不通，每次遍历，size都会被初始化。

（2）思路2：size是全局变量

那我们把它定义成一个全局的可不可以？不可以。

Tree.c：

int size = 0;
//二叉树结点个数 
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	size++;
	BinaryTreeSize(root->left);
	BinaryTreeSize(root->right);

	return size;
}

运行一下，可以看到：我们调用一次BinaryTreeSize没有问题——

那么如果再调用一次呢？

有问题了，size怎么能够叠加呢？这说明size在不断地累加。

难道后面我们只调用一次二叉树结点个数吗？不会啊，我们肯定会多次用到。

错误总结：创建全局变量，多次调用方法会出现累加的情况。

（3）思路3：给size加上static

Tree.c：

static int size = 0;
//二叉树结点个数 
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	size++;
	BinaryTreeSize(root->left);
	BinaryTreeSize(root->right);

	return size;
}

我们再运行一下——

还是没什么用。

（4）思路4：修改结构体——增加size

Tree.h：

typedef char BTDataType;
//定义二叉树节点结构
typedef struct BinaryTreeNode
{
	BTDataType data; // 当前结点值域
	struct BinTreeNode* left; // 指向当前结点左孩子
	struct BinTreeNode* right; // 指向当前结点右孩子 
	int size;
}BTNode;

问题：每2创建一个节点，它将会大四个字节（有可能还不止），既然每添加一个节点就要增加四个字节的大小，太不划算了。

（5）思路5：修改函数的参数——增加新的变量size

头文件这里自然也要改掉——

test.c文件这里既然返回的是void，就不能再打印了——

我们运行一下——

怎么回事？大家有想到吗？没错，传址。

老生常谈的问题：传值调用，形参不影响实参，形参是实参的一份临时拷贝。

既然要传址，我们要用到一级指针：

当然，头文件也要改：

我们把size改成Treesize，方便区分实参和形参：

运行一下——

这只是一次运行，如果我们多运行几次就得要这样写：

这样改也有问题：

（1）会改变原本的函数声明，参数要再加一个，返回值也要改；（2）其次，非常麻烦的一点——我们每次在函数调用的时候，都要手动把第二个参数Treesize置为0。

这种方法可以是可以，就是实在是太麻烦了！

（6）最优解法：递归实现

如果不创建新的变量，就只能想到递归了——

Tree.c：

//二叉树结点个数 = 1 + 左子树结点个数 + 右子树结点个数 
int BinaryTreeSize(BTNode* root)
{
	if (root == 0)
	{
		return 0;
	}
	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

运行一下——

我们调用三遍，看会不会出现像思路2【全局变量】那种累加的情况呢？我们观察一下——

可以看到：累加的情况没有出现。

这个就是求二叉树结点个数一个充满递归算法暴力美学的例子。

4、二叉树叶子结点个数

Tree.c：

//二叉树叶子结点个数 
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);
}

运行一下——

5、二叉树第k层结点个数

Tree.c：

//二叉树第k层结点个数 
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	//判断是否为第K层
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->left, k - 1) 
        + BinaryTreeLevelKSize(root->right, k - 1);
}

我们让k等于3，调试运行一下，看看结果是不是3——

6、二叉树的深度/高度

我们如果写成一个三目表达式，是不是太长了？我们把它们保存一下——

Tree.c：

//二叉树的深度/高度
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftDep = BinaryTreeDepth(root->left);
	int rightDep = BinaryTreeDepth(root->right);
	//根节点+max(左子树高度，右子树高度)
	return 1 + (leftDep > rightDep ? leftDep : rightDep);
	//return 1 + (BinaryTreeDepth(root->left) > BinaryTreeDepth(root->right) ?
	//	BinaryTreeDepth(root->left) : BinaryTreeDepth(root->right);
}

用一个三目表达式判断一下，我们这样打印——

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

Tree.c：

//二叉树查找值为x的结点 
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	BTNode* leftFind = BinaryTreeFind(root->left, x);
	if (leftFind)
	{
		return leftFind;
	}
	BTNode* rightFind = BinaryTreeFind(root->right, x);
	if (rightFind)
	{
		return rightFind;
	}
		return NULL;
}

我们先查找一个有的值' E '——

运行一下——

我们再查找一个没有的值' H '——

二叉树查找值为x的结点的代码就写完了。

8、二叉树销毁(后序遍历)

Tree.c：

// 二叉树销毁(后序遍历)
void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}
	BinaryTreeDestory(&((*root)->left));
	BinaryTreeDestory(&((*root)->right));
	free(*root);
	*root = NULL;
}

都是后序遍历，对比一下——

链式结构实现的完整代码

Tree.h：

#pragma once
#include<stdio.h>
#include<stdlib.h>

typedef char BTDataType;
//定义二叉树节点结构
typedef struct BinaryTreeNode
{
	BTDataType data; // 当前结点值域
	struct BinTreeNode* left; // 指向当前结点左孩子
	struct BinTreeNode* right; // 指向当前结点右孩子 
}BTNode;

//前序遍历
void PerOrder(BTNode* root);

//中序遍历
void InOrder(BTNode* root);

//后序遍历
void PostOrder(BTNode* root);

//二叉树结点个数 
int BinaryTreeSize(BTNode* root);
//void BinaryTreeSize(BTNode* root, int* psize);

//二叉树叶子结点个数 
int BinaryTreeLeafSize(BTNode* root);

//二叉树第k层结点个数 
int BinaryTreeLevelKSize(BTNode* root, int k);

//二叉树的深度/高度
int BinaryTreeDepth(BTNode* root);

//二叉树查找值为x的结点 
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);

// 二叉树销毁
void BinaryTreeDestory(BTNode** root);

Tree.c：

#define  _CRT_SECURE_NO_WARNINGS  1
#include"Tree.h"

//前序遍历————口诀：根左右
void PerOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->data);
	PerOrder(root->left);
	PerOrder(root->right);
}

//中序遍历——左根右
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	InOrder(root->left);
	printf("%c ", root->data);
	InOrder(root->right);
}

//后序遍历——左右根
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%c ", root->data);
}

////错误：创建全局变量，多次调用方法会出现累加的情况
//int size = 0;
////二叉树结点个数 
//int BinaryTreeSize(BTNode* root)
//{
//	if (root == NULL)
//	{
//		return 0;
//	}
//	size++;
//	BinaryTreeSize(root->left);
//	BinaryTreeSize(root->right);
//
//	return size;
//}

//方法二：需要改造函数定义
////二叉树结点个数
//void BinaryTreeSize(BTNode* root, int* psize)
//{
//	if (root == NULL)
//	{
//		return 0;
//	}
//	(*psize)++;
//	BinaryTreeSize(root->left,psize);
//	BinaryTreeSize(root->right,psize);
//}

//二叉树结点个数 = 1 + 左子树结点个数 + 右子树结点个数 
int BinaryTreeSize(BTNode* root)
{
	if (root == 0)
	{
		return 0;
	}
	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

//二叉树叶子结点个数 
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)
{
	if (root == NULL)
	{
		return 0;
	}
	//判断是否为第K层
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

//二叉树的深度/高度
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftDep = BinaryTreeDepth(root->left);
	int rightDep = BinaryTreeDepth(root->right);
	//根节点+max(左子树高度，右子树高度)
	return 1 + (leftDep > rightDep ? leftDep : rightDep);
	//return 1 + (BinaryTreeDepth(root->left) > BinaryTreeDepth(root->right) ?
	//	BinaryTreeDepth(root->left) : BinaryTreeDepth(root->right);
}

//二叉树查找值为x的结点 
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	BTNode* leftFind = BinaryTreeFind(root->left, x);
	if (leftFind)
	{
		return leftFind;
	}
	BTNode* rightFind = BinaryTreeFind(root->right, x);
	if (rightFind)
	{
		return rightFind;
	}
		return NULL;
}

// 二叉树销毁(后序遍历)
void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}
	BinaryTreeDestory(&((*root)->left));
	BinaryTreeDestory(&((*root)->right));
	free(*root);
	*root = NULL;
}

test.c：

#define  _CRT_SECURE_NO_WARNINGS  1
#include"Tree.h"

BTNode* buyNode(char x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if ( x == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->left = newnode->right = NULL;

	return newnode;
}

BTNode* creatTree()
{
	BTNode* nodeA = buyNode('A');
	BTNode* nodeB = buyNode('B');
	BTNode* nodeC = buyNode('C');
	BTNode* nodeD = buyNode('D');
	BTNode* nodeE = buyNode('E');
	BTNode* nodeF = buyNode('F');

	nodeA->left = nodeB;
	nodeA->right = nodeC;
	nodeB->left = nodeD;
	nodeC->left = nodeE;
	nodeC->right = nodeF;

	return nodeA;
}

void test01()
{
	BTNode* root = creatTree();
	//PerOrder(root);
	//InOrder(root);
	/*PostOrder(root);*/

	//既然返回的是void，就不能再打印了
	//printf("size:%d\n", BinaryTreeSize(root));
	//printf("size:%d\n", BinaryTreeSize(root));
	//int Treesize = 0;
	//BinaryTreeSize(root, &Treesize);
	//printf("size:%d\n", Treesize);

	//Treesize = 0;
	//BinaryTreeSize(root, &Treesize);
	//printf("size:%d\n", Treesize);
	printf("size:%d\n", BinaryTreeSize(root));
	printf("leaf size:%d\n", BinaryTreeLeafSize(root));
	printf("K level size:%d\n", BinaryTreeLevelKSize(root,3));
	printf("Tree Depth:%d\n", BinaryTreeDepth(root));
	BTNode* find = BinaryTreeFind(root, 'H');
	if (find)
	{
		printf("找到了!\n");
	}
	else
	{
		printf("未找到!\n");
	}
	BinaryTreeDestory(&root);
}

int main()
{
	test01();
	return 0;
}

（四）层序遍历的实现

1、思路

前面我们介绍前中后序遍历的时候就提到了层序遍历：

因此实现层序遍历需要额外借助数据结构：队列。

2、思考过程

像前序、中序、后序遍历我们称之为深度优先遍历；像层序遍历这种遍历我们称之为广度优先遍历。

这里我们就不能用递归来实现，如果我们用节点（指针）往下去找，用递归往上回溯。

如果我用这种方法，我打印A之后来到它的左孩子B，打印完之后向往上回，指针可以回吗？不能，你只能递归，但是递归一定是深度优先遍历，所以它一定会走到底，不会说像B这样，走到一半就往上走的，所以这里递归是无法实现层序遍历的。

我们要借助数据结构——队列，来实现层序遍历——

注意：这里我们插入的不是一个A的字符(一个值)，而是一个节点。因为把节点存到队列里面不影响节点里面的三个成员：保存的值A以及left和right指针；但是如果你存的是A，就找不到它的左右孩子，这个A是一个字符，所以存的一定要是节点。

将根节点保存在队列中，是队列不为空，循环判断队列是否为空，不为空取队头，将队头不为空的孩子节点入队列

之前我们就已经实现过队列的结构以及各种方法了，这里我们直接【添加】-->【现有项】。

这里Queue.h的结构体类型要更改一下——

这里不用管找不找得到，有友友可能觉得这里不包含上不是会找不到吗？下图中我们包含了头文件，但是，头文件嵌套，代码就要报错了。

前置声明————不需要定义，就相当于下面的void QueueInit(Queue* pq);这些方法一样：

我们在这里是一个声明的作用——

这个struct必须要有，因为它的作用就是告诉编译器：这是个结构体，如果不加，编译器就不知道这里的BinaryTreeNode是个啥了。

满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

层序遍历代码：

Tree.c：

//层序遍历————借助数据结构：队列
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		//取队头
		BTNode* top = QueueFront(&q);
		printf("%c ", top->data);
		QueuePop(&q);
		//队头节点不为空的孩子节点入队列
		if (top->left)
			QueuePush(&q, top->left);
		if(top->right)
			QueuePush(&q, top->right);
	}

	QueueDestory(&q);
}

3、层序遍历实现的完整代码

头文件：

（1）Queue.h：

（2）Tree.h：

源文件：

（3）Queue.c：

（4）Tree.c：

（5）test.c：

运行一下——

（五）判断是否为完全二叉树

1、思路

完全二叉树性质回顾：

1、最后一个结点个数不一定达到最大； 2、其他每层结点个数都达到最大(2个)； 3、节点从左到右依次排列。

我们根据这几条性质，可以得出两个判断依据：

（1）判断每层节点个数；（2）叶子结点是否从左到右依次排列。

2、解决过程

非完全二叉树：

取到空的队头，跳出循环，此时队列只剩下了空节点和非空节点。

完全二叉树：

取到空的队头，跳出循环，此时队列中剩下了空节点。

只要取到空，就跳出循环，看此时队列中剩下什么，如果只剩下空节点和非空节点，就是非完全二叉树，如果队列中剩下了空节点，就是完全二叉树。

3、代码演示

Tree.c：

//判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	//头节点入队列
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		//取队头，出队头
		BTNode* top = QueueFront(&q);
		QueuePop(&q);
		if (top == NULL)
		{
			//top取到空就直接出队列
			break;
		}
		//将队头节点的左右孩子入队列
		QueuePush(&q, top->left);
		QueuePush(&q, top->right);
	}
	//队列不为空，继续取队列中的队头
	while (!QueueEmpty(&q))
	{
		BTNode* top = QueueFront(&q);
		QueuePop(&q);
		if (top != NULL)
		{
			//不是完全二叉树
			QueueDestory(&q);
			return false;
		}
	}
	QueueDestory(&q);
	return true;
}

4、构造完全二叉树

（六）二叉树链式结构实现的完整代码

代码如下，每个接口博主都测试过了，可作为参考：

头文件：

（1）Queue.h：

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

//typedef int QDataType;
//int更改为二叉树节点结构
//前置声明————不需要定义，就相当于下面的void QueueInit(Queue* pq);这些方法一样
typedef struct BinaryTreeNode* QDataType;

//定义节点的结构
 typedef struct QueueNode 
{
	QDataType data;
	struct QueueNode* next;
}QueueNode;

 //定义队列的结构
typedef struct Queue 
{
	QueueNode* phead;//指向队头节点的指针
	QueueNode* ptail;//指向队尾节点的指针
	int size;		   //队列中有效数据个数
}Queue;

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

//销毁
void QueueDestory(Queue* pq);

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

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

//队列判空
bool QueueEmpty(Queue* pq);

//取队头数据
QDataType QueueFront(Queue* pq);

//取队尾数据
QDataType QueueBack(Queue* pq);

//队列有效元素个数
int QueueSize(Queue* pq);

（2）Tree.h：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

typedef char BTDataType;
//定义二叉树节点结构
typedef struct BinaryTreeNode
{
	BTDataType data; // 当前结点值域
	struct BinTreeNode* left; // 指向当前结点左孩子
	struct BinTreeNode* right; // 指向当前结点右孩子 
}BTNode;

//前序遍历
void PerOrder(BTNode* root);

//中序遍历
void InOrder(BTNode* root);

//后序遍历
void PostOrder(BTNode* root);

//二叉树结点个数 
int BinaryTreeSize(BTNode* root);
//void BinaryTreeSize(BTNode* root, int* psize);

//二叉树叶子结点个数 
int BinaryTreeLeafSize(BTNode* root);

//二叉树第k层结点个数 
int BinaryTreeLevelKSize(BTNode* root, int k);

//二叉树的深度/高度
int BinaryTreeDepth(BTNode* root);

//二叉树查找值为x的结点 
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);

// 二叉树销毁
void BinaryTreeDestory(BTNode** root);

//层序遍历————借助数据结构：队列
void LevelOrder(BTNode* root);

//判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);

源文件：

（3）Queue.c：

#define  _CRT_SECURE_NO_WARNINGS  1

#include"Queue.h"

//初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

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

	QueueNode* pcur = pq->phead;
	while(pcur)
	{
		QueueNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pq->phead = pq->ptail = NULL;//防止phead、ptail变野指针
	pq->size = 0;//销毁后元素个数重置为0
}

//入队列,队尾
void QueuePush(Queue* pq, QDataType x)
{
	int size = 0;
	assert(pq);
	//创建值为x的节点
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
	//队列为空
	if (pq->phead == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = pq->ptail->next;
	}
	pq->size++;//入队后元素个数+1
}

//队列判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead == NULL;
}

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

	//队列中只有一个节点
	if (pq->phead == pq->ptail)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else 
	{
		QueueNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
	pq->size--;//出队后元素个数-1
}

//取队头数据
QDataType QueueFront(Queue* pq)
{ 
	assert(!QueueEmpty(pq));
	return pq->phead->data;
}

//取队尾数据
QDataType QueueBack(Queue* pq)
{
	assert(!QueueEmpty(pq));
	return pq->ptail->data;
}

//队列有效元素个数
int QueueSize(Queue* pq)
{
	/*assert(pq);
	QueueNode* pcur = pq->phead;
	int size = 0;
	while (pcur)
	{
		++size;
		pcur = pcur->next;
	}
	return size;*/
	return pq->size;
}

（4）Tree.c：

#define  _CRT_SECURE_NO_WARNINGS  1
#include"Tree.h"
#include"Queue.h"

//前序遍历————口诀：根左右
void PerOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->data);
	PerOrder(root->left);
	PerOrder(root->right);
}

//中序遍历——左根右
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	InOrder(root->left);
	printf("%c ", root->data);
	InOrder(root->right);
}

//后序遍历——左右根
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%c ", root->data);
}

////错误：创建全局变量，多次调用方法会出现累加的情况
//int size = 0;
////二叉树结点个数 
//int BinaryTreeSize(BTNode* root)
//{
//	if (root == NULL)
//	{
//		return 0;
//	}
//	size++;
//	BinaryTreeSize(root->left);
//	BinaryTreeSize(root->right);
//
//	return size;
//}

//方法二：需要改造函数定义
////二叉树结点个数
//void BinaryTreeSize(BTNode* root, int* psize)
//{
//	if (root == NULL)
//	{
//		return 0;
//	}
//	(*psize)++;
//	BinaryTreeSize(root->left,psize);
//	BinaryTreeSize(root->right,psize);
//}

//二叉树结点个数 = 1 + 左子树结点个数 + 右子树结点个数 
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return 1 + BinaryTreeSize(root->left) 
		+ BinaryTreeSize(root->right);
}

//二叉树叶子结点个数 
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)
{
	if (root == NULL)
	{
		return 0;
	}
	//判断是否为第K层
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->left, k - 1) 
		+ BinaryTreeLevelKSize(root->right, k - 1);
}

//二叉树的深度/高度
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftDep = BinaryTreeDepth(root->left);
	int rightDep = BinaryTreeDepth(root->right);
	//根节点+max(左子树高度，右子树高度)
	return 1 + (leftDep > rightDep ? leftDep : rightDep);
	//return 1 + (BinaryTreeDepth(root->left) > BinaryTreeDepth(root->right) ?
	//	BinaryTreeDepth(root->left) : BinaryTreeDepth(root->right);
}

//二叉树查找值为x的结点 
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	BTNode* leftFind = BinaryTreeFind(root->left, x);
	if (leftFind)
	{
		return leftFind;
	}
	BTNode* rightFind = BinaryTreeFind(root->right, x);
	if (rightFind)
	{
		return rightFind;
	}
	return NULL;
}

// 二叉树销毁(后序遍历)
void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}
	BinaryTreeDestory(&((*root)->left));
	BinaryTreeDestory(&((*root)->right));
	free(*root);
	*root = NULL;
}

//层序遍历————借助数据结构：队列
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		//取队头，打印队头
		BTNode* top = QueueFront(&q);
		printf("%c ", top->data);
		QueuePop(&q);
		//队头节点不为空的孩子节点入队列
		if (top->left)
			QueuePush(&q, top->left);
		if(top->right)
			QueuePush(&q, top->right);
	}

	QueueDestory(&q);
}

//判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	//头节点入队列
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		//取队头，出队头
		BTNode* top = QueueFront(&q);
		QueuePop(&q);
		if (top == NULL)
		{
			//top取到空就直接出队列
			break;
		}
		//将队头节点的左右孩子入队列
		QueuePush(&q, top->left);
		QueuePush(&q, top->right);
	}
	//队列不为空，继续取队列中的队头
	while (!QueueEmpty(&q))
	{
		BTNode* top = QueueFront(&q);
		QueuePop(&q);
		if (top != NULL)
		{
			//不是完全二叉树
			QueueDestory(&q);
			return false;
		}
	}
	QueueDestory(&q);
	return true;
}

（5）test.c：

#define  _CRT_SECURE_NO_WARNINGS  1
#include"Tree.h"

BTNode* buyNode(char x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (x == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->left = newnode->right = NULL;

	return newnode;
}

BTNode* creatTree()
{
	BTNode* nodeA = buyNode('A');
	BTNode* nodeB = buyNode('B');
	BTNode* nodeC = buyNode('C');
	BTNode* nodeD = buyNode('D');
	BTNode* nodeE = buyNode('E');
	BTNode* nodeF = buyNode('F');

	nodeA->left = nodeB;
	nodeA->right = nodeC;
	nodeB->left = nodeD;
	nodeC->left = nodeE;
	nodeC->right = nodeF;
	//nodeB->right = nodeE;
	//nodeC->left = nodeF;

	return nodeA;
}

void test01()
{
	BTNode* root = creatTree();
	//PerOrder(root);
	//InOrder(root);
	/*PostOrder(root);*/

	//既然返回的是void，就不能再打印了
	//printf("size:%d\n", BinaryTreeSize(root));
	//printf("size:%d\n", BinaryTreeSize(root));
	//int Treesize = 0;
	//BinaryTreeSize(root, &Treesize);
	//printf("size:%d\n", Treesize);

	//Treesize = 0;
	//BinaryTreeSize(root, &Treesize);
	//printf("size:%d\n", Treesize);
	printf("size:%d\n", BinaryTreeSize(root));
	printf("leaf size:%d\n", BinaryTreeLeafSize(root));
	printf("K level size:%d\n", BinaryTreeLevelKSize(root, 1));
	printf("Tree Depth:%d\n", BinaryTreeDepth(root));
	BTNode* find = BinaryTreeFind(root, 'H');
	if (find)
	{
		printf("找到了!\n");
	}
	else
	{
		printf("未找到!\n");
	}

	//层序遍历
	printf("层序遍历的结果: ");
	LevelOrder(root);
	printf("\n");
	////层序遍历
	//printf("层序遍历的结果: ", LeveOrder(&root));
	bool isComplete = BinaryTreeComplete(root);
	if (isComplete)
	{
		printf("是完全二叉树！\n");
	}
	else
	{
		printf("不是完全二叉树！\n");
	}

	BinaryTreeDestory(&root);
}

int main()
{
	test01();
	return 0;
}

到这里，链式结构我们全部就实现完了。

结尾

至此，【数据结构】初级阶段的二叉树的主线内容我们已经全部介绍完了！

往期回顾：

函数栈帧的创建与销毁相关博客的链接，博主都已经放在正文前面了，有需要的友友自取。

【数据结构与算法】数据结构初阶：详解二叉树（四）——链式结构二叉树（上）：前中后序遍历、创建一棵链式二叉树

【数据结构与算法】数据结构初阶：详解二叉树（三）——堆（续）：向上向下调整算法的证明及时间复杂度、TOP-K问题详解

【数据结构与算法】数据结构初阶：详解二叉树（二）——堆

【数据结构与算法】数据结构初阶：详解二叉树（一）

本期内容需要回顾的C语言知识如下面的截图中所示（指针博主写了6篇，列出来有水字数嫌疑了，就只放指针第六篇的网址，博主在指针（六）把指针部分的前五篇的网址都放在【往期回顾】了，点击【传送门】就可以看了）。大家如果对前面部分的知识点印象不深，可以去上一篇文章的结尾部分看看，博主把需要回顾的知识点相关的博客的链接都放在上一篇文章了，上一篇文章的链接博主放在下面了：

【数据结构与算法】数据结构初阶：详解顺序表和链表（三）——单链表（上）

结语：本篇文章到这里就结束了，对数据结构的二叉树知识感兴趣的友友们可以在评论区留言，博主创作时可能存在笔误，或者知识点不严谨的地方，大家多担待，如果大家在阅读的时候发现了行文有什么错误欢迎在评论区斧正，再次感谢友友们的关注和支持！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-07-24，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度