C语言详解实现链式二叉树的遍历与相关接口

目录

• 前言
• 一、二叉树的链式结构
• 二、二叉树的遍历方式
• 1.1 遍历方式的规则
• 1.2 前序遍历
• 1.3 中序遍历
• 1.4 后序遍历
• 1.5 层序遍历
• 三、二叉树的相关接口实现
• 3.1 二叉树节点个数
• 3.2 二叉树叶子节点个数
• 3.3 二叉树第 k 层节点个数
• 3.4 二叉树的深度(高度)
• 3.5 二叉树查找值为 x 的节点
• 3.6 总结 & 注意
• 四、二叉树的创建和销毁
• 4.1 通过前序遍历的字符串来构建二叉树
• 4.2 二叉树销毁
• 4.3 判断二叉树是否是完全二叉树

前言

二叉树的顺序结构就是用数组来存储，而「数组」一般只适合表示「满二叉树」或「完全二叉树」，因为不是完全二叉树会有「空间的浪费」。

普通二叉树的增删查改没有意义，主要学习它的结构，要加上搜索树的规则，才有价值。

一、二叉树的链式结构

在学习二叉树的基本操作前，需先要创建一棵二叉树，此处我们手动快速创建一棵简单的二叉树，快速进入二叉树操作学习，等二叉树结构了解的差不多时，我们反过头再来研究二叉树真正的创建方式。

#include<stdio.h>  // perror, printf
#include<stdlib.h> // malloc
typedef char BTDataType;
// 定义二叉树的节点
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;
// 动态申请一个新节点
BTNode* BuyNode(BTDataType x)
{
	//
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	newnode->data = x;
	newnode->left = newnode->right = NULL;
	return newnode;
}
// 二叉树的链式结构
BTNode* CreatBinaryTree()
{
	// 创建多个节点
	BTNode* node_A = BuyNode('A');
	BTNode* node_B = BuyNode('B');
	BTNode* node_C = BuyNode('C');
	BTNode* node_D = BuyNode('D');
	BTNode* node_E = BuyNode('E');
	BTNode* node_F = BuyNode('F');
	// 用链来指示节点间的逻辑关系
	node_A->left = node_B;
	node_A->right = node_C;
	node_B->left = node_D;
	node_C->left = node_E;
	node_C->right = node_F;
	return node_A;
}

注意：上述代码并不是创建二叉树的方式，真正创建二叉树方式后续讲解。

二、二叉树的遍历方式

1.1 遍历方式的规则

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

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历 和 层序遍历：

• 前序遍历(Preorder Traversal) ：访问根结点的操作发生在遍历其左右子树之前。

根 --> 左子树 --> 右子树

（比如上图中，访问的路径为：A B D NULL NULL NULL C E NULL NULL F NULL NULL）

• 中序遍历(Inorder Traversal) ：访问根结点的操作发生在遍历其左右子树之中（间）。

左子树 --> 根 --> 右子树

（比如上图中，访问的路径为：NULL D NULL B NULL A NULL E NULL C NULL F NULL）

计算中序遍历访问路径可以用简单直观的投影法：

• 后序遍历(Postorder Traversal)：访问根结点的操作发生在遍历其左右子树之后。

左子树 --> 右子树 --> 根

（比如上图中，访问的路径为：NULL NULL D NULL B NULL NULL E NULL NULL F C A）

• 层序遍历(LevelOrder traversal)：一层一层的走

（比如上图中，访问的路径为：A B C D NULL E F NULL NULL NULL NULL NULL NULL）

由于被访问的结点必是「某子树的根」，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

深度优先遍历：前序、中序、后序

广度优先遍历：层序

【理解前/中/后序遍历的思路】

前中后序遍历中，每一颗子树都会被分为（根、左子树、右子树）三部分来看待，分而治之。

举个栗子：

校长想要统计全校学生的人数，他并不会自己挨个挨个去数，而是把每个年级的负责人叫过来，各年级负责人又把各班的班主任叫过来，各班主任又把各班班长叫过来，班长统计人数后，大家把结果再层层上报，最终传回到校长这里，就知道学校总人数了。

1.2 前序遍历

代码是非常简单的：

// 二叉树前序遍历
void PreOrder(BTNode* root)
{
	if (root) // 先判断树是否为空
	{
		// 根 --> 左子树 --> 右子树
		printf("%c ", root->data);
		PreOrder(root->left);
		PreOrder(root->right);
	}
}
int main()
{
	// 创建一颗链式二叉树
	BTNode* root = CreatBinaryTree();
	// 前序遍历
	PreOrder(root); // A B D C E F
    return 0;
}

前序遍历函数递归调用图解：每个函数调用，都会建立一个自己的栈帧。

前序遍历递归图解：

1.3 中序遍历

