数据结构第十四天(树的存储/双亲表示法)

目录

前言

概述

接口: 

源码:

测试函数:

运行结果:

往期精彩内容


前言

孩子,一定要记得你的父母啊!!!

哈哈,今天开始学习树结构中的双亲表示法,让孩子记得归家的路,记得自己的父母是谁😉😉😉

概述

树的双亲表示法是一种常用的树的存储结构,它通过使用一个数组来表示树的节点,并且每个节点都包含了其父节点的索引信息。

在双亲表示法中,树的每个节点都包含以下两个信息:

  1. 节点的数据域:用来存储节点的数据。
  2. 父节点索引:用来存储该节点的父节点在数组中的索引。

每一个节点我们可以这样表示:

其中 data 是数据域,存储结点的数据信息。而 parent 是指针域,存储该结点的双亲在数组中的下标。 

通过这种方式,我们可以方便地找到一个节点的父节点,并且能够实现树的遍历和操作。

使用双亲表示法可以有效地存储树的结构,并且可以方便地进行遍历和操作。但双亲表示法的缺点是,它不太适合表示具有大量节点的树,因为节点之间的关系需要通过数组来表示,可能会浪费一定的空间。
 

接口: 

void addNode(char* data, char* parent);
void getParent(char* dest, char* child);
bool bTrueIfEmptyTree();
bool bTrueIfFullFilledTree();

源码:

#include<string.h>
#include<stdio.h>
#include <malloc.h>
class TREE{
private:
	
	struct PARENTSTRUCT
	{
		char data[15];
		struct PARENTSTRUCT* parent;
	};
	struct  PARENTSTRUCT* index[15];
	unsigned int currentSite = 0;

struct  PARENTSTRUCT* findParent(char* child);	

public:

void addNode(char* data, char* parent);
void getParent(char* dest, char* child);
bool bTrueIfEmptyTree();
bool bTrueIfFullFilledTree();
};
struct  TREE::PARENTSTRUCT* TREE::findParent(char* child)
{
	for (int i = 0; i < currentSite; ++i)
	{
		if (strcmp(child, index[i]->data) == 0)
		{
			return index[i]->parent;
		}
	}

}
void TREE::addNode(char* data, char* parent)
{
	index[currentSite] = (PARENTSTRUCT*)malloc(sizeof(PARENTSTRUCT));
	strcpy(index[currentSite]->data, data);
	if (parent == nullptr)
	{
		index[currentSite]->parent = nullptr;
	}
	else{
		for (int i = 0; i < currentSite; ++i)
		{
			if (strcmp(parent, index[i]->data) == 0)
			{
				index[currentSite]->parent = index[i];
			}
		}
		
	}
	currentSite++;
	return;
}
bool TREE::bTrueIfFullFilledTree()
{
	if (currentSite == 15)
	{
		return true;
	}
	else{
		return false;
	}
}
void TREE::getParent(char* dest, char* child)
{
	PARENTSTRUCT* ptr = findParent(child);
	if (ptr != nullptr)
	{
		strcpy(dest, ptr->data);
	}
	else{
		strcpy(dest, "抱歉,此为根");
	}
	return;
}

由下图数据来建一棵树,由此进行测试 

测试函数:

#include<stdio.h>
#include<iostream>
using namespace std;
#include"TREE.h"//上面提到的源码函数头文件
#include<windows.h>
int main()
{

TREE tree;
	tree.addNode("A", nullptr);
	tree.addNode("B","A");
	tree.addNode("C", "A");
	tree.addNode("D", "B");
	tree.addNode("G", "D");
	tree.addNode("H", "D");
	tree.addNode("I", "D");
	tree.addNode("E", "C");
	tree.addNode("F", "C");
	tree.addNode("J", "E");
	char buff[40];
	tree.getParent(buff, "H");
	cout << "输出H的父母:" << buff << endl;
	tree.getParent(buff, "J");
	cout << "输出J的父母:" << buff << endl;
	system("pause");
	return 0;
}

运行结果:

往期精彩内容

数据结构第一天(生成1000以内的随机数自动填充数组)

