【数据结构】09.树与二叉树

一、树的概念与结构

1.1 树的概念

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

  • 根结点：根节点没有前驱结点。
  • 除根节点外，其余结点被分成是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。
  • 因此，树是递归定义的。

在这里插入图片描述

1.2 树的相关概念

在这里插入图片描述

  • 节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为4
  • 叶节点或终端节点：度为0的节点称为叶节点； 如上图：B、F、G、D、H节点为叶节点
  • 非终端节点或分支节点：度不为0的节点； 如上图：A、C、E节点为分支节点
  • 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点
  • 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点
  • 兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点
  • 树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为4
  • 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
  • 树的高度或深度：树中节点的最大层次； 如上图：树的高度为3
  • 堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：F、G互为兄弟节点
  • 节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
  • 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
  • 森林：由m棵互不相交的树的集合称为森林；

1.3 树的表示法

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既要保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。

在介绍以下存储结构的过程中，我们都以下面这个树为例子。在这里插入图片描述

1.3.1 双亲表示法

我们假设以一组连续空间存储树的结点，同时在每个结点中，附设一个指示器指示其双亲结点到链表中的位置。也就是说，每个结点除了知道自已是谁以外，还知道它的双亲在哪里。
在这里插入图片描述
其中data是数据域，存储结点的数据信息。而parent是指针域，存储该结点的双亲在数组中的下标。
以下是我们的双亲表示法的结点结构定义代码。

/*树的双亲表示法结点结构定义*/
#define MAX_TREE_SIZE 100
typedef int TElemType;	//树结点的数据类型，目前暂定为整型
/*结点结构*/
typedef struct TreeNode
{
	TElemType data;	//结点数据
	int parent;	//双亲位置
}TreeNode;
/*树结构*/
typedef struct
{
	TreeNode nodes[MAX_TREE_SIZE];	//结点数组
	int r, n;	//根的位置和结点数
}PTree;

这样的存储结构，我们可以根据结点的parent 指针很容易找到它的双亲结点，所用的时间复杂度为0(1)，直到parent为-1时，表示找到了树结点的根。可如果我们要知道结点的孩子是什么，对不起，请遍历整个结构才行。

1.3.2 孩子兄弟表示法

刚才我们分别从双亲的角度和从孩子的角度研究树的存储结构，如果我们从树结点的兄弟的角度又会如何呢?当然，对于树这样的层级结构来说，只研究结点的兄弟是不行的，我们观察后发现，任意一棵树， 它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。 因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。

在这里插入图片描述

/*树的孩子兄弟表示法结构定义*/
typedef struct TreeNode
{
	TElemtype data;
	struct TreeNode *firstchild, *rightsib;
} TreeNode,* pTreeNode;

1.4 树在实际中的应用

在这里插入图片描述

二、二叉树的概念及结构

2.1概念

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

  • 或者为空
  • 由一个根节点加上两棵别称为左子树和右子树的二叉树组成

在这里插入图片描述

从上图可以看出：

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

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

2.2 特殊的二叉树

  1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是2^k-1 ，则它就是满二叉树。
  2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
    在这里插入图片描述

2.3 二叉树的性质

  1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点
  2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是 2^h-1
  3. 对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为 n2,则有 n0＝n2 ＋1
  4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=log (n+1) (ps： 是log以2为底，n+1为对数)
  5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：
    • 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
    • 若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子
    • 若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子

2.4 二叉树的存储结构

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

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

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

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

四、二叉树的链式结构及其实现

4.1 二叉树的遍历

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

4.1.1 前序遍历

//根 左子树 右子树
void PrevOrder(pTreeNode root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	printf("%d ", root->val);
	PrevOrder(root->left);
	PrevOrder(root->right);
}

下图为递归过程：
在这里插入图片描述

4.1.2 中序遍历

//左子树 根 右子树
void InOrder(pTreeNode root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	InOrder(root->left);
	printf("%d ", root->val);
	InOrder(root->right);
}

下面为递归过程：
在这里插入图片描述

4.1.3 后序遍历

//左子树 右子树 根
void PostOrder(pTreeNode root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

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

下面为递归过程：
在这里插入图片描述

4.2.4 层序遍历

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

我们这里介入队列来进行二叉树的前序遍历。

// 层序遍历
void LevelOrder(pTreeNode root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		pTreeNode front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL)
		{
			printf("NULL ");
		}
		else
		{
			printf("%d ", front->val);
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}
	}
	QueueDestory(&q);
}

