【数据结构】二叉树链式结构的实现

用户11290673

发布于 2024-09-25 12:44:41

470

发布于 2024-09-25 12:44:41

文章被收录于专栏：学习

前言上篇博客我们说了有关二叉树顺序结构——堆，堆是完全二叉树，但我们对于普通的二叉树（不一定为完全二叉树），我们该用什么结构实现那，本篇就来详细说一下，二叉树另一个实现的结构，链式结构 💓 个人主页：小张同学zkf ⏩ 文章专栏：数据结构若有问题评论区见📝 🎉欢迎大家点赞👍收藏⭐文章

1.二叉树的创建与遍历

1.1 前序，中序，后序遍历

看这个题之前，我们先来说一下三个遍历

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

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

1. 前序遍历 (Preorder Traversal 亦称先序遍历 )—— 访问根结点的操作发生在遍历其左右子树之前。

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

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

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

前序遍历递归图解 ：

对上图，遍历结果如下 前序遍历结果： 1 2 3 4 5 6 中序遍历结果： 3 2 1 5 4 6 后序遍历结果： 3 2 5 6 4 1

那了解了三个遍历，那对应的代码如何实现那？

我们可以用递归来解决

假如，传入函数的节点是空那就直接返回，若不为空，打印当前数值，把对应的左孩子与右孩子分别传进去，子节点与其父亲节点处理问题思路相同，符合把大事化小原则，是递归思想，那前中后序代码，其实就是打印与递归顺序不同，前序就是先打印再递归左孩子，最后递归右孩子，而中序就是先递归左孩子，再打印，再递归右孩子，后序就是先递归左孩子，再递归右孩子，最后打印

代码如下

void BinaryTreePrevOrder(BTNode* root)//前序遍历
{
	if (root == NULL)
	{
		return 0;
	}
	printf("%c ", root->_data);
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
}
void BinaryTreeInOrder(BTNode* root)//中序遍历
{
	if (root == NULL)
	{
		return 0;
	}
	BinaryTreePrevOrder(root->_left);
	printf("%c ", root->_data);
	BinaryTreePrevOrder(root->_right);
}
void BinaryTreePostOrder(BTNode* root)//后序遍历
{
	if (root == NULL)
	{
		return 0;
	}
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
	printf("%c ", root->_data);
}

1.2层序遍历

还有一种遍历是层序遍历

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

那么层序遍历的代码如何实现

这里我们需要用到我们之前学到的队列，我们可以将一个根节点打入队列，再让他出队列，出队列的节点打印，出队列同时，将他的左右子树再打入队列，前提左右孩子节点不为空，继续上述的操作，直到队列为空时循环停止。

代码如下

void BinaryTreeLevelOrder(BTNode* root)//层序遍历
{
	Queue as;
	QueueInit(&as);
	QueuePush(&as, root);
	while (!QueueEmpty(&as))
	{
		BTNode* aq = QueueFront(&as);
		QueuePop(&as);
		printf("%c", aq->_data);
		if (aq->_left)
		{
			QueuePush(&as, aq->_left);
		}
		if (aq->_right)
		{
			QueuePush(&as, aq->_right);
		}
	}
	QueueDestroy(&as);
}

1.3二叉树的创建

我们再回归到这个题，我们可以用先序遍历创建二叉树，我们现将数组首地址以及下标地址传进函数中，如果数组里的值为‘#’此处创建空节点，若不是，开辟一个二叉树的结构体空间，左右孩子子树也是这么创建的，子问题思路相同符合先序遍历的递归，左右孩子创建都用递归，别忘了下标访问一次数组，要自增，最后返回这个根节点

代码如下

BTNode* BinaryTreeCreate(BTDataType* a, int* pi)//通过前序遍历，创建二叉树 { if (a[*pi] == '#') { (*pi)++; return NULL; } BTNode* qa = (BTNode*)malloc(sizeof(BTNode)); qa->_data = a[(*pi)++]; qa->_left = BinaryTreeCreate(a, pi); qa->_right = BinaryTreeCreate(a, pi); return qa; }

最后再中序遍历打印就行了，代码在上面打过了

2.二叉树的节点个数

二叉树遍历与构建都清楚了，那我们如何用代码统计二叉树的节点个数，我们想想如果二叉树的节点为空，那么个数就返回0，若不为空，就是自身节点算一个，左孩子节点个数加右孩子节点个数加1（自身）,那么对于子问题也是如此求个数，可以用递归，为了节省效率，可以用三目操作符。

