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

数据结构与算法：二叉树

article 2025/3/4 8:00:08

目录

树的概念

二叉树

二叉树性质

二叉树的遍历

前序遍历

中序遍历 

后序遍历

层序遍历

 二叉树节点个数

二叉树叶子节点个数

二叉树高度

二叉树第k层节点个数

二叉树查找值为x的节点

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

二叉树销毁

树的概念

树型结构是一类重要的非线性数据结构。其中以树和二叉树最为常用，直观看来，树是以分支关系定义的层次结构。把它叫做“树”是因为它常看起来像一棵倒挂的树，也就是说它常是根朝上，而叶朝下的。

树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树来形象表示。树在计算机领域中也得到广泛应用，如在操作系统中,可用树来表示文件系统的结构。又如在数据库系统中，树形结构也是信息的重要组织形式之一 。

树在不同领域也有不同的定义。

1、在数学中，树是一种无向图，其中不存在环路（即无回路），且任意两个结点之间有且仅有一条简单路径相连 [2]。这种定义主要用于图论和离散数学中，用于研究树的性质和特征。

2、在操作系统中，树是一种用于表示文件系统的结构，其中根目录位于树的顶部，子目录和文件位于根目录下 [3]。这种定义主要用于操作系统设计和文件管理。

3、在数据库中，树是一种用于表示层次关系的数据结构，树结构常用于实现数据库的索引、表示层次数据关系（如组织结构、分类目录）以及优化查询操作。这种定义主要用于数据库设计和数据管理，以提高数据检索效率和结构化数据的存储。

基本术语：

  • 1.结点：包含一个数据元素及若干指向其子树的分支；
  • 2.结点的度：一个结点拥有的子树的数目；
  • 3.叶子或终端结点：度为0的结点；
  • 4.非终端结点或分支结点：度不为0的结点；
  • 5.树的度：树内各结点的度的最大值；
  • 6.孩子结点或子结点：结点的子树的根称为该结点的孩子结点或子结点；
  • 7.双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的双亲结点或父结点；
  • 8.兄弟结点：同一个双亲的孩子之间互称兄弟；
  • 9.祖先结点：从根到该结点所经分支上的所有结点；
  • 10.子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙；
  • 11.结点的层次：从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第 L 层．则其子树的根就在第 L + 1层；
  • 12.堂兄弟结点：其双亲在同一层的结点互为堂兄弟；
  • 13.树的深度或高度：树中结点的最大层次；
  • 14.森林：由m（m > 0）棵互不相交的树的集合称为森林;
  • 15.有序树和无序树：树中结点的各子树从左到右是有次序的，不能互换，称该树为有序树，否则称为无序树；
  • 16.路径和路径长度：路径是由树中的两个结点之间的结点序列构成的。而路径长度是路径上所经过的边的个数

二叉树

​

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

二叉树性质

1.若规定根节点的层数为1，则一棵非空二叉树上的第 i 层最多有2^{(i-1)}个节点

2.若规定根节点的层数为1，则深度为 h 的二叉树的最大节点数是2^{h}-1

3.对任何一棵二叉树，如果度为0其叶节点个数为n_{0}，度为2的分支结点个数为n_{2},则有n_{0} = n_{2} + 1 

4.若规定根节点的层数为1，具有 n 个节点的满二叉树的深度，h = \log_{2}(N+1)

5.对于具有 n 个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所以结点从0开始编号，则对于序号为 i 的结点有：

  1. 若 i > 0, i  位置结点的双亲序号：(i - 1) / 2;  i = 0,   i 为根节点编号，无双亲结点。
  2. 若 2i+ 1 < n ，左孩子序号 2i+ 1， 2i+ 1 >= n 则为左孩子
  3. 若 2i+ 2 < n，右孩子序号：2i+ 2，2i+ 1 >= n 则无右孩子

二叉树的遍历

前序遍历

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

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

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

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

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

//后序
void Posorder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	Posorder(root->left);
	Posorder(root->right);
	printf("%d ", root->data);
}

层序遍历

‌层序遍历（也称为广度优先遍历）是二叉树遍历的一种方法，其基本思想是从根节点开始，按照从上到下、从左到右的顺序访问二叉树的每一层节点‌。‌

层序遍历通常使用队列来实现：

  1. 将根节点放入队列中。
  2. 当队列不为空时，循环执行以下操作：
    • 从队列中弹出一个节点，访问该节点。
    • 如果该节点有左子节点，将左子节点加入队列。
    • 如果该节点有右子节点，将右子节点加入队列。
  3. 继续执行步骤2，直到队列为空。
void TreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		//上一层带下一层

		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%d ", front->data);

		if (front->left)
			QueuePush(&q, front->left);
		if (front->right)
			QueuePush(&q, front->right);
	}
	QueueDestory(&q);
}

 二叉树节点个数

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

不能这样写，这样写每次调用这个函数都会累加

​

可以这样写

int size = 0;
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	else
		++size;
	BinaryTreeSize(root->left);
	BinaryTreeSize(root->right);
	return size;
}

但是每次调用这个函数的时候，都要重置一下size。

最好的方法 分治递归

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);
}

 什么是叶子结点呢？通常来讲在一棵树里面，如果一个结点没有左子树和右子树，那么它就是叶子。左子树和右子树为空，那么叶子结点个数加1，返回给上一层。

二叉树高度

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

 上面这种方法存在效率问题，原因是递归返回后函数栈帧会销毁，没有记录，

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

	return left > right ? left + 1 : right + 1;
}

//int BinaryTreeHeight(BTNode* root)
//{
//	if (root == NULL)
//		return 0;
//	return fmax(BinaryTreeHeight(root->left), BinaryTreeHeight(root->right)) + 1;
//}

二叉树第k层节点个数

int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return BinaryTreeLevelKSize(root->left, k - 1) +
		BinaryTreeLevelKSize(root->right, k - 1);
}

求第k层结点个数，需要转化成当前问题和子问题。比如说，求第3层结点的个数，那么对这棵树的第一层来说，从它开始，求它向下的3层。然后k减1。对于第二层来说，求从它开始向下的第2层，k减1。对于第三层来说，就是求从它开始向下的第1层，为第1层时，返回1给上一层。

二叉树查找值为x的节点

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;

	BTNode* ret1 = BinaryTreeFind(root->left, x);
	if (ret1)
		return ret1;
	BTNode* ret2 = BinaryTreeFind(root->right, x);
	if (ret2)
		return ret2;

	return NULL;
}

如果走到叶子节点的下一个，即root为空，就返回空。如果在左子树找到了，那么在右子树就没必要找了，就直接返回这个节点。但是一定要记录这个节点，因为递归返回会销毁函数栈帧，你不返回给上层这个找到的节点的记录，上层不知道你找到没有，就认为没有找到。继续返回给它的上层。 如果左子树没有找到，右子树也没有找到，就返回空。

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

需要用到层序遍历 

bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	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);
	}

	//开始判断队列中已有的数据
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		//遇到非空,不是完全二叉树
		if (front)
		{
			QueueDestory(&q);
			return false;
		}
	}
	QueueDestory(&q);
	return true;
}

首先定义一个队列，初始化队列，如果树不为空，那么让树的根结点入队列。通过一个while循环，可以把二叉树的所有节点全部遍历一遍，让它的节点入队列和出队列。这个while循环结束后吗，二叉树中的所有结点全部过了一遍，就算有 没有入队列的结点，也没有关系，因为这时只需要判断现在的队列中，是否还存在数据，如果存在，则说明不是完全二叉树，返回false。反之，说明为完全二叉树，返回true。这一层判断通过一个while循环完成。

二叉树销毁

void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
		return;
	BinaryTreeDestory((*root)->left);
	BinaryTreeDestory((*root)->right);
	free(*root);
}

二叉树的销毁可以看成一个后序遍历，先左子树销毁，然后右子树销毁，最后根节点销毁。


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

相关文章：

  • C++ Qt OpenGL渲染FFmpeg解码后的视频
  • CMS Made Simple v2.2.15远程命令执行漏洞（CVE-2022-23906）
  • 20250301_代码笔记_函数class CVRPEnv: def step(self, selected)
  • 文件描述符与重定向
  • ES批量查询
  • 大模型训练——pycharm连接实验室服务器
  • Python中文自然语言处理库SnowNLP
  • 多通道数据采集和信号生成的模块化仪器如何重构飞机电子可靠性测试体系？
  • 数据结构之各类排序算法代码及其详解
  • 判断按键盘是否好使的开机自启动PowerShell脚本
  • 【MATLAB例程】三维下的IMM（交互式多模型），模型使用CV（匀速）和CA（匀加速）
  • UWB人员定位：精准、高效、安全的智能管理解决方案
  • 使用3090显卡部署Wan2.1生成视频
  • 基于ai技术的视频生成工具
  • Java——String
  • 计算机网络之传输层（传输层提供的服务）
  • DeepSeek 开源狂欢周（五）正式收官｜3FS并行文件系统榨干SSD
  • 【漫话机器学习系列】111.指数之和的对数（Log-Sum-Exp）
  • Flink同步数据mysql到doris问题合集
  • Ubuntu 下 nginx-1.24.0 源码分析 - ngx_init_cycle 函数 - 详解（5）