4.1 二叉树的创建与销毁

二叉树的创建与销毁，我们以二叉树遍历为例题。

//二叉树的创建
struct TreeNode* Creat(char* arr,int n,int* i)
{ 
    if(*i<n&&arr[*i]=='#')
    {
        (*i)++;
        return NULL;
    }
    
    TreeNode* newnode=(TreeNode*)malloc(sizeof(TreeNode));
    newnode->left=NULL;
    newnode->right=NULL;

    newnode->val=arr[(*i)++];
    newnode->left=Creat(arr,n,i);
    newnode->right=Creat(arr,n,i);
    
    return newnode;
}

//二叉树的销毁
void TreeDestroy(struct TreeNode* root)
{
    if(root==NULL)
    {
        return;
    }
    TreeDestroy(root->left);
    TreeDestroy(root->right);
    free(root);
}

4.3 二叉树的其他操作

以下的操作均是沿着遍历的思想展开的。

// 二叉树节点个数
int TreeSize(pTreeNode root)
{
	if (root == NULL)
	{
		return 0;
	}
	return TreeSize(root->left) + TreeSize(root->right) + 1;
}

// 二叉树叶子节点个数
int TreeLeafSize(pTreeNode root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

// 二叉树第k层节点个数
int TreeLevelKSize(pTreeNode root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return TreeLevelKSize(root->left, k - 1) + TreeLevelKSize(root->right, k - 1);
}

// 二叉树查找值为x的节点
pTreeNode TreeFind(pTreeNode root, TreeDataType x)
{

	if (root == NULL)
	{
		return NULL;
	}
	//相等就返回
	if (root->val == x)
		return root;
	//找左子树
	pTreeNode left=TreeFind(root->left, x);
	if (left)
	{
		return left;
	}
	//找右子树
	pTreeNode right = TreeFind(root->right, x);
	if (right)
	{
		return right;
	}
	//都没找到
	return NULL;
}

//二叉树的高度
int TreeHeight(pTreeNode root)
{
	if (root == NULL)
	{
		return 0;
	}
	int max_left = TreeHeight(root->left) ;
	int max_right = TreeHeight(root->right);
	return max_left > max_right ? max_left + 1 : max_right + 1;
}

//判断是否是完全二叉树
bool TreeComplete(pTreeNode root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		pTreeNode front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL)
		{
			break;
		}
		else
		{
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}
	}
	while (!QueueEmpty(&q))
	{
		pTreeNode front = QueueFront(&q);
		QueuePop(&q);
		if (front)
		{
			QueueDestory(&q);
			return false;
		}
	}
	QueueDestory(&q);
	return true;
}

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

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

相关文章

webGL可用的14种3D文件格式，但要具体问题具体分析。

webGL可用的14种3D文件格式，但要具体问题具体分析。

hello&#xff0c;我威斯数据&#xff0c;你在网上看到的各种炫酷的3d交互效果&#xff0c;背后都必须有三维文件支撑&#xff0c;就好比你网页的时候&#xff0c;得有设计稿源文件一样。WebGL是一种基于OpenGL ES 2.0标准的3D图形库&#xff0c;可以在网页上实现硬件加速的3D图…
阅读更多...
阶段三：项目开发---大数据开发运行环境搭建:任务2：安装配置ZooKeeper

阶段三：项目开发---大数据开发运行环境搭建:任务2：安装配置ZooKeeper

任务描述 知识点&#xff1a;安装配置ZooKeeper 重 点&#xff1a; 安装配置ZooKeeper 难 点&#xff1a;无 内 容&#xff1a; ZooKeeper是一个开源分布式协调服务&#xff0c;其独特的Leader-Follower集群结构&#xff0c;很好的解决了分布式单点问题。目前主要用于诸…
阅读更多...
IT之家最新科技热点 | 小米 AI 研究院开创多模态通用模型

IT之家最新科技热点 | 小米 AI 研究院开创多模态通用模型