int BinaryTreeSize(BTNode* root)//节点个数
{
	return root == NULL ? 0 : BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}

如果递归想不出来的话，我们可以举个例子，方便我们记忆

假如一个学校让统计在校人数，校长吩咐给院长，院长吩咐给辅导员，辅导员吩咐给班长，班长统计人数返回给辅导员，辅导员把俩班人数加起来再加自身返回给院长，院长也是如此最后返回给校长，这其实就是二叉树的节点通过递归的统计方法，我们可以类比想一下

3.二叉树的叶子结点个数

叶子节点他的左孩子与右孩子都为空节点，我们计算二叉树叶子结点的个数，跟计算节点的个数类似，只不过此刻不需要加自身，只需要计算每个节点的左孩子叶子节点个数加右孩子叶子节点的个数就行了，如果我们找到一个叶子结点，返回1，若空节点返回0

代码如下

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行节点个数，不返回最后一行叶子结点个数，返回任意一行节点个数

假如我返回第三行的节点个数，那在我们遍历过程中，我们如何确定节点是否是第三行那，我们有图可以过一行K减一，只要向下递归一行K减一，到目标行第三行K就是1，也就是说，若K等于1，到达目标行

代码如下

int BinaryTreeLevelKSize(BTNode* root, int k)//二叉树第k个节点
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1);
}

4.二叉树的深度

二叉树的深度，就是通过比较左右子树深度高的那个加一，不断递归，找到最高的深度，代码如下

这里我们要注意一下，如图第一个代码，三目操作符你会发现大的那位会多调用一次，若递归越深，效率会急速下降，所以我们可以将他们的值用临时变量来判断

5.寻找x节点

这个首先通过先序遍历遍历每个节点，找到的话返回这个节点，若没找到，返回NULL，扎到的话用临时变量接收，不能直接返回，以为在递归遍历中，你返回返回的是递归过程中上一个函数，并不能完全返回出来，要想在递归中返回出来，就要用变量不断接收。

代码如下

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)//二叉树找值为x的节点
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->_data == x)
	{
		return root;
	}
	BTNode* as = BinaryTreeFind(root->_left, x);
	if (as)
		return as;
	BTNode* ak = BinaryTreeFind(root->_right, x);
	if (ak)
		return ak;
	return NULL;
}

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

怎么判断这个二叉树为完全二叉树那

我们沿用层序遍历的思路，层序遍历是将每个节点传入队列里，然后通过出队列顺序达到目的，那我们画图来看一下

由图可见，我们层序遍历过程中，若遇见空节点，我们要判断此刻队列里是否还有非空节点，若有则代表不连续，不是完全二叉树，若没有则是完全二叉树

代码如下

int BinaryTreeComplete(BTNode* root)//判断是否是完全二叉树
{
    Queue as;
    QueueInit(&as);
    QueuePush(&as, root);
    while (!QueueEmpty(&as))
    {
        BTNode* aq = QueueFront(&as);
        QueuePop(&as);
        if (aq == NULL)
        {
            break;
        }
            QueuePush(&as, aq->_left);
            QueuePush(&as, aq->_right);
    }
    while (!QueueEmpty(&as))
    {
        BTNode* ad = QueueFront(&as);
        if (ad)
        {
            QueueDestroy(&as);
            return 0;
        }
    }
    QueueDestroy(&as);
    return 1;
}

7.销毁二叉树

销毁二叉树不能从根开始消除，如果把根消除，怎么访问孩子节点，这是大忌！！！

我们得采用后序遍历来进行销毁，从叶子结点开始消除

代码如下

void BinaryTreeDestory(BTNode** root)//销毁二叉树
{
	if (*root == NULL)
	{
		return 0;
	}
	BinaryTreeDestory((*root)->_left);
	BinaryTreeDestory((*root)->_right);
	free(root);
}

8.以下是二叉树的实现

#pragma once
typedef char BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;
#include "队列.h"
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int* pi);
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
//二叉树的高度
int BinaryTreeHeight(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root);

#define _CRT_SECURE_NO_WARNINGS 1
#include "二叉树.h"

//BTNode* BTNodecreat(int i)
//{
//	BTNode* as = (BTNode*)malloc(sizeof(BTNode));
//	as->_data = i;
//	as->_left = NULL;
//	as->_right = NULL;
//}

