首页 > 其他分享 >树(森林)的定义和画图

树(森林)的定义和画图

时间:2024-09-16 20:49:03浏览次数:11  
标签:存储 定义 孩子 struct 画图 表示法 typedef 双亲 森林

 

目录

代码实现

“双亲表示法”顺序存储

“孩子表示法”链式存储

树的孩子表示法存储 v.s. 图的邻接表存储 v.s. 散列表的拉链法 v.s. 基数排序

“孩子兄弟表示法”链式存储

画图表示

“双亲表示法”

1.树

2.森林

“孩子表示法” 

1.树

2.森林

 “孩子兄弟表示法”

1.树

2.森林

​编辑


写代码:使用“双亲表示法”,定义顺序存储的树(以及森林) 
写代码:使用“孩子表示法”,定义链式存储的树(以及森林) 
对比:树的孩子表示法存储 v.s. 图的邻接表存储 v.s. 散列表的拉链法 v.s. 基数排序。你发现了什么? 
写代码:使用“孩子兄弟表示法”,定义链式存储的树(以及森林) 
自己动手创造,画一个结点总数不少于10的树,并画出对应的“双亲表示法、孩子表示法、孩子兄弟表示法”三种数据结构的示意图 
自己动手创造,画一个至少包含3棵树的森林,并画出对应的“双亲表示法、孩子表示法、孩子兄弟表示法”三种数据结构的示意图 

代码实现

“双亲表示法”顺序存储

#include <stdio.h>

#define MAX_TREE_SIZE 100//树中最多结点数
typedef int ElemType;
typedef struct //树的结点定义 
{
	ElemType data;//数据元素
	int parent;//双亲位置域
	 
}PTNode;
typedef struct
{
	PTNode nodes[MAX_TREE_SIZE];
	int n;
}PTree;
 

“孩子表示法”链式存储

typedef struct CTNode {
    int child;
    struct CTNode *next;
} *ChildPtr;
typedef struct {
    ElemType data;
    ChildPtr firstChild;
} CTBox;
typedef struct {
    CTBox nodes[MAX_TREE_SIZE];
    int n, r;
} CTree;

树的孩子表示法存储 v.s. 图的邻接表存储 v.s. 散列表的拉链法 v.s. 基数排序

存储方法内容相似之处差异之处
孩子表示法

专注于表示树结构中的父子关系。每个节点都有一个指向其孩子节点的链表。便于实现树的各种遍历和操作。

优点:找孩子结点方便

缺点:找双亲结点不方便,需要遍历整个数组

这四种数据结构或算法都涉及到了链表的使用,无论是表示节点关系还是解决冲突。
它们都是为了解决特定问题而设计的,具有各自的优点和适用场景。
孩子表示法和图的邻接表存储是用于表示节点关系的,而散列表的拉链法是用于解决散列冲突的,基数排序则是一种排序算法。
它们的适用场景不同,孩子表示法适用于树结构,图的邻接表适用于图结构,散列表的拉链法适用于散列表中的冲突解决,基数排序适用于整数排序。
它们的实现方式和复杂度也不同,例如基数排序的时间复杂度可以达到O(d*(n+r)),其中d是位数,n是待排序列中记录的个数,r是基数的范围,而孩子表示法和图的邻接表存储则主要关注于空间复杂度和节点关系的表示。
‌图的邻接表

用于表示图结构中的节点关系。
每个节点都有一个指向其相邻节点的链表。
适用于表示复杂的关系网络,如社交网络、交通网络等。

‌散列表的拉链法‌

用于解决散列冲突的一种方法。
当多个关键字散列到同一位置时,将它们链接成一个链表。
提高了散列表的查找效率,但增加了空间复杂度。

‌基数排序‌一种非比较型整数排序算法。
按照低位先排序,然后收集;再按照高位排序,然后再收集的方式进行。
适用于整数排序,特别是当整数范围较大时。

“孩子兄弟表示法”链式存储

#include <stdio.h>

typedef int ElemType;
typedef struct CSNode
{
	ElemType data;//数据域 
	struct CSNode *firstchild,*nextsibling;//第一个孩子和右兄弟指针
	 
}CSNode,*CSTree;