数据结构第二天(直接插入排序/内存申请/指针操作)

数据结构第三天(折半插入排序)

数据结构第四天(希尔排序)

数据结构第五天(冒泡排序)

数据结构第六天(快速排序)

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

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

相关文章

SB+AVL——二刷错误总结

码云 SBTree insert中对头节点的处理 void Insert(int val){Node* node new Node(val);// 找插入位置if (_root nullptr){_root node;return;}else{Node* pre _root, *head _root;while (head){pre head;if (head->_val < val) head head->_right;else if (h…

P1259 黑白棋子的移动题解

题目 有2n个棋子排成一行&#xff0c;开始为位置白子全部在左边&#xff0c;黑子全部在右边&#xff0c;如下图为n5的情况&#xff1a; 移动棋子的规则是&#xff1a;每次必须同时移动相邻的两个棋子&#xff0c;颜色不限&#xff0c;可以左移也可以右移到空位上去&#xff0c…

【C++】内存管理方式--new/delete

&#x1f490; &#x1f338; &#x1f337; &#x1f340; &#x1f339; &#x1f33b; &#x1f33a; &#x1f341; &#x1f343; &#x1f342; &#x1f33f; &#x1f344;&#x1f35d; &#x1f35b; &#x1f364; &#x1f4c3;个人主页 &#xff1a;阿然成长日记 …

Repo命令使用实例(三十八)

简介&#xff1a; CSDN博客专家&#xff0c;专注Android/Linux系统&#xff0c;分享多mic语音方案、音视频、编解码等技术&#xff0c;与大家一起成长&#xff01; 优质专栏&#xff1a;Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 优质专栏&#xff1a;多媒…

(01)Hive的相关概念——架构、数据存储、读写文件机制

目录 一、架构及组件介绍 1.1 Hive整体架构 1.2 Hive组件 1.3 Hive数据模型&#xff08;Data Model&#xff09; 1.3.1 Databases 1.3.2 Tables 1.3.3 Partitions 1.3.4 Buckets 二、Hive读写文件机制 2.1 SerDe 作用 2.2 Hive读写文件流程 2.2.1 读取文件的过程 …

BUGKU-WEB 你必须让他停下

题目描述 题目截图如下&#xff1a; 进入场景看看&#xff1a; 解题思路 图片会消失,那应该是使用了js来控制根据提示,那就是要停止js才会看到flag (也就是要抓包,不要陷入停止js的思维) 相关工具 F12大法Burp Suit抓包工具 解题步骤 出现图片的时候,源码中确实出现…

ICLR 2023#Learning to Compose Soft Prompts for Compositional Zero-Shot Learning

组合零样本学习&#xff08;CZSL&#xff09;中Soft Prompt相关工作汇总&#xff08;一&#xff09; 文章目录 组合零样本学习&#xff08;CZSL&#xff09;中Soft Prompt相关工作汇总&#xff08;一&#xff09;ICLR 2023#Learning to Compose Soft Prompts for Compositional…

Android之Android.bp文件格式语法(一百八十六)

简介&#xff1a; CSDN博客专家&#xff0c;专注Android/Linux系统&#xff0c;分享多mic语音方案、音视频、编解码等技术&#xff0c;与大家一起成长&#xff01; 优质专栏&#xff1a;Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 优质专栏&#xff1a;多媒…

力扣hot3--并查集+哈希

第一想法是排个序然后遍历一遍&#xff0c;but时间复杂度就超啦 并查集居然与哈希结合了&#xff08;&#xff09; 已经好久没用过并查集了&#xff0c;&#xff0c;&#xff0c;我们用哈希表f_node中来记录原结点的父节点&#xff0c;其中key是原结点&#xff0c;value是父节点…

Github项目推荐-Tiny-Rdm

项目地址 GitHub - tiny-craft/tiny-rdm: A Modern Redis GUI Client 项目简述 一个开源的Redis管理工具&#xff0c;有漂亮的界面和丰富的功能。使用的编程语言如下 项目截图

【Qt】环境安装与初识

目录 一、Qt背景介绍 二、搭建Qt开发环境 三、新建工程 四、Qt中的命名规范 五、Qt Creator中的快捷键 六、QWidget基础项目文件详解 6.1 .pro文件解析 6.2 widget.h文件解析 6.3 widget.cpp文件解析 6.4 widget.ui文件解析 6.5 main.cpp文件解析 七、对象树 八、…

对什么都不感兴趣,怎么办?

这大概是现代社会&#xff0c;最为常见的都市病。 很多人大抵都明白&#xff1a;好的生活是什么样的呢&#xff1f;要有一个大目标&#xff0c;再分拆成一个个小目标&#xff0c;每天朝着目标前进&#xff0c;看着自己的进步和成长&#xff0c;转化为成就感和动力 —— 对不对&…

揭秘Angular世界的奥秘:全面提升你的前端开发技能!

介绍&#xff1a;Angular是一个由Google维护的开源JavaScript框架&#xff0c;专为构建Web应用程序而设计&#xff0c;特别适合开发大型单页应用&#xff08;SPA&#xff09;。以下是对Angular的详细介绍&#xff1a; 技术栈&#xff1a;Angular使用HTML作为模板语言&#xff0…

C++集群聊天服务器 nginx+redis安装 笔记 (中)

一、nginx安装 nginx: download 下载nginx安装包 hehedalinux:~/package$ tar -zvxf nginx-1.24.0.tar.gz nginx-1.24.0/ nginx-1.24.0/auto/ nginx-1.24.0/conf/ nginx-1.24.0/contrib/ nginx-1.24.0/src/ nginx-1.24.0/configure nginx-1.24.0/LICENSE nginx-1.24.0/README…

言语残疾和言语残疾分级

言语残疾和言语残疾分级 言语残疾&#xff0c;指各种原因导致的不同程度的言语障碍&#xff0c;经治疗一年以上不愈或病程超过两年&#xff0c;而不能或难以进行正常的言语交流活动&#xff0c;以致影响其日常生活和社会参与。包括&#xff1a;失语、运动性构音障碍、器质性构音…

黑马程序员——移动Web——day02

目录 空间转换 空间转换简介平移视距旋转左手法则rotate3d-了解立体呈现案例-3d导航缩放动画 动画实现步骤animation复合属性animation拆分写法案例-走马灯精灵动画多组动画综合案例-全名出游 背景云彩位置和动画文字动画 1.空间转换 空间转换简介 空间&#xff1a;是从坐标…

ITK 图像分割(一):阈值ThresholdImageFilter

效果&#xff1a; Video: 区域增加分割 1、itkThresholdImageFilter 该类的主要功能是通过设置低阈值、高阈值或介于高低阈值之间&#xff0c;则将图像值输出为用户指定的值。 如果图像值低于、高于或介于设置的阈值之间&#xff0c;该类就将图像值设置为用户指定的“外部”值…

山西电力市场日前价格预测【2024-02-10】

日前价格预测 预测说明&#xff1a; 如上图所示&#xff0c;预测明日&#xff08;2024-02-10&#xff09;山西电力市场全天平均日前电价为126.73元/MWh。其中&#xff0c;最高日前电价为302.95元/MWh&#xff0c;预计出现在08:15。最低日前电价为0.00元/MWh&#xff0c;预计出…

Stable Diffusion之最全详解图解

Stable Diffusion之最全详解图解 1. Stable Diffusion介绍1.1 研究背景1.2 学术名词 2.Stable Diffusion原理解析2.1 技术架构2.2 原理介绍扩散过程 3.1 Diffusion前向过程3.2 Diffusion逆向&#xff08;推断&#xff09;过程 1. Stable Diffusion介绍 Stable Diffusion是2022…

分布式文件系统 SpringBoot+FastDFS+Vue.js【一】

分布式文件系统 SpringBootFastDFSVue.js【一】 一、分布式文件系统1.1.文件系统1.2.什么是分布式文件系统1.3.分布式文件系统的出现1.3.主流的分布式文件系统1.4.分布式文件服务提供商1.4.1.阿里OSS1.4.2.七牛云存储1.4.3.百度云存储 二、fastDFS2.1.fastDSF介绍2.2.为什么要使…