// 二叉树中序遍历
void InOrder(BTNode* root)
{
	if (root) // 先判断树是否为空
	{
		// 左子树 --> 根 --> 右子树
		InOrder(root->left);
		printf("%c ", root->data);
		InOrder(root->right);
	}
}

1.4 后序遍历

// 二叉树后序遍历
void PostOrder(BTNode* root)
{
	if (root) // 先判断树是否为空
	{
		// 左子树 --> 右子树 --> 根
		PostOrder(root->left);
		PostOrder(root->right);
		printf("%c ", root->data);
	}
}

1.5 层序遍历

层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

核心思路：

用一个队列来进行层序遍历：

• 先入第一层的节点（根节点）
• 上一层出来后，再入下一层（即它的左右孩子节点）

比如：

先入根节点 A

根节点 A 出来后，再入它的孩子节点 B 和 C

节点 B 出来后，再入它的孩子节点 D 和 E，节点 C 出来后，再入它的孩子节点 F ……

// 二叉树的层序遍历
void LevelOrder(BTNode* root)
{
	LinkQueue q; // 链式队列
	QueueInit(&q); // 初始化队列
	// 树的根节点root不为空，把根节点入队
	if (root)
	{
		QueuePush(&q, root);
	}
    // 当队列不为空时，不断的出队，以及入队根节点root的左右子树
	while (!QueueEmpty(&q))
	{
		// 当前树的根节点出队
		BTNode* front = QueueFront(&q); // 获取队头元素
		printf("%c ", front->data);     // 打印节点值
		QueuePop(&q);                   // 出队
		// 如果当前树根的左右孩子不为空，则分别入队
		if (front->left)
		{
			QueuePush(&q, front->left);
		}
		if (front->right)
		{
			QueuePush(&q, front->right);
		}
	}
	printf("\n");
	QueueDestroy(&q); // 销毁队列
}

三、二叉树的相关接口实现

3.1 二叉树节点个数

// 二叉树节点个数
/* 方法一：
1、递归遍历 -- 用全局变量/静态局部变量来记录节点个数
2、递归遍历 -- 函数外定义一个局部变量记录节点个数，传址给函数
*/
// 方法二：分而治之的思路
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL) // 1. 先判断当前访问的节点是否为空
	{
		return 0;
	}
	// 2. 当前节点不为空，节点个数累+1，则继续访问其左右子树
	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

3.2 二叉树叶子节点个数

// 二叉树叶子节点个数
/* 方法一：
1、递归遍历 -- 用全局变量/静态局部变量来记录节点个数
2、递归遍历 -- 函数外定义一个局部变量记录节点个数，传址给函数
*/
// 方法二：分而治之的思路
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL) // 1. 先判断当前访问的节点是否为空
	{
		return 0;
	}
	// 2. 当前节点不为空，它的左右孩子都为空，说明该节点是叶子节点
    if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	// 3. 当前节点不为空，左右孩子不都为空，则继续往下遍历
	return BinaryTreeLeafSize(root->left)
		+ BinaryTreeLeafSize(root->right);
}

3.3 二叉树第 k 层节点个数

核心思路：

• 求当前树第 k 层的节点个数 = 求左子树第 k-1 层的节点个数 + 求右子树第 k-1 层的节点个数
• 比如：
• 求当前树（A）第 2 层的节点个数
• = 求左子树（B）第 1 层的节点个数 + 求右子树（C）第 1 层的节点个数
• = 1 + 1
• = 2

如何知道这个节点是不是第 k 层的？我自己复习时是用的这个思路来写，感觉容易理解些：

求二叉树第 k 层的节点个数，我们从根节点开始往下遍历（我在代码中是根左右的顺序），每遍历一次 k 减 1一次，当 k == 1 时，说明我们遍历到了第 k 层，我们此时访问该层的节点，如果它不为空，则二叉树第 k 层的节点个数就要+1。

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL) // 1. 先判断当前访问的节点是否为空
	{
		return 0;
	}
	if (k == 1) // 2. 当前节点不为空，而k已经减到1了，说明遍历到了第k层，说明该节点是第k层的
	{
		return 1;
	}
	// 3. 还没有遍历到第k层，我们就继续往下遍历
	return BinaryTreeLevelKSize(root->left, k - 1)
		+ BinaryTreeLevelKSize(root->right, k - 1);
}

3.4 二叉树的深度(高度)

核心思想：

当前树的深度 = Max(左子树的深度，右子树的深度) + 1

• root 是空节点：height ( root ) = 0
• root 是非空节点：height ( root ) = max ( height ( root->left ), height ( root->right ) ) + 1

