数据结构——树

数据结构树的概念及操作

一期一祈^

1695人浏览 · 2024-11-18 19:41:08

一期一祈^ · 2024-11-18 19:41:08 发布

一、树的概念及结构

1.1树的概念

树是一种非线性的数据结构，它是由n（n>=0）个有限节点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它跟朝上，而叶朝下。

有一个特殊的节点，称为根节点，根节点没有前驱节点
除根节点外，其余节点被分成M(M>0)个互不相交的集合T1，T2…、Tm，其中每一个集合Ti(1<=i<=m)又是一棵结构与树类似的子树。每棵子树的的根节点有且只有一个前驱，可以有0个或多个后继
因此，树是递归定义的

树形结构中，子树之间不能有交集，否则就不是树形结构。

1.2树的相关概念

树中的关系是用人类亲缘关系来描述的。

结点的度：一个结点含有的子树的个数称为该结点的度
叶结点或终端结点：度为0的结点称为叶结点
非终端结点或分支结点：度不为0的结点
双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点
孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点
兄弟结点：具有相同父结点的结点互称为兄弟结点
树的度：一棵树中，最大的结点的度称为树的度
结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推
树的高度或深度：树中结点的最大层次
堂兄弟结点：双亲在同一层的结点互为堂兄弟
结点的祖先：从根到该结点所经分支上的所有结点
子孙：以某结点为根的子树中任一结点都称为该结点的子孙
森林：由m(m>0)棵互不相交的树的集合称为森林；多颗树就叫做森林

在这里插入图片描述

任何一棵树都是由根和子树构成。

二、二叉树概念及结构

2.1二叉树的概念

二叉树是n(n>0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。
特点：

1.每个结点至多有二棵子树
2.二叉树的子树有左右之分，且其次序不能任意颠倒，因此二叉树是有序树

对于任意的二叉树都是由以下几种复合而成：
在这里插入图片描述

特殊的二叉树
1.满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K，且结点总数是 $2^k-1$ ，则它就是满二叉树。
在这里插入图片描述

2.完全二叉树:完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。
在这里插入图片描述

2.2二叉树的性质

特点：
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)$ ，(ps: $log_2(n+1)$ 是l0g以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+2>=n否则无右孩子

对任何一棵二叉树，如果度为0其叶结点个数为n0，度为2的分支结点个数为n2，则有n0=n2+1；度为0的永远比度为2的多一个

2.3二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，二叉树顺存储在物理上是一个数组，在逻辑上是一颗二叉树。
二叉树的链式存储结构是指用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链。

三、二叉树顺序结构及实现

3.1二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。
在这里插入图片描述

3.2堆的概念及结构

如果有一个关键码的集合K={ $k_0$ ， $k_1$ ， $k_2$ ，…， $k_n-1$ }，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足: $K_i$ <= $K(_2*_i+_1)$ 且 $K_i$ <= $K(_2*_i+_2)$ ， $K_i$ >= $K(_2*_i+_1)$ 且 $K_i$ >= $K(_2*_i+_2$ ) i=0，1，2…，则称为小堆(或大堆)。将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。

堆的性质：

堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树
堆只限定了左右孩子大于或小于父结点，因此堆不是有序的。

3.3堆的实现

以大堆示例

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int HPDataType；
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;

void HPInit(HP* php);
void HPDestroy(HP* php);

void HPPush(HP* php,HPDataType x);
void HPPop(HP* php);
HPDataType HeapTop(HP* php);
bool HeapEmpty(HP* php);
int HeapSize(HP* php);

void AdjustUp(HPDataType* a,int child);
void AdjustDown(HPDataType* a,int n,int parent);

接口的实现

#include "Heap"
void HPInit(HP* php)
{
	assert(php);
	php->a = (HPDataType*)malloc(sizeof(HPDataType)*4);
	if(php->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	php->size = 0;
	php->capacity = 4;
}

void Swap(HPDataType* p1,HPDataType *p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void AdjustUp(HPDataType* a,int child)
{
	int parent = (child-1)/2;
	while(chlid > 0)
	{
		if(a[child] > a[parent])
		{
			Swap(&a[child],&a[parent]);
			child = parent;
			parent = (child-1)/2;
		}
		else
		{
			break;
		}
	}
}

void HPPush(HP* php,HPDataType x)
{
	assert(php);
	if(php->a==capacity)
 	{
 		HPDataType* tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType)*php->capacity*2)
 		if(tmp==NULL)
 		{
 			perror("realloc fail");
 			return;
 		}
 		php->a = tmp;
 		php->capacity *= 2;
 	}
 	php->a[php->size++] = x;
 	AdjustUp(php->a,php->size-1);
}

void AdjustDown(HPDataType* a,int n,int parent)
{
	int child = parent * 2 + 1;
	while(child < n)					//默认左孩子大
	{
		if(child + 1 < n && a[child] < a[child+1])		//如果右孩子存在且右孩子大于左孩子	
		{
			++child;
		}
		if (a[child] > a[parent])		
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HPPop(HP* php)
{
	assert(php);
	assert(!HPEmpty(php));
	Swap(&php->a[0],&a[php->size-1]);			//头尾交换位置在删除,为了不影响根和子树的关系
	php->size--;
	AdjustDowm(php->a,php->size,0);
}

HPDataType HeapTop(HP* php)
{
	assert(php);
	return php->a[0];
}

bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

int HeapSize(HP* php)
{
	assert(php);
	return php->size;
}

测试函数

#include "heap.h"

void test()
{
	HP hp;
	HeapInit(&hp);
	HeapPush(&hp, 36);
	HeapPush(&hp, 32);
	HeapPush(&hp, 33);
	HeapPush(&hp, 255);
	HeapPush(&hp, 44);
	HeapPush(&hp, 8);
	HeapPush(&hp, 333);
	HeapPush(&hp, 332);
	HeapPush(&hp, 2);
	HeapPush(&hp, 500);
	while (!HeapEmpty(&hp))
	{
		printf("%d ", HeapTop(&hp));
		HeapPop(&hp); 
		//输出:500 333 332 255 44 36 33 32 8 2
	}
	printf("\n");
}


int main()
{
	test();
}

3.4调整示例图

在这里插入和删除比顺序表多一个向上调整和向下调整的步骤
这里的难点是操作的是数组，想象操作的是个树，必须得画出来才方便理解

向上调整的前提条件：除了child位置，前面数据构成堆

在这里插入图片描述这个依次交换位置的过程叫做向上调整，所有父结点大于孩子结点，是大堆

向下调整的前提条件：左右子树都是大堆或小堆

四、二叉树链式结构

在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。这里先手动快速创建一棵简单的二叉树，快速进入二叉树操作学习，等二叉树结构了解的差不多时，后续再来研究二叉树真正的创建方式。

4.1遍历

前序：根，左子树，右子树
中序：左子树，根，右子树
后序：左子树，右子树，根

在这里插入图片描述前中后序遍历在递归中只需要换一下打印语句的位置就可以。
以上图的树为例

#pragma once
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

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");
		return NULL;
	}
	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 = node3;
	node2->left = node4;
	node3->left = node5;
	node3->right = node6;
	return node1;
}

//前序遍历
void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
	//输出:1 2 4 NULL NULL NULL 3 5 NULL NULL 6 NULL NULL
}

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

