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

一.树

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/679922.html

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

相关文章

python学习笔记-04

python学习笔记-04

高级数据类型 一组按照顺序排列的值称为序列&#xff0c;python中存在三种内置的序列类型&#xff1a;字符串、列表和元组。序列可以支持索引和切片的操作&#xff0c;第一个索引值为0表示从左向右找&#xff0c;第一个索引值为负数表示从右找。 1.字符串操作 1.1 切片 切片…
阅读更多...
Renesas MCU之定时器计数功能应用

Renesas MCU之定时器计数功能应用

目录 概述 1 功能介绍 1.1 时钟相关配置 1.2 应用接口 2 FSP配置Project参数 2.1 软件版本信息 2.2 配置参数 2.3 项目生成 3 定时器功能代码实现 3.1 定时器初始化函数 3.2 定时器回调函数 4 功能测试 5 参考文档 概述 本文主要介绍Renesas MCU的定时器功能的基…
阅读更多...
Python语法详解module1（变量、数据类型）

Python语法详解module1（变量、数据类型）

目录 一、变量1. 变量的概念2. 创建变量3. 变量的修改4. 变量的命名 二、数据类型1. Python中的数据类型2. 整型&#xff08;int&#xff09;3. 浮点型&#xff08;float&#xff09;4. 布尔型&#xff08;bool&#xff09;5. 字符串&#xff08;str&#xff09;6.复数&#xf…
阅读更多...
​ChatTTS：Win11本地安装和一键运行包!

​ChatTTS：Win11本地安装和一键运行包!

ChatTTS 是一个专为交互式语音准备的AI语音合成项目&#xff0c;特点是自然&#xff0c;逼真&#xff0c;可把控声音细节&#xff0c;能说能笑能停顿。 效果演示 具体内容&#xff0c;已经在另外的文章中介绍过。 本文主要是关注两个点。 如何在Windows上安装这个项目。分享一…
阅读更多...
2024蓝桥杯初赛决赛pwn题全解

2024蓝桥杯初赛决赛pwn题全解

蓝桥杯初赛决赛pwn题解 初赛第一题第二题 决赛getting_startedbabyheap 初赛 第一题 有system函数&#xff0c;并且能在bss上读入字符 而且存在栈溢出&#xff0c;只要过掉check函数即可 check函数中&#xff0c;主要是对system常规获取权限的参数&#xff0c;进行了过滤&…
阅读更多...
软件测试总结基础

软件测试总结基础

软件测试总结基础 1. 何为软件测试 定义&#xff1a;使用技术手段验证软件是否满足需求 目的&#xff1a;减少bug&#xff0c;保证质量 2. 软件测试分类 阶段划分 单元测试&#xff0c;针对源代码进行测试集成测试&#xff0c;针对接口进行测试系统测试&#xff0c;针对功能…
阅读更多...
声音的归宿：恢复手机录音的3个步骤与策略

声音的归宿：恢复手机录音的3个步骤与策略

“手机录音删除了怎么恢复&#xff0c;没有云备份。本人平时喜欢用手机录音机录一些唱的歌&#xff0c;上次录过之后就再也没有打开&#xff0c;今天一打开发现上个月的录音都没了&#xff01;里面都是我的歌&#xff0c;还有期末重点&#xff0c;还有声乐课的录的音频&#xf…
阅读更多...
免费工具扫描 Linux 中已知威胁

免费工具扫描 Linux 中已知威胁

首发公众号网络研究观&#xff0c;关注获取更多。 卡巴斯基为 Linux 平台发布了一款名为 KVRT 的新病毒清除工具&#xff0c;允许用户免费扫描他们的系统并清除恶意软件和其他已知威胁。 尽管人们普遍误以为 Linux 系统本质上是安全的&#xff0c;不会受到威胁&#xff0c;但不…
阅读更多...
jeecg dictText字典值

jeecg dictText字典值

前端列表的字典值回显&#xff0c;配置了数据字典后&#xff0c;在本地测试可以回显中文的数据&#xff0c; 但在线上服务器不能正常回显出来&#xff1b; 原因是在前端拿到records的列表值时可以拿到dictText的字典&#xff0c;但是线上服务器没有dictText的值&#xff1b; …
阅读更多...
对称二叉树[简单]

对称二叉树[简单]

优质博文&#xff1a;IT-BLOG-CN 一、题目 给你一个二叉树的根节点root&#xff0c; 检查它是否轴对称。 示例 1&#xff1a; 输入&#xff1a;root [1,2,2,3,4,4,3] 输出&#xff1a;true 示例 2&#xff1a; 输入&#xff1a;root [1,2,2,null,3,null,3] 输出&#xf…
阅读更多...
YOLOv5改进 | Conv篇 | 利用YOLOv10提出的SCDown魔改YOLOv5进行下采样（附代码 + 结构图 + 添加教程）