// 二叉树的深度(高度)
int BinaryTreeDepth(BTNode* root)
{
    // 1. 先判断当前树的根节点是否为空
	if (root == NULL)
	{
		return 0;
	}
	// 2. 当前树的根节点不为空，分别计算其左右子树的深度
	int leftDepth = BinaryTreeDepth(root->left);
	int rightDepth = BinaryTreeDepth(root->right);
	// 3. 比较当前树左右子树的深度，最大的那个+1 就是当前树的深度
	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

有一道OJ题考到了该算法，链接如下：二叉树的最大深度

3.5 二叉树查找值为 x 的节点

核心思路：

先判断是不是当前节点，是就返回，不是就先去该节点的左子树找，找到了就返回，左子树没找到，再去该节点的右子树找。

// 二叉树查找值为x的节点，若有则返回该节点的地址，若没有则返回NULL
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL) // 1. 先判断当前访问的节点是否为空
	{
		return NULL;
	}
	if (root->data == x) // 2. 判断要找的x值节点是不是当前节点
	{
		return root;
	}
	// 3. 不是当前节点，则继续去该节点的左子树中找
	BTNode* ret = BinaryTreeFind(root->left, x);
	if (ret != NULL)
	{
		return ret; // 找到了返回地址
	}
	// 3. 还没找到，再继续去该节点的右子树中找
	ret = BinaryTreeFind(root->right, x);
	if (ret != NULL)
	{
		return ret; // 找到了返回地址
	}
	// 4. 当前节点及其左右子树中都没找到，返回NULL
	return NULL;
}

3.6 总结 & 注意

二叉树相关的算法，如果用的是递归遍历，且代码中需要一个变量在整个递归过程中去记录什么信息，一定要注意，不要把这个变量直接定义成了局部变量。（因为每次递归调用，都会建立一个栈帧，各栈帧中的局部变量是彼此独立的）

所以需要下面这样做：

1、递归遍历 – 用全局变量/静态局部变量来记录节点个数

2、递归遍历 – 函数外定义一个局部变量记录节点个数，传址给函数

四、二叉树的创建和销毁

4.1 通过前序遍历的字符串来构建二叉树

// 通过前序遍历的字符串数组arr "ABD##E#H##CF##G##" 构建二叉树
BTNode* BinaryTreeCreate(BTDataType* arr, int size, int* pi);

4.2 二叉树销毁

// 二叉树销毁
// 一级指针(头节点指针)，形参是实参的一份拷贝，函数内改变形参的值，无法改变外部实参的值
// 所以我们需要在函数外置头节点指针为NULL
void BinaryTreeDestroy(BTNode* root)
{
	// 不建议使用前中序遍历销毁，如果节点先被销毁，就变成随机值了，不知道它的左右子树位置了
	// 所以我们采用后序遍历销毁
	if (root)
	{
		BinaryTreeDestroy(root->left);
		BinaryTreeDestroy(root->right);
		free(root);
	}
}
int main()
{
	// 创建一颗链式二叉树
	BTNode* root = CreatBinaryTree();
	// 销毁二叉树
    BinaryTreeDestroy(root);
	// 头节点指针置NULL
    root = NULL;
	return 0;
}

4.3 判断二叉树是否是完全二叉树

核心思路：

层序遍历时，把空节点也入队列

• 完全二叉树，「非空节点」是连续的，则「空节点」是连续的。
• 非完全二叉树，「非空节点」不是连续的，则「空节点」不是连续的。

所以在出队时，判断一下，出到第一个「空节点」时，跳出循环；

在下面重新写一个循环继续出队，并检查出队元素：

• 如果「第一个空节点」后面的全是「空节点」，说明是完全二叉树
• 如果「第一个空节点」后面的有「非空节点」，说明是非完全二叉树

// 判断二叉树是否是完全二叉树（利用层序遍历的思想来判断）
bool BinaryTreeComplete(BTNode* root)
{
	LinkQueue q; // 链式队列
	QueueInit(&q); // 初始化队列
	// 树的根节点root不为空，把根节点入队
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		// 当前树的根节点出队
		BTNode* front = QueueFront(&q); // 获取队头元素
		QueuePop(&q);                   // 出队
		// @@@ 出队的节点中，出到第一个空节点时，跳出循环 @@@
		if (front == NULL)
		{
			break;
		}
		// 不管当前树根的左右孩子是否为空，都分别入队
		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}
	// @@@ 出队的节点中，出到第一个空节点时，跳出上面循环 @@@
	// 在这里继续出队：
	// 1、如果队列中全是空节点，则是完全二叉树
	// 2、如果队列中有非空节点，则是非完全二叉树
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q); // 获取队头元素
		QueuePop(&q);                   // 出队
		// @@@ 出队的节点中，如果出现非空节点，说明是非完全二叉树 @@@
		if (front)
		{
			QueueDestroy(&q); // 销毁队列
			return false;
		}
	}
	QueueDestroy(&q); // 销毁队列
	// @@@ 出队的节点中，如果没有出现非空节点，说明是完全二叉树 @@@
	return true;
}

到此这篇关于C语言详解实现链式二叉树的遍历与相关接口的文章就介绍到这了,更多相关C语言链式二叉树遍历内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！