数据结构：二叉树的链式结构及相关算法详解

一.链式结构的实现

1.二叉树结点基本结构，初始化与销毁：

二.链式结构二叉树的几种遍历算法

1.几种算法的简单区分：

2.前序遍历：

3.中序遍历：

4.后序遍历：

5.层序遍历（广度优先遍历BFS）：

三.链式二叉树的几种使用

1.计算树的结点个数：

2.计算树的叶子结点个数：

3.计算树的第k层结点个数：

4.计算树的深度：

5.查找结点为X的结点：

6.判断二叉树是否为完全二叉树：

一.链式结构的实现

1.二叉树结点基本结构，初始化与销毁：

（1）⽤链表来表示⼀棵⼆叉树，即⽤链来指示元素的逻辑关系。通常的⽅法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别⽤来给出该结点左孩子和右孩子所在的链结点的存储地址，其结构如下：

（2）二叉树结点的初始化与树的创建：
#include"Tree.h"
//结点的初始化
BTNode* buyNode(char x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	node->data = x;
	node->left = node->right = NULL;

	return node;
}
//树结构的创建
BTNode* creatBinaryTree()
{
	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->right = nodeE;
	nodeC->right = nodeF;
}
（3）链式二叉树的销毁：

（使用后序遍历，我在下文会写出具体操作）
void BinaryTreeDestory(BTNode** root)
{
	//这里因为要改变根节点，应该传入的是根节点的地址，所以得拿二级指针接收
	//递归出口
	if ((*root) == NULL)
	{
		return;
	}
	//自叶向根方向的释放
	//如果先释放的话，就找不到叶子节点了
	BinaryTreeDestory(&((*root)->left));
	BinaryTreeDestory(&((*root)->right));
	free(*root);
	*root = NULL;
}

二.链式结构二叉树的几种遍历算法

1.几种算法的简单区分：

举一个普遍的例子具体说明一下，如图：

2.前序遍历：

简单说明一下前序遍历的基本逻辑：

假设一个树：

A
/ \
B C
/ \
D E

那么其遍历过程为：
访问根节点 A 。
递归遍历左子树（以 B  为根）：
访问 B
递归遍历左子树（以 D  为根）：
访问 D
递归遍历右子树（以 E  为根）：
访问 E
递归遍历右子树（以 C  为根）：
访问 C

//前序遍历
void preOrder(BTNode* root)
{
	//头 左 右
	//递归出口
	if (root == NULL)
	{
		printf("NULL");
		return;
	}
	printf("%c",root->data);
	preOrder(root->left);
	preOrder(root->right);
}

3.中序遍历：

void inOrder(BTNode* root)
{
	//左 头 右
	//递归出口
	if (root == NULL)
	{
		printf("NULL");
		return;
	}
	inOrder(root->left); //注意别调用错了，调用中序的
	printf("%c", root->data);
	inOrder(root->right);
}

4.后序遍历：

void postOrder(BTNode* root)
{
	//递归出口
	if (root == NULL)
	{
		printf("NULL");
		return;
	}
	postOrder(root->left);
	postOrder(root->right);
	printf("%c", root->data);
}

总结：如上述所示，前中后序遍历的代码共同点也是相当明显了，主要就是递归顺序左右子树的顺序不同而影响的代码输出顺序不同，其根本上来说就是函数栈帧的不断进行嵌套式的创建与销毁，如果挨个遍历可能会显得比较复杂，但通过代码所示的这种递归算法，前中后序的遍历实现也显得十分简洁明了

但还有一点尤其需要注意：就是不同于层序遍历，我上面所说的三种遍历都属于深度优先遍历（DFS），而层序遍历却属于广度优先遍历，关于这两大类遍历的优劣我会在实现层序遍历后作详细介绍

5.层序遍历（广度优先遍历BFS）：

思路：

借助数据结构：队列，先通过根节点入队列，再循环判断队列是否为空，不为空则取队头然后出队头，并将队头结点的左右孩子入队列

(由于后续层序遍历的实现需要用到好些队列的知识，所有我先将队列的一些简单用法附在下面，需要的可以稍微看看)

//定义结点结构
typedef int QDataTpe;
typedef struct QueueNode
{
	struct QueneNode* next;
	QDataTpe data;
}QueueNode;



//定义队列的结构
typedef struct Queue
{
	QueueNode* phead;//队头
	QueueNode* ptail;//队尾
	int size;
}Queue;

BTNode* buyNode(char x);



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

//入队（从队尾入）
void QueuePush(Queue* pq, QDataTpe x)
{
	assert(pq);
	//申请一个结点
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc failed");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
	//队列为空，newnode是对头也是队尾
	if (pq->phead == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else //队列非空，尾插
	{
		pq->ptail->next = newnode;
		pq->ptail = pq->ptail->next;
	}
	pq->size++;
}
//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead == 0;
}

//出队（从队头出）
void QueuePop(Queue* pq)
{
	assert(!QueueEmpty(pq));
	//只有一个结点的情况下，要把队尾和队头的两个指针都考虑到
	if (pq->phead == pq->ptail)
	{
		free(pq->ptail);
		pq->phead = pq->ptail = NULL;
	}
	QueueNode* next = pq->phead->next;
	free(pq->phead);
	pq->phead = next;  
	pq->size--;
}

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

//队列的销毁
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;
}

//取队列元素个数
int QueueSize(Queue* pq)
{
	return pq->size;
}

//层序遍历
void LeveIOrder(BTNode* root)
{
	Queue q;//创建一个队列
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		//取队头出队头，打印结点值
		BTNode* top = QueueFront(&q);
		QueuePop(&q);
		printf("%c", top->data);
		//将队头结点的非空左右孩子结点入队列
		if (top->left)
		{
			QueuePush(&q, top->left);
		}
		if (top->right)
		{
			QueuePush(&q, top->right);
		}
		QueuDestroy(&q);
	}

}

小结：
DFS 优点（深度优先遍历）
节点少时效率高，节省内存
适合需要“全探索”或“找到任意解即可”的场景（如迷宫路径）

DFS 缺点
可能陷入无限循环（需记录已访问节点）
不保证最短路径（除非剪枝优化）

BFS 优点（广度优先遍历）
保证找到最短路径（无权图中）
层级分明，易于理解

BFS 缺点
内存占用大（需存储整个层级节点）
不适合大规模数据或深层结构（如树深度极大）