一篇文章讲透数据结构之树

一.树

1.1树的定义

树是一种非线性的数据结构，它是有n个有限结点组成的一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根在上，叶在下的。

在树中有一个特殊的结点，称为根结点，根结点没有前驱结点

除根结点外，其余的结点被分成了M个互不相交的集合T1、T2、......、Tm，其中每一个集合Ti又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱结点，但可以有0个或多个后继结点。因此：树是递归定义的。

注意：树的结点之间是不可以有交集的，有交集的话就不是树了，至于是什么我们后期再说。

如下图：以A为根节点的就不是树，以D为结点的才是树。

  

1.2树的基本概念

  1. 结点的度：一个结点含有的子树的个数称为该结点的度
  2. 叶子结点：度为0的结点称为叶子结点
  3. 分支结点：度不为0的结点
  4. 双亲结点/父结点：若一个结点包含子节点，则这个结点称为其子结点的父节点
  5. 孩子结点/子节点：一个结点含有的子树的根结点称为该结点的子节点
  6. 兄弟结点：具有相同父节点的结点互称为兄弟结点
  7. 树的度：一棵树中，度最大的结点的度称为树的度
  8. 结点的层次：定义根为第一层，根的子节点为第二层，依次类推即可
  9. 树的高度或深度：树中结点的最大层次
  10. 堂兄弟结点：双亲在同一层的结点互为堂兄弟结点
  11. 结点的祖先：从根到该结点所经分支上的所有结点。
  12. 子孙：以某结点为根的子树的任一结点都称为该结点的子孙。
  13. 森林：由m棵互不相交的树组成的集合称为森林。

1.3树的表示方法

我们在这里学习三种树的表示方法，分别为双亲表示法、树的孩子表示法、左孩子右兄弟表示法。

我们将用这三种方法来表示这一棵树：

1.3.1父节点表示法（双亲表示法）

树的父节点表示法，是利用顺序表来完成的，怎么做呢？

首先，我们创建顺序表结构体来存储结点的内容以及父节点的下标。我们将这个结构体称为结点结构体。

然后，我们创建树的结构体，其中一个是结点结构体数组，一个是数组内元素个数。

由此，我们可以写出如下代码：

//双亲表示法
//顺序表的方式存储
//顺序表存储结点的数据和双亲结点的下标
typedef int DataType;
typedef struct Node
{
	DataType data;//数据域
	int parent;//双亲结点下标
}Node;
//树-->结点组成的数组
typedef struct Tree
{
	Node NodeArr[10];//保存结点的数组，也可以动态申请
	int size;//结点个数
};

在这里需要我们大家注意的是：由于根节点没有前驱结点，我们将其的父节点特别记为-1. 

下面我们来表示一下这棵树。

1.3.2树的孩子表示法

树的孩子表示法是通过顺序表和链表结合的形式表示的

它的原理是：

  • 先定义一个单链表结构体表示一个父节点的所有孩子结点的下标，一个孩子指向另外一个孩子
  • 然后用一个顺序表结构体存储当前结点的数值以及这个结点的第一个孩子结点的下标
  • 最后定义一个树结构体

那么，我们就可以写出如下代码：

typedef int DataType;
//链表
struct ListNode
{
	int child;//当前孩子结点下标
	struct Listnode* next;//下一个孩子
};
//顺序表
struct Node
{
	DataType data;//结点的数据
	ListNode* FirstChild;//第一个孩子
};
struct Tree
{
	Node NodeArr[10];
	int size;
};

现在我们画图来理解一下这个方法

  • 绿色的是全部的链表结构体（每个单链表之间没有关系）
  • 绿色的每一块是一个单链表
  • 紫色中的每一块是一个顺序表
  • 由于图的篇幅有限，将一个树分开画了，紫色的其实是一个整体
  • 紫色每一块的右下角是元素的个数

 

这个方法的缺点就是：我们要在顺序表中插入或者删除数据需要移动大量的数据。 

1.3.3左孩子右兄弟表示法

这个是最常用的表示树的的方法，即定义两个指针，让左指针指向最左边的子节点，右指针指向兄弟节点。