人不走空 &#x1f308;个人主页&#xff1a;人不走空 &#x1f496;系列专栏&#xff1a;算法专题 ⏰诗词歌赋&#xff1a;斯是陋室&#xff0c;惟吾德馨 目录 &#x1f308;个人主页&#xff1a;人不走空 &#x1f496;系列专栏&#xff1a;算法专题 ⏰诗词歌…
阅读更多...
一.2.（3）放大电路的图解分析方法和微变等效电路分析方法；

一.2.（3）放大电路的图解分析方法和微变等效电路分析方法；

放大电路的主要分析方法:图解法、微变等效电路法 这里以共射放大电路为例 (1) 图解法: 1.静态分析 首先确定静态工作点Q,然后根据电路的特点,做出直流负载线,进而画出交流负载线,最后,画出各极电流电压的波形。求出最大不失真输出电压。 估算IBQ&#xff0c;然后根据数据手册里…
阅读更多...
二分查找2

二分查找2

1. 山脉数组的峰顶索引&#xff08;852&#xff09; 题目描述&#xff1a; 算法原理&#xff1a; 根据题意我们可以将数组分为两个部分&#xff0c;一个部分是arr[mid-1]<arr[mid]&#xff0c;另一个部分为arr[mid-1]>arr[mid]&#xff0c;此时不难发现我们可以将二分…
阅读更多...
U.S.News发布全美最佳本科AI专业排名

U.S.News发布全美最佳本科AI专业排名

10 加州大学圣迭戈分校 University of California, San Diego UCSD的人工智能项目从事广泛的理论和实验研究&#xff0c;学校的优势领域包括机器学习、不确定性下的推理和认知建模。除了理论学习&#xff0c;UCSD教授非常注重把计算机知识运用到自然语言处理、数据挖掘、计算…
阅读更多...
从模拟到预测，从智能到智慧：数字孪生技术在水库管理中的应用演变，推动水利行业向更高层次的智慧化迈进

从模拟到预测，从智能到智慧：数字孪生技术在水库管理中的应用演变，推动水利行业向更高层次的智慧化迈进

目录 引言 一、数字孪生技术概述 二、数字孪生技术在水库管理中的应用演变 1. 从模拟到预测&#xff1a;构建精准的数字孪生模型 2. 从智能到智慧&#xff1a;实现全面感知与精准控制 3. 推动公众参与与透明化管理 三、数字孪生技术推动水利行业向更高层次的智慧化迈进 …
阅读更多...
密室逃脱——收集版修改测试

密室逃脱——收集版修改测试

一、原版修改 1、导入资源 Unity Learn | 3D Beginner: Complete Project | URP 2、设置Scene 删除SampleScene&#xff0c;打开UnityTechnologies-3DBeginnerComplete下的MainScene 3、降低音量 (1) 打开Hierarchy面板上的Audio降低音量 (2) 打开Prefabs文件夹&#xf…
阅读更多...
推荐3款【王炸级别】的效率软件，免费无广告，你一定要收藏

推荐3款【王炸级别】的效率软件，免费无广告，你一定要收藏

Temp Cleaner Temp Cleaner 是一款专为 Windows 操作系统设计的临时文件清理工具。它的主要功能是安全且快速地清理磁盘上的临时文件和系统缓存&#xff0c;从而释放磁盘空间。该软件体积小巧&#xff08;仅有826KB&#xff09;&#xff0c;并且是无广告的绿色软件&#xff0c;…
阅读更多...
智能交通（3）——Learning Phase Competition for Traffic Signal Control

智能交通（3）——Learning Phase Competition for Traffic Signal Control

论文分享 https://dl.acm.org/doi/pdf/10.1145/3357384.3357900https://dl.acm.org/doi/pdf/10.1145/3357384.3357900 论文代码 https://github.com/gjzheng93/frap-pubhttps://github.com/gjzheng93/frap-pub 摘要 越来越多可用的城市数据和先进的学习技术使人们能够提…
阅读更多...
初学Spring之 AOP 面向切面编程

初学Spring之 AOP 面向切面编程

AOP&#xff08;Aspect Oriented Programming&#xff09;面向切面编程 通过预编译方式和运行期间动态代理实现程序功能的统一维护的一种技术 是面向对象&#xff08;OOP&#xff09;的延续 AOP 在 Spring 中的作用&#xff1a; 1.提供声明式事务 2.允许用户自定义切面 导…
阅读更多...
Java 基础--File - IO流（2）

Java 基础--File - IO流（2）

