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

二叉树链式结构：数据结构中的灵动之舞

article 2025/2/19 16:23:50

目录

前言

一、 前置说明 

二、二叉树的遍历

2.1前序遍历

 2.2中序遍历

 2.3 后序遍历

2.4层序遍历

 三、二叉树的遍历的应用

  3.1二叉树节点个数：

 3.2二叉树的高度

3.3 二叉树第k层的节点的个数

 3.4二叉树的查找

总结

前言

在数据结构的世界里，二叉树是一种极其重要的结构，它以其独特的性质和广泛的应用场景而备受关注。二叉树的存储结构主要有两种：顺序存储和链式存储。今天，我们将深入探讨二叉树的链式存储结构，从其基本概念、实现方式到实际，应用帮助大家全面理解这一强大的数据结构。

一、 前置说明 

在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。由于现在对二叉树结构还不够深入，为了降低学习成本，此处手动快速创建一棵简单的二叉树，快速进入二叉树操作学习，等二叉树结构了解的差不多时，我们反过头再来研究二叉树真正的创建方式。

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

BTNode* Buynode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		exit(1);
	}
	node->data = x;
	node->left = NULL;
	node->right = NULL;
	return node;
}
BTNode* CreatTree()
{
	BTNode* node1 = Buynode(1);
	BTNode* node2 = Buynode(2);
	BTNode* node3 = Buynode(3);
	BTNode* node4 = Buynode(4);
	BTNode* node5 = Buynode(5);
	BTNode* node6 = Buynode(6);
	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	return node1;
}

 在看二叉树基本操作前，首先要对二叉树的基本结构要清楚

  • 空树
  • 非空：根节点，根节点的左子树、根节点的右子树组成的。

 可以看出，二叉树的定义是递归式的，所以后续基本操作中基本都是按递归实现的，当然也是以二叉树的基本结构：根，左子树，右子树为基本展开的

二、二叉树的遍历

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

 二叉树的遍历有：前序/中序/后序的递归结构遍历：

2.1前序遍历

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

 前序遍历（根-左-右）

void PreOrder(BTNode* root)//前序遍历
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}

  递归演示图:

 OR

void PreOrder(BTNode* root)//前序遍历
{
	if (root)
	{
	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
    }
}

 递归演示图:

 

 2.2中序遍历

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

中序遍历（左-根-右）

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

}

 2.3 后序遍历

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

 后序遍历（左-右-根）

void PostOrder(BTNode* root)//后序遍历
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);

}

测试一下：

 

2.4层序遍历

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

 

 要用到队列的结构，A节点进对列出队列的时候，把a节点的左右子数节点进队列，a节点的左子数节点就是b，然后b再出队列的时候，又把b的左右子数节点路队列，然后c节点出队列，再又把c节点的左右子数节点路队列，以此类推

void LevelOrder(BTNode* root)//层序遍历
{
	Queue q;
		Init(&q);
		if(root)
	     Push(&q, root);
	while (!Empty(&q))
	{
		BTNode*front = QueueFront(&q);
		Pop(&q);
		printf("%d ",front->data);
		if (front->left)
		{
			Push(&q, front->left);
		}
		if (front->right)
		{
			Push(&q, front->right);
		}
	}
	Destroy(&q);
}

需注意的是，存入队列的是指向节点的指针，因此，需改变一下队列存储的数据类型：

typedef struct BinaryTreeNode* c;
typedef struct QueueNode
{
	struct QueueNode* next;
	c data;
}QNode;

 测试一下：

 三、二叉树的遍历的应用

  3.1二叉树节点个数：

int TreeSize(BTNode* root)
{
	return root == NULL ? 0 :
		TreeSize(root->left) +
		TreeSize(root->right) + 1;
}

 当然还有其他的方法 如：

定义一个全局变量size，然后用递归遍历树，每次能成功递归一次，就加一

int size = 0;
void TreeSize(BTNode* root)
{
	if (root == NULL)
		return;
	size++;
	TreeSize(root->left);
	TreeSize(root->right);

}
int main()
{
	BTNode* root = CreatTree();
	PreOrder(root);
	printf("\n");
	InOrder(root);
	printf("\n");
	PostOrder(root);
	printf("\n");
	TreeSize(root);
	printf("TreeSize=%d ",size);
	TreeSize(root);
	printf("\n");
	printf("TreeSize=%d ", size);
	return 0;
}

但是最好不要用全局变量，而且每次统计数量时，还要初始化一次，要不然就会

int size = 0;
void TreeSize(BTNode* root)
{
	if (root == NULL)
		return;
	size++;
	TreeSize(root->left);
	TreeSize(root->right);

}
int main()
{
	BTNode* root = CreatTree();
	PreOrder(root);
	printf("\n");
	InOrder(root);
	printf("\n");
	PostOrder(root);
	printf("\n");
	TreeSize(root);
	printf("TreeSize=%d ",size);
	TreeSize(root);
	printf("\n");
	printf("TreeSize=%d ", size);
	return 0;
}

 如果是改为局部的静态，甚至都没法初始化它，局部的静态只会在第一次调用它的时候初始化，