如果没有节点，则都指向空。

typedef int DataType;
struct Node
{
	struct Node* leftChild;//孩子结点
	struct Node* rightBrother;//指向下一个兄弟结点
	DataType Data;//数据域
};

我们下面具体画一下图： 

1.4树的实际应用

在linux环境下目录结构就是有一颗树构成。

而在Windows环境下，目录许多内容并不交叉，所以是由森林构成。

二.二叉树

2.1二叉树的定义

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

1.或者为空

2.由一个根节点加上两棵别称（别名/外号）为：左子树、右子树的二叉树组成

从上图可以看出

  • 二叉树不存在度大于2的结点
  • 二叉树的子树有左右之分，次序不能颠倒， 因此二叉树是有序树

我们可以将一棵二叉树拆分开来，我们会发现任何一棵二叉树都是由以下几种情况复合而来的：

下面给大家看一张现实生活中存在的二叉树： 

2.2特殊的二叉树

  • 满二叉树：

一个二叉树，如果每一层的节点数都达到了最大值，那么这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是2^k-1，则它就是满二叉树。

  • 完全二叉树：

完全二叉树是一种效率很高的数据结构。

完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1到n的结点都可以一一对应时，则可称之为完全二叉树。也就是说：满二叉树是一种特殊的完全二叉树。（文字表述蛮抽象的，其实就是倒数第二层满，最后一层的叶子结点要从左往右放）

2.3二叉树的相关性质

1. 若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1)个结点.
2. 若规定根结点的层数为1，则深度为h的二叉树的最大结点数是2^h-1.
3. 对任何一棵二叉树, 如果度为0其叶结点个数为 , 度为2的分支结点个数为 ,则有 n0＝n2＋1

