当前位置：首页 > news >正文

【数据结构】链式二叉树知识点超全整理（内含完整代码解析

news 来源：原创 2024/5/20 0:54:33

1.二叉树链式结构的实现

1.1回顾一下二叉树的概念

1.2链式二叉树的构建和销毁

1.2.1链式二叉树的构建：

1.2.2链式二叉树的销毁

1.3二叉树的遍历

1.3.1 前序、中序以及后序遍历

1.3.2层序遍历

1.4. 节点个数以及高度等

1.4.1.求二叉树节点个数

1.4.2.二叉树叶子节点个数

1.4.3.二叉树第k层节点个数

1.4.4.二叉树查找值为x的节点

1.5判断树是否为完全二叉树

1.二叉树链式结构的实现

1.1回顾一下二叉树的概念

一棵二叉树是结点的一个有限集合，该集合:

1. 或者为空

2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成

具体细节可以移步我的这篇博文：

(17条消息) 【数据结构】二叉树、堆_vpurple__的博客-CSDN博客https://blog.csdn.net/vpurple_/article/details/126202240?spm=1001.2014.3001.5501从概念中可以看出，二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的。

1.2链式二叉树的构建和销毁

总体使用以下结构作为链式二叉树中的节点定义：

typedef char BTDataType;

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

1.2.1链式二叉树的构建：

BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);

参数介绍：

a 为指向"ABD##E#H##CF##G##"这个数组的指针

n 为数组的长度

pi 作为指向数组下标的指针

请注意：

在a指向的这个字符型数组中以'#'代表NULL，作为递归的返回条件。

在这个函数中通过读数组下标的方式来得到其中的数据，由于每递归一次就会重新建立一个新的函数栈帧，在其中的局部变量是独立的，如果传递的是数组下标而不是数组下标的地址的话，会导致完成一整套递归，返回上一层时的数组下标并没有随之++，而是重复访问

采用如下代码可成功构建链式二叉树：

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
	BTNode* tree = (BTNode*)malloc(sizeof(BTNode));
	if (tree == NULL)
	{
		perror("malloc fail\n");
		exit(-1);
	}
	if (*pi >= n || a[*pi] == '#')
	{
		return NULL;
	}
	tree->data = a[*pi];
	(* pi)++;
	tree->left = BinaryTreeCreate(a, n,pi );
	(* pi)++;
	tree->right = BinaryTreeCreate(a, n, pi);
	return tree;
}

1.2.2链式二叉树的销毁

要采用后续遍历的方法销毁，不然会造成前面的结点销毁后面链接的节点找不到的情况，从而造成内存泄漏。

void BinaryTreeDestory(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}

	BinaryTreeDestory(root->left);
	BinaryTreeDestory(root->right);
	free(root);
	root = NULL;
	return;
}

1.3二叉树的遍历

1.3.1 前序、中序以及后序遍历

学习二叉树结构，最简单的方式就是遍历。

所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。按照规则，二叉树的遍历有：

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

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->data);
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
	return;
}

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

// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	BinaryTreeInOrder(root->left);
	printf("%c ", root->data);
	BinaryTreeInOrder(root->right);
	return;
}

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

// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	BinaryTreePostOrder(root->left);
	BinaryTreePostOrder(root->right);
	printf("%c ", root->data);
	return;
}

1.3.2层序遍历

层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。

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

在这里我们借助之前写的队列来实现层序遍历：

先回顾一下之前写的队列：

这里主要会使用到

QueueInit 创建队列函数

QueueDestroy 销毁队列函数

QueuePush 数据队尾入队列函数

QueuePop 数据队头出队列函数

QueueFront 获取队头元素函数

(6条消息) 【数据结构】队列、环形队列_vpurple__的博客-CSDN博客https://blog.csdn.net/vpurple_/article/details/126200057?spm=1001.2014.3001.5501

解析如下，用电脑端打开观看更佳：

完整代码如下：

 层序遍历
// 通过队列实现层序遍历

void BinaryTreeLevelOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	Queue list;
	QueueInit(&list);
	QueuePush(&list, root);

	//当队列不是空的时候
	while (!QueueEmpty(&list))
	{
		//打印front的值，注意front的类型是BTNode*
		BTNode* front=QueueFront(&list);
		printf("%c ", front->data);
		QueuePop(&list);

		//front的左右入队列
		if (front->left != NULL)
		{
			QueuePush(&list, front->left);
		}
		if (front->right != NULL)
		{
			QueuePush(&list, front->right);
		}
	}
	printf("\n");
	QueueDestroy(&list);
}