画图表示

“双亲表示法”

1.树

2.森林

 

“孩子表示法” 

1.树

2.森林

 

 “孩子兄弟表示法”

1.树

2.森林

标签:存储,定义,孩子,struct,画图,表示法,typedef,双亲,森林
From: https://blog.csdn.net/snowy_and_sunny/article/details/142306546

相关文章

  • urllib自定义opener对象设置代理IP
    urllib.request.urlopen()源代码——urlopen()在干什么返回opener.open(url,data,timeout)方法的结果 _opener=None#_opener被赋值为Nonedefurlopen(url,data=None,timeout=socket._GLOBAL_DEFAULT_TIMEOUT,*,cafile=None,capath=None,cadefault=......
  • 鸿蒙开发入门day18-自定义扩展
    (创作不易,感谢有你,你的支持,就是我前行的最大动力,如果看完对你有帮助,还请三连支持一波哇ヾ(@^∇^@)ノ)目录自定义扩展能力概述AttributeModifierAttributeUpdaterAttributeModifier概述接口定义行为规格属性设置与修改设置多态样式、事件AttributeUpdater概述接口定......
  • Python编程之旅:定义自定义异常的艺术
    引言在实际开发过程中,我们经常会遇到各种各样的错误情况,如数据类型不符、资源访问失败等。这时候,合理地使用异常处理机制就显得尤为重要了。Python内置了许多异常类,但有时候它们并不能完全满足我们的需求。这时,就需要我们自己动手定义一些特定场景下的异常类型了。定义自定义异常......
  • 【Go开发】Go语言基本语法入门:数据类型与方法定义
    文章目录环境准备一、引言二、Var关键字三、数据类型1.整型符号表示值的范围2.浮点型精度范围性能3.布尔型4.字符串三、变量声明1.指定变量类型2.自动推导类型3.批量声明四、方法定义五、总结环境准备开发环境:MacOSGo版本:goversiongo1.23.1darwin/am......
  • 自定义字体加载
    <!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><metaname="viewport"content="width=device-width,initial-scale=1.0"><title>CustomFontLoading</ti......
  • 「ComfyUI」生图修图神器,自定义调节颜色光暗,更生动更强对比度生图技巧分享!
    今天再给小伙伴们分享一个简单又实用生图神器插件,可以调整整个图像的光暗变化以及颜色变化。原理的话,我们也简单来说下,我们在使用VAE将图像编码为潜在噪声时,VAE解码的值通常在一定范围内,使得最终的潜在噪声只有较小的值范围,而作者做的就是编写了一个函数扩大了这个值的范围......
  • dede怎么添加自定义属性
    在DedeCMS中添加自定义属性可以通过修改数据库表来实现。以下是具体的步骤:登录数据库管理工具:登录到你的数据库管理工具,如phpMyAdmin。修改dede_archives表:寻找dede_archives表,并打开其结构。找到flag字段,这是一个枚举类型字段,用于存储文档的一些标志。编辑flag字段,......
  • 字典的定义及其应用
    在Python中,字典(dictionary)是一种可变的、无序的容器数据类型,用于存储键值对(key-valuepairs)。一、定义字典使用花括号 {} 和冒号 : 来定义字典,键和值之间用冒号分隔,不同的键值对之间用逗号分隔。例如:   my_dict= {'name': 'Alice', 'age': 30, 'city': ......
  • C++ 定义静态成员 static 关键字不能在定义出重复出现
    定义静态成员和其他的成员函数一样,我们既可以在类的内部也可以在类的外部定义静态成员函数。当在类的外部定义静态成员时,不能重复static关键字,该关键字只出现在类内部的声明语句:voidAccount::rate(doublenewRate){interestRate=newRate;}Note:和类的所有成员一样,当我......
  • 优化批处理流程:自定义BatchProcessorUtils的设计与应用
    优化批处理流程:自定义BatchProcessorUtils的设计与应用| 原创作者/编辑:凯哥Java                    | 分类:个人小工具类在我们开发过程中,处理大量的数据集是一项常见的任务。特别是在数据库操作、文件处理或者任何需要对大量数据进行分......