4.若规定根结点的层数为1，具有n个结点的满二叉树的深度，h=log(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否则无右孩子

结论3的推导过程：

 其余结论的推导过程可参考：堆的实现 

2.4二叉树的存储

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

2.4.1顺序结构

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树。

因为不是完全二叉树会有空间的浪费。

而现实中使用中只有堆才会使用数组来存储，关于堆的实现可以参考上面的链接。

二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

如下图，左边是完全二叉树，不会有空间浪费；

右边是不完全二叉树，有空间浪费。

2.4.2链式存储 

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。

如下图所示：

最左边是存储结构，中间是二叉树实例，右边是逻辑结构图。

在这里我们采用链式结构来存储二叉树：

2.5二叉树的遍历

二叉树的遍历方式有四种：前序遍历、中序遍历、后序遍历、层序遍历

二叉树的前、中、后序遍历都可以通过递归和用栈模拟递归实现，这里我们学习这两种方法.

大家可以先研究代码，理解困难的话可以根据视频学习：

视频1：

二叉树的前中后序遍历的递归实现

视频2：

二叉树前中后序遍历的非递归实现以及层序遍历

2.5.1前序遍历

前序遍历：先遍历根节点，再依次遍历左子树，右子树。而遍历左子树，又要先遍历根节点，再依次遍历左子树，右子树…...直到遍历完整棵树。

递归实现 

void PreOrder1(BTree* root)
{
	assert(root);
	if (!root)
	{
		return;
	}
	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}

 非递归实现

typedef BTree* STDataType;
void PreOrder2(BTree* root)
{
	//开辟一个栈
	Stack s;
	StackInit(&s);
	BTree* p = root;
	while (p || !IsEmpty(&s))
	{
		if (p != NULL)
		{
			printf("%d ", p->data);
			StackPush(&s, p);
			p = p->left;
		}
		else
		{
             p = StackTop(&s);		    
             StackPop(&s);
			p = p->right;
		}
	}
}

2.5.2中序遍历

先遍历左子树，再依次遍历根节点，右子树。而遍历左子树，又要先遍历左子树，再依次遍历根节点，右子树…直至遍历完整棵树。

递归实现

void Inorder1(BTree*root)
{
    if (root == NULL)
    {
        return;
    }
    PreOrder(root->left);//左子树
    printf("%d ", root->data);//根节点
    PreOrder(root->right);//右子树
}

非递归实现 

  typedef BTree* STDataType;
  void Inorder2(BTree* root)
  {
	  Stack s;
	  InitStack(&s);
	  BTree* p = root;
	  while (p || !IsEmpty(&s))  
	  {
		  if (p != NULL)//入栈
		  {
			  StackPush(&s, p);
			  p = p->left;
		  }
		  else
		  {
			  p = StackTop(&s);
			  StackPop(&s);	  
			  printf("%d ", p->data);
			  p = p->right;
		  }
	  }
  }

2.5.3后序遍历

后序遍历：先遍历左子树，再依次遍历右子树，根节点。而遍历左子树，又要先遍历左子树，再依次遍历右子树，根节点…直至遍历完整棵树。

递归实现

void Postorder1(BTree*root)
{
    if (root == NULL)
    {
        return;
    }
    PreOrder(root->left);//左子树
    PreOrder(root->right);//右子树
    printf("%d ", root->data);//根节点
}

 非递归实现

void Postorder2(BTree* root)
{
	Stack s;
	InitStack(&s);
	BTree* p = root;// p为遍历指针
	BTree* v = root;// v标记已访问节点
	while (p || !IsEmpty(&s))  // 栈不为空或p不为空时循环
	{
		while(p != NULL)//入栈
		{
			StackPush(&s, p);
			p = p->left;
		}
		p = StackTop(&s);
		if (p->right && p->right != v)//存在右子树，且没有被访问
		{
			p = p->right;//访问
		}
		else//没有右子树或者右子树已被访问
		{
			printf("%d ", p->data);
			v = p;//记录当前访问的节点
			p = NULL;//防止重复访问左子树
			StackPop(&s);// 栈顶元素出栈
		}
	}
}

2.5.4层序遍历

层序遍历，就是一层一层的遍历。

这里我们借助队列来实现。

void leverOrder(BTree* root, Queue* pq)
{
	if (root == NULL)//为空直接返回
	{
		return;
	}
	QueuePush(pq, root);//插入第一个节点
	while (!QueueEmpty(pq))//队列不为空
	{
		BTree* p = QueueFront(pq);
		printf("%d ", p->data);
		QueuePop(pq);
		if (p->left != NULL)//带入左孩子
		{
			QueuePush(pq, p->left);
		}
		if (p->right != NULL)//带入右孩子
		{
			QueuePush(pq, p->right);
		}
	}
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/669147.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

vue3可以快速简单的操作dom元素了

vue3可以快速简单的操作dom元素了

再也不需要用document.getElementById("myElement")的这种方式来对dom元素进行操作了 我们需要使用模板引用——也就是指向模板中一个 DOM 元素的 ref。我们需要通过这个特殊的 ref attribute 来实现模板引用&#xff1a; <script setup> import { ref, onMo…
阅读更多...
【linux】docker安装下载器：aria2、gopeed、thunder迅雷

【linux】docker安装下载器：aria2、gopeed、thunder迅雷

一、aria2 1、下载aria2服务镜像 docker pull p3terx/aria2-pro 2、下载ariang页面服务 docker pull p3terx/ariang 3、启动aria2服务 docker run -d --name aria2 \ --restart unless-stopped \ --log-opt max-size1m \ -e PUID$UID \ -e PGID$GID \ -e UMASK_SET022 \ -…
阅读更多...
基于电导增量MPPT控制算法的光伏发电系统simulink建模与仿真

基于电导增量MPPT控制算法的光伏发电系统simulink建模与仿真

目录 1.课题概述 2.系统仿真结果 3.核心程序与模型 4.系统原理简介 5.完整工程文件 1.课题概述 基于电导增量MPPT控制算法的光伏发电系统simulink建模与仿真。输出MPPT跟踪后的系统电流&#xff0c;电压以及功率。 2.系统仿真结果 3.核心程序与模型 版本&#xff1a;MAT…
阅读更多...
Facebook的创新实验室：人工智能与新技术探索

Facebook的创新实验室：人工智能与新技术探索

Facebook作为全球领先的社交媒体平台之一&#xff0c;一直在不断探索和应用最新的技术来改善用户体验、推动创新和拓展业务边界。其创新实验室更是探索人工智能&#xff08;AI&#xff09;和新技术的前沿&#xff0c;为未来的社交媒体发展开辟了新的可能性。本文将深入探讨Face…
阅读更多...
深度学习复盘与论文复现A

深度学习复盘与论文复现A

文章目录 一、查漏补缺复盘1、python中zip()用法2、Tensor和tensor的区别3、计算图中的迭代取数4、nn.Modlue及nn.Linear 源码理解5、知识杂项思考列表6、KL散度初步理解 二、处理多维特征的输入1、逻辑回归模型流程2、Mini-Batch (N samples) 三、加载数据集1、Python 魔法方法…
阅读更多...
神经网络的工程基础（二）——随机梯度下降法｜文末送书

神经网络的工程基础（二）——随机梯度下降法｜文末送书

相关说明 这篇文章的大部分内容参考自我的新书《解构大语言模型&#xff1a;从线性回归到通用人工智能》&#xff0c;欢迎有兴趣的读者多多支持。 本文涉及到的代码链接如下&#xff1a;regression2chatgpt/ch06_optimizer/stochastic_gradient_descent.ipynb 本文将讨论利用…
阅读更多...
Linux下CPU1000%记一次挖矿病毒清理流程

Linux下CPU1000%记一次挖矿病毒清理流程

今天top后发现一个进程CPU高1795%&#xff0c;判断是病毒 查找进程ps -elf|grep 进程idpid和ppid查找到sleep进程 ps -ef|grep 4277 查看具体进程内容&#xff0c;ll /proc/进程idpid ll /proc/4277 ls -l /proc/{pid号} ls -l /proc/{pid号}/exe kill掉病毒进程 排查病毒…
阅读更多...
Android开机动画的结束过程BootAnimation(基于Android10.0.0-r41)

Android开机动画的结束过程BootAnimation(基于Android10.0.0-r41)

文章目录 Android 开机动画的结束过程BootAnimation(基于Android10.0.0-r41) Android 开机动画的结束过程BootAnimation(基于Android10.0.0-r41) 路径frameworks/base/cmds/bootanimation/bootanimation_main.cpp init进程把我们的BootAnimation的二进制文件拉起来了&#xf…
阅读更多...
如何备份RDK X3（旭日X3派）的 SD卡镜像

如何备份RDK X3（旭日X3派）的 SD卡镜像

该方法可以在Ubuntu的开发机上生成一个img镜像&#xff0c;后续可以直接使用rufus软件烧录备份好的镜像。 Step 1&#xff1a;在Ubuntu的开发机上安装gparted软件 如果安装失败则需要为您的Ubuntu开发机换源&#xff0c;这里推荐阿里源&#xff1a;https://developer.aliyun.…
阅读更多...
用户购物性别模型标签（USG）之决策树模型

用户购物性别模型标签（USG）之决策树模型

一、USG模型引入: 首先了解一下&#xff0c;如何通过大数据来确定用户的真实性别&#xff0c; 经常谈论的用户精细化运营&#xff0c;到底是什么? 简单来讲&#xff0c;就是将网站的每个用户标签化&#xff0c;制作一个属于用户自己的网络身份证。然后&#xff0c;运营人员 通…
阅读更多...
【算法】贪心算法简介

【算法】贪心算法简介

贪心算法概述 目录 1.贪心算法概念2.贪心算法特点3.贪心算法学习 1.贪心算法概念 贪心算法是一种 “思想” &#xff0c;即解决问题时从 “局部最优” 从而达到 “全局最优” 的效果。 ①把解决问题的过程分为若干步②解决每一步时候&#xff0c;都选择当前最优解(不关注全局…
阅读更多...
基于SSM前后端分离版本的论坛系统-自动化测试

基于SSM前后端分离版本的论坛系统-自动化测试

目录 前言 一、测试环境 二、环境部署 三、测试用例 四、执行测试 4.1、公共类设计 创建浏览器驱动对象 测试套件 释放驱动类 4.2、功能测试 注册页面 登录页面 版块 帖子 用户个人中心页 站内信 4.3、界面测试 注册页面 登录页面 版块 帖子 用户个人中心页…
阅读更多...
数据整理操作及众所周知【数据分析】

数据整理操作及众所周知【数据分析】

各位大佬好 &#xff0c;这里是阿川的博客&#xff0c;祝您变得更强 个人主页&#xff1a;在线OJ的阿川 大佬的支持和鼓励&#xff0c;将是我成长路上最大的动力 阿川水平有限&#xff0c;如有错误&#xff0c;欢迎大佬指正 Python 初阶 Python–语言基础与由来介绍 Python–…
阅读更多...
进程与线程（二）

进程与线程（二）

进程与线程&#xff08;二&#xff09; exec函数族守护进程守护进程的概念Linux守护进程的编写步骤创建子进程&#xff0c;父进程退出在子进程中创建新会话改变当前目录为根目录重设文件权限掩码关闭文件描述符守护进程案例编写 线程线程的概念Linux下进程和线程的区别 Linux下…
阅读更多...
C++基础编程100题-002 OpenJudge-1.1-04 输出保留3位小数的浮点数

C++基础编程100题-002 OpenJudge-1.1-04 输出保留3位小数的浮点数

更多资源请关注纽扣编程微信公众号 002 OpenJudge-1.1-04 输出保留3位小数的浮点数 http://noi.openjudge.cn/ch0101/04/ 描述 读入一个单精度浮点数&#xff0c;保留3位小数输出这个浮点数。 输入 只有一行&#xff0c;一个单精度浮点数。 输出 也只有一行&#xff0c;…
阅读更多...
java —— 集合

java —— 集合

一、集合的概念 集合可以看做是一个存储对象的容器&#xff0c;与数组不同的是集合可以存储不同类型的对象&#xff0c;但开发中一般不这样做。集合不能存储基本类型的对象&#xff0c;如果存储则需要将其转化为对应的包装类。 二、集合的分类 集合分为 Collection 和 Map 两…
阅读更多...
2024抖音流量认知课：掌握流量底层逻辑，明白应该选择什么赛道 (43节课)

2024抖音流量认知课：掌握流量底层逻辑，明白应该选择什么赛道 (43节课)

课程下载&#xff1a;https://download.csdn.net/download/m0_66047725/89360865 更多资源下载&#xff1a;关注我。 课程目录 01序言&#xff1a;拍前请看.mp4 02抖音建模逻辑1.mp4 03抖音标签逻辑2.mp4 04抖音推流逻辑3.mp4 05抖音起号逻辑4.mp4 06养号的意义.mp4 0…
阅读更多...
算法解析——单身狗问题

算法解析——单身狗问题

欢迎来到博主的专栏&#xff1a;算法解析 博主ID代码小豪 文章目录 什么是单身狗问题leetcode_136——只出现一次的数字I使用位运算解决单身狗问题。 leetcode_137——只出现一次的数字II统计二进制数解决单身狗问题leetcode_260 只出现一次数字III分区域按位异或解决问题。 总…
阅读更多...
iperf3带宽压测工具使用

iperf3带宽压测工具使用

iperf3带宽压测工具使用 安装下载地址&#xff1a;[下载入口](https://iperf.fr/iperf-download.php)测试结果&#xff1a;时长测试&#xff08;压测使用&#xff09;:并行测试反向测试UDP 带宽测试 iPerf3 是用于主动测试 IP 网络上最大可用带宽的工具 安装 下载地址&#x…
阅读更多...
SAP 生产订单批量报工(代码分享)

SAP 生产订单批量报工(代码分享)

最近公司一直在对成本这块的业务进行梳理，影响比较大的就是生产这块的报工，经常会要求要批量的冲销报工，然后在继续报工，来调整生产订单的实际工时，前面的博客中已经给大家分享了批量冲销生产订单的代码， 下面给大家分享一下生产订单批量报工的代码 首先流程制造和离散制…
阅读更多...
最新文章

Copyright @ 2022~2023