//后序遍历
void PosOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PosOrder(root->left);
	PosOrder(root->right);
	printf("%d ", root->data);
	//NULL NULL 4 NULL 2 NULL NULL 5 NULL NULL 6 3 1
}

//结点的个数
int TreeSize(BTNode* root)
{
	return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

//树的高度
int TreeHeight(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	
	//注意保存变量的值
	int leftHeight = TreeHeight(root->left);
	int rightHeight = TreeHeight(root->right);
	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

//第k层结点个数
int TreeKLevel(BTNode* root,int k)
{
	assert(k > 0);
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return TreeKLevel(root->left,k-1) + TreeKLevel(root->right,k-1);
}

BTNode* TreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	BTNode* lret = TreeFind(root->left,x);
	if (lret)
		return lret;
	BTNode* rret = TreeFind(root->right, x);
	if (rret)
		return rret;
	return NULL;
}


int main()
{
	BTNode* root = CreatTree();

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

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

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

	printf("TreeSize:%d\n", TreeSize(root));
	//输出:TreeSize:6
	
	printf("TreeHeight:%d\n", TreeHeight(root));
	//输出:TreeHeight : 3
	
	printf("TreeKLevel:%d\n", TreeKLevel(root, 1));
	//输出:TreeKLevel : 1
	printf("TreeKLevel:%d\n", TreeKLevel(root, 3));
	//输出:TreeKLevel: 3
	
	printf("TreeFind:%p\n", TreeFind(root, 5));
	//输出:TreeFind:008D9680
	printf("TreeFind:%p\n", TreeFind(root, 16));
	//输出:TreeFind:00000000
}

4.2其他基础操作

当前树的个数=左右子树+1
当前树的高度=左右子树高度大的那个+1。注意保存变量的值
当前树的第k层个数=左子树第k-1层个数+右子树第k-1层个数。注意判断条件
二叉树查找值为x的结点：找到x结点后注意保存

五、总结

在这里插入图片描述

DAMO开发者矩阵

DAMO开发者矩阵，由阿里巴巴达摩院和中国互联网协会联合发起，致力于探讨最前沿的技术趋势与应用成果，搭建高质量的交流与分享平台，推动技术创新与产业应用链接，围绕“人工智能与新型计算”构建开放共享的开发者生态。

更多推荐

RAG从入门到精通：文档处理与向量化，垃圾进垃圾出？不存在的！

如何用 RecursiveCharacterTextSplitter 智能切分文档。如何用 sentence-transformers 和 ChromaDB 将文本向量化并持久化。源码及依赖下载地址：https://pan.baidu.com/s/1CNntkxr226Xeo_jmnrCCkg?pwd=ek4t下一章，我们将进入检索与生成根据用户问题检索相关文档块。把检索结果和问题一起提交给Dee