BTNode* BinaryTreeCreate(BTDataType* a, int* pi)//通过前序遍历，创建二叉树
{
	/*BTNode* s1 = BTNodecreat(1);
	BTNode* s2 = BTNodecreat(2);
	BTNode* s3 = BTNodecreat(3);
	BTNode* s4 = BTNodecreat(4);
	BTNode* s5 = BTNodecreat(5);
	BTNode* s6 = BTNodecreat(6);
	s1->_left = s2;
	s1->_right = s3;
	s2->_left = s4;
	s2->_right = s5;
	s3->_left = s6;*/
	if (a[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}
	BTNode* qa = (BTNode*)malloc(sizeof(BTNode));
	qa->_data = a[(*pi)++];
	qa->_left = BinaryTreeCreate(a, pi);
	qa->_right = BinaryTreeCreate(a, pi);
	return qa;
}
void BinaryTreePrevOrder(BTNode* root)//前序遍历
{
	if (root == NULL)
	{
		return 0;
	}
	printf("%c ", root->_data);
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
}
void BinaryTreeInOrder(BTNode* root)//中序遍历
{
	if (root == NULL)
	{
		return 0;
	}
	BinaryTreePrevOrder(root->_left);
	printf("%c ", root->_data);
	BinaryTreePrevOrder(root->_right);
}
void BinaryTreePostOrder(BTNode* root)//后序遍历
{
	if (root == NULL)
	{
		return 0;
	}
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
	printf("%c ", root->_data);
}
int BinaryTreeSize(BTNode* root)//节点个数
{
	return root == NULL ? 0 : BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}
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);
}
int BinaryTreeLevelKSize(BTNode* root, int k)//二叉树第k个节点
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1);
}
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)//二叉树找值为x的节点
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->_data == x)
	{
		return root;
	}
	BTNode* as = BinaryTreeFind(root->_left, x);
	if (as)
		return as;
	BTNode* ak = BinaryTreeFind(root->_right, x);
	if (ak)
		return ak;
	return NULL;
}
void BinaryTreeDestory(BTNode** root)//销毁二叉树
{
	if (*root == NULL)
	{
		return 0;
	}
	BinaryTreeDestory((*root)->_left);
	BinaryTreeDestory((*root)->_right);
	free(root);
}
int BinaryTreeHeight(BTNode* root)//二叉树的深度
{
	if (root == NULL)
		return 0;
	return fmax(BinaryTreeHeight(root->_left), BinaryTreeHeight(root->_right))+1;
}
void BinaryTreeLevelOrder(BTNode* root)//层序遍历
{
	Queue as;
	QueueInit(&as);
	QueuePush(&as, root);
	while (!QueueEmpty(&as))
	{
		BTNode* aq = QueueFront(&as);
		QueuePop(&as);
		printf("%c", aq->_data);
		if (aq->_left)
		{
			QueuePush(&as, aq->_left);
		}
		if (aq->_right)
		{
			QueuePush(&as, aq->_right);
		}
	}
	QueueDestroy(&as);
}
int BinaryTreeComplete(BTNode* root)//判断是否是完全二叉树
{
	Queue as;
	QueueInit(&as);
	QueuePush(&as, root);
	while (!QueueEmpty(&as))
	{
		BTNode* aq = QueueFront(&as);
		QueuePop(&as);
		if (aq == NULL)
		{
			break;
		}
			QueuePush(&as, aq->_left);
			QueuePush(&as, aq->_right);
	}
	while (!QueueEmpty(&as))
	{
		BTNode* ad = QueueFront(&as);
		if (ad)
		{
			QueueDestroy(&as);
			return 0;
		}
	}
	QueueDestroy(&as);
	return 1;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "二叉树.h"
int main()
{
	char a[] ="ABD##E#H##CF##G##";
	int i = 0;
	BTNode* root = BinaryTreeCreate(a, &i);
	BinaryTreePrevOrder(root);
	printf("\n");
	BinaryTreeInOrder(root);
	printf("\n");
	printf("TreeSize:%d\n", BinaryTreeSize(root));
	printf("TreeLeafSize:%d\n", BinaryTreeLeafSize(root));
	printf("TreeHeight:%d\n", BinaryTreeHeight(root));
	printf("TreeLevelKSize:%d\n", BinaryTreeLevelKSize(root, 3));
	printf("TreeLevelKSize:%d\n", BinaryTreeLevelKSize(root, 4));

	BinaryTreeLevelOrder(root);
	printf("\n");

	BinaryTreeDestory(root);
	root = NULL;

	return 0;
}