I/O流 定义 数据从硬盘流向内存为输入流&#xff0c;数据从内存流向硬盘为输出流。输入也叫读取数据&#xff0c;输出也叫写出数据。 IO分类 1.按照数据的流向分为&#xff1a;输入流和输出流 ①输入流&#xff1a;把数据从其他设备上读取到内存中的流 ②输出流&#xff1…
阅读更多...
pdf怎么转换成图片格式文件，pdf文档怎么转换成图片格式

pdf怎么转换成图片格式文件，pdf文档怎么转换成图片格式

在数字化时代&#xff0c;pdf文件转换成图片格式是一种常见的操作&#xff0c;无论是在工作还是日常生活中&#xff0c;我们总会遇到需要将pdf文件转换为图片的需求。这可能是因为图片格式更易于分享、展示或编辑。那么&#xff0c;如何高效地将pdf转换成图片呢&#xff1f;本文…
阅读更多...
240705_昇思学习打卡-Day17-基于 MindSpore 实现 BERT 对话情绪识别

240705_昇思学习打卡-Day17-基于 MindSpore 实现 BERT 对话情绪识别

240705_昇思学习打卡-Day17-基于 MindSpore 实现 BERT对话情绪识别 近期确实太忙&#xff0c;此处仅作简单记录&#xff1a; 模型简介 BERT全称是来自变换器的双向编码器表征量&#xff08;Bidirectional Encoder Representations from Transformers&#xff09;&#xff0c…
阅读更多...
#数据结构 顺序表

#数据结构 顺序表

线性表 顺序表 每种结构都有它存在意义 线性表的顺序存储实现指的是用一组连续的存储单元存储线性表的数据元素。 概念 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性表&#xff0c;一般情况下采用数组存储。在数组上完成数据的增查改删。 逻辑结构&#…
阅读更多...
阶段三：项目开发---大数据开发运行环境搭建:任务8：安装配置Redis

阶段三：项目开发---大数据开发运行环境搭建:任务8：安装配置Redis

任务描述 知识点&#xff1a;安装配置Redis 重 点&#xff1a; 安装配置Redis 难 点&#xff1a;无 内 容&#xff1a; Redis&#xff08;Remote Dictionary Server )&#xff0c;即远程字典服务&#xff0c;是一个开源的使用ANSI C语言编写、支持网络、可基于内存亦可…
阅读更多...
数据结构1:C++实现变长数组

数据结构1:C++实现变长数组

数组作为线性表的一种&#xff0c;具有内存连续这一特点&#xff0c;可以通过下标访问元素&#xff0c;并且下标访问的时间复杂的是O(1)&#xff0c;在数组的末尾插入和删除元素的时间复杂度同样是O(1)&#xff0c;我们使用C实现一个简单的边长数组。 数据结构定义 class Arr…
阅读更多...
【手写数据库内核组件】01 解析树的结构，不同类型的数据结构组多层的链表树，抽象类型统一引用格式

【手写数据库内核组件】01 解析树的结构，不同类型的数据结构组多层的链表树，抽象类型统一引用格式

不同类型的链表 ​专栏内容&#xff1a; postgresql使用入门基础手写数据库toadb并发编程 个人主页&#xff1a;我的主页 管理社区&#xff1a;开源数据库 座右铭&#xff1a;天行健&#xff0c;君子以自强不息&#xff1b;地势坤&#xff0c;君子以厚德载物. 文章目录 不同类型…
阅读更多...
图像基础知识

图像基础知识

图像卷积 卷积（convolution）是通过两个函数f和g生成第三个函数的一种数学算子，表征函数f与g经过翻转和平移的重叠部分的面积。 卷积概念是两个变量在某范围内相乘后求和的结果。图像处理中的卷积概念：数字图像是一个二维的离散信号，对数字图像做卷积操作其实就是利用卷积…
阅读更多...
【帧中继实验-ensp】

【帧中继实验-ensp】

实验要求 在R1上开启一个点对点子接口&#xff0c;用于连接 R1–R2&#xff0c;两端IP地址为12.1.1.x 。开启一个多点子接口 &#xff0c;用于连接R1–R3&#xff0c;R4&#xff0c;两段IP地址为134.1.1.x。 具体DLCI分配和映射关系如下&#xff1a; R1 102 R2 201—动态映射…
阅读更多...
最新文章

Copyright @ 2022~2023