void TreeSize(BTNode* root)
{
	static int size = 0;
	if (root == NULL)
		return;
	size++;
	TreeSize(root->left);
	TreeSize(root->right);

}

 最好的方式就是在TreeSize函数中增添一个变量psize，统计它的个数，想要形参影响实参，就要传指针，就要传地址：

void TreeSize(BTNode* root,int *psize)
{
	static int size = 0;
	if (root == NULL)
		return;
	(*psize)++;
	TreeSize(root->left,psize);
	TreeSize(root->right,psize);
}
int main()
{
	BTNode* root = CreatTree();
	PreOrder(root);
	printf("\n");
	InOrder(root);
	printf("\n");
	PostOrder(root);
	printf("\n");
	int size1 = 0;
	TreeSize(root,&size1);
	printf("TreeSize=%d ",size1);
	int size2 = 0;
	TreeSize(root,&size2);
	printf("\n");
	printf("TreeSize=%d ", size2);
	return 0;
}

 测试一下：

 3.2二叉树的高度

int TreeHight(BTNode* root)
{
	if (root == NULL)
		return 0;
	int leftHeight = TreeHight(root->left);
	int rightHeight = TreeHight(root->right);

	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

 用参数保留它递归的结果，这样就不用return的时候再递归

3.3 二叉树第k层的节点的个数

int TreeKevel(BTNode* root, int x)
{
	assert(x > 0);
	if (root == NULL)
		return 0;
	if (x == 1)
		return x;
	/* int leftK = TreeKevel(root->left, x - 1);
	int rightK = TreeKevel(root->right, x - 1); 
	return leftK+rightK+1   or*/
	return TreeKevel(root->left, x - 1) + TreeKevel(root->right, x - 1);
}

 3.4二叉树的查找

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL || root->data == x)
		return root;
	BTNode* Findleft = BinaryTreeFind(root->left, x);
	if (Findleft)
		return Findleft;
	BTNode* Findright = BinaryTreeFind(root->right, x);
	if (Findright)
		return Findright;
	return NULL;
}

 我一开始在写的时候只写出了这样的代码，后来我画图演示递归的过程,才发现的错误,所以说要多画图

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL || root->data == x)
		return root;
	BTNode* Findleft = BinaryTreeFind(root->left, x);
	if (Findleft)
		return Findleft;
	BTNode* Findright = BinaryTreeFind(root->right, x);
	if (Findright)
		return Findright;
}

 查找递归演示图:

链式结构的优缺点

  • 优点1. 灵活性高：可以方便地表示任意形状的二叉树。
  • 2. 操作方便：插入、删除等操作只需修改指针，无需移动大量数据。
  • 3. 内存使用灵活：可以根据需要动态分配内存。
  • 缺点1. 空间开销大：每个节点需要额外存储两个指针，增加了内存开销。
  • 2. 访问效率低：链式存储无法像顺序存储那样通过下标快速访问节点。 

总结

二叉树的链式存储结构是一种强大而灵活的存储方式。它适用于各种复杂的二叉树操作，尤其是在处理非满二叉树时表现出色。通过本文的介绍，希望大家对二叉树的链式存储结构有了更深入的理解。在实际应用中，可以根据具体需求选择合适的存储方式，充分发挥链式结构的优势。


http://www.kler.cn/a/546812.html

相关文章：

  • 20250214 随笔 线程安全 线程不安全
  • C++实用技巧之 --- 观察者模式详解
  • OpenEuler学习笔记（三十三）：在 OpenEuler 上搭建 OpenGauss 数据库环境
  • Swift 的 KeyPath 是什么？
  • Java网络编程学习(二)
  • 西门子S7-1500 PLC的自动化控制系统解决方案
  • 28 在可以控制 postgres 服务器, 不知道任何用户名的情况下怎 进入 postgres 服务器
  • 芯谷 D2761：专为扬声器保护设计的音频限幅器
  • maven-antrun-plugin插件的用法
  • 制造业物联网的十大用例
  • 国家队出手！DeepSeek上线国家超算互联网平台！
  • 探索DeepSeek：开源大模型领域的中国力量
  • Java中使用EasyExcel
  • 微信小程序日程预约
  • 【Python深入浅出㊵】解锁Python3的requests模块：网络请求的魔法钥匙
  • 遵循规则：利用大语言模型进行视频异常检测的推理
  • DeepSeek v3 技术报告阅读笔记
  • spring 中 AspectJ 基于 XML 的实现分析
  • 安全启动(secure boot)怎么关闭_史上最全的各品牌机和组装机关闭安全启动教程
  • 将错误消息输出到标准错误流：Rust中的最佳实践