YOLOv5改进 | Conv篇 | 利用YOLOv10提出的SCDown魔改YOLOv5进行下采样（附代码 + 结构图 + 添加教程）

一、本文介绍 本文给大家带来的改进机制是利用YOLOv10提出的SCDown魔改YOLOv5进行下采样&#xff0c;其是更高效的下采样。具体而言&#xff0c;其首先利用点卷积调整通道维度&#xff0c;然后利用深度卷积进行空间下采样。这将计算成本减少到和参数数量减少到。同时&#xff…
阅读更多...
5.透明效果

5.透明效果

实时渲染中要实现透明效果&#xff0c;通常会在渲染模型时控制它的透明通道&#xff08;Alpha channel&#xff09;。 当一个物体被渲染到屏幕上时&#xff0c;每个片元除了颜色和深度值之外&#xff0c;它还有另一个属性—透明度。 当透明度为1时&#xff0c;表示该像素是完…
阅读更多...
信息系统项目管理师0141：产品范围和项目范围（9项目范围管理—9.1管理基础—9.1.1产品范围和项目范围）

信息系统项目管理师0141：产品范围和项目范围（9项目范围管理—9.1管理基础—9.1.1产品范围和项目范围）

点击查看专栏目录 文章目录 第9章 项目范围管理9.1 管理基础9.1.1 产品范围和项目范围 第9章 项目范围管理 项目范围管理包括确保项目做且只做所需的全部工作&#xff0c;以成功完成项目。项目范围管理主要在于定义和控制哪些工作应该包括在项目内&#xff0c;哪些不应该包含在…
阅读更多...
Golang | Leetcode Golang题解之第131题分割回文串

Golang | Leetcode Golang题解之第131题分割回文串

题目&#xff1a; 题解&#xff1a; func partition(s string) (ans [][]string) {n : len(s)f : make([][]int8, n)for i : range f {f[i] make([]int8, n)}// 0 表示尚未搜索&#xff0c;1 表示是回文串&#xff0c;-1 表示不是回文串var isPalindrome func(i, j int) int8…
阅读更多...
数据结构与算法之Floyd弗洛伊德算法求最短路径

数据结构与算法之Floyd弗洛伊德算法求最短路径

目录 前言 Floyd弗洛伊德算法 定义 步骤 一、初始化 二、添加中间点 三、迭代 四、得出结果 时间复杂度 代码实现 结束语 前言 今天是坚持写博客的第18天&#xff0c;希望可以继续坚持在写博客的路上走下去。我们今天来看看数据结构与算法当中的弗洛伊德算法。 Flo…
阅读更多...
如何学习SQL？YouTube近百万粉丝技术频道的学习路径图。

如何学习SQL？YouTube近百万粉丝技术频道的学习路径图。

大家好&#xff0c;我是王有志&#xff0c;一个分享硬核 Java 技术的金融摸鱼侠&#xff0c;欢迎大家加入 Java 人自己的交流群“共同富裕的 Java 人”。 ByteByteGo 频道在 5 月 30 日的通信邮件中提到了“How to Learn SQL”这一主题&#xff0c;并给出了一张详细的学习路径…
阅读更多...
python——网络编程

python——网络编程

流程图 面向连接的套接字 面向连接的通信提供序列化的、可靠的和不重复的数据交付&#xff0c;而没有记录边界。主要的协议是传输控制协议&#xff08;TCP&#xff09;; TCP套接字&#xff0c;在python中&#xff0c;必须使用SOCK_STREAM作为套接字类型 tcp的特点 面向连接…
阅读更多...
使用GitHub托管静态网页

使用GitHub托管静态网页

前言​&#xff1a; 如果没有服务器&#xff0c;也没有域名&#xff0c;又想部署静态网页的同学&#xff0c;那就可以尝试使用GitHub托管自己的网页​。 正文&#xff1a; 首先要有自己的GitHub的账号&#xff0c;如果没有可以自己搜索官网进行注册登录&#xff0c;国内对Gi…
阅读更多...
深入了解 C 语言 Bug

深入了解 C 语言 Bug

目录 一、引言二、Bug的定义三、Bug的由来四、Bug的影响五、应对 Bug 的方法六、结论 一、引言 1、在 C 语言的编程世界中&#xff0c;Bug 是一个我们无法回避的话题。 2、Bug&#xff0c;简单来说&#xff0c;就是程序中存在的错误或缺陷。它可以表现为程序运行结果的异常、崩…
阅读更多...
容器运行nslookup提示bash: nslookup: command not found【笔记】

容器运行nslookup提示bash: nslookup: command not found【笔记】

在容器中提示bash: nslookup: command not found&#xff0c;表示容器中没有安装nslookup命令。 可以通过以下命令安装nslookup&#xff1a; 对于基于Debian/Ubuntu的容器&#xff0c;使用以下命令&#xff1a; apt-get update apt-get install -y dnsutils对于基于CentOS/R…
阅读更多...
最新文章

Copyright @ 2022~2023