【数据结构】树与森林(树的存储结构、森林与二叉树的转化、树与森林的遍历)

这篇具有很好参考价值的文章主要介绍了【数据结构】树与森林(树的存储结构、森林与二叉树的转化、树与森林的遍历)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

  1. 树与二叉树知识点文章: 【数据结构】树与二叉树(递归法先序、中序、后序、层次遍历二叉树、二叉树的建立以及求树高的方法)
  2. 二叉树遍历算法的应用: 【数据结构】树与二叉树遍历算法的应用(求叶子节点个数、求树高、复制二叉树、创建二叉树、二叉树存放表达式、交换二叉树每个结点的左右孩子)

树和森林

树的非顺序存储映像:

  1. 双亲表示法
  2. 孩子表示法
  3. 树的二叉链表(孩子-兄弟)存储表示法

树的存储结构

一、树的双亲表示法:

祖先(双亲)
定义:用一维数组存放树中的每一结点的值(data)和双亲位置(parent,逻辑关系)

特点:找祖先易,找子孙难
典型用例:并查集
【数据结构】树与森林(树的存储结构、森林与二叉树的转化、树与森林的遍历),数据结构,线性代数,c++,c语言

//树的双亲表示法
#define MAX_TREE_SIZE 100
typedef struct PTNode {
    int data;
    int parent;  // 双亲位置
} PTNode;

typedef struct {
    PTNode nodes[MAX_TREE_SIZE];
    int  r,n;//r为根节点的位置,n为树中结点的个数
} PTree;

说明:结点存放无顺序要求,根结点不一定存在第一个位置;每个数组元素对应树中一个结点,存放结点的值和双亲位置r—根结点位置,n—树中结点个数。

二、树的孩子表示法

树的孩子表示法:存放树中每个结点的信息、直接后继的地址。

根据结点直接后继的存放方式,分为:

  1. 定长结点的多重链表:每个结点按照树的度设置孩子指针的数量
  2. 不定长结点的多重链表:每个结点按照结点自身的度设置孩子指针的数量
  3. 孩子单链表:每个结点的孩子结点(直接后继)建一个单链表
方法一:定长结点的多重链表

树的孩子表示法:定长结点的多重链表
(典型:实现树的层次遍历)

定义:链表存放树中的每一结点的值(data)和孩子结点位置(child[i],第i个孩子指针,表示逻辑关系),每个结点的孩子指针的个数=树中孩子最多的结点的孩子个数=树的度.
【数据结构】树与森林(树的存储结构、森林与二叉树的转化、树与森林的遍历),数据结构,线性代数,c++,c语言

1. 特点:结点的结构统一,若树的度为d,则点包含一个数据域,d个孩子指针域.

2. 缺点:空指针多,浪费空间

方法二:不定长结点的多重链表

树的孩子表示法–不定长结点的多重链表

定义:链表存放树中的每一结点的值(data)和孩子结点位置(child[i],逻辑关系),每个结点的孩子指针的个数=该结点的孩子个数=结点的度
【数据结构】树与森林(树的存储结构、森林与二叉树的转化、树与森林的遍历),数据结构,线性代数,c++,c语言

树的度为d,该树的不定长结点的多重链表中结点结构有几种?
树的度为d=3,该树的不定长结点的多重链表中结点结构有4种
总结:树的度为d,该树的不定长结点的多重链表中结点结构有d+1种.

【数据结构】树与森林(树的存储结构、森林与二叉树的转化、树与森林的遍历),数据结构,线性代数,c++,c语言

特点:结点的结构不统一,包含一个数据域,结点的度d, d个孩子指针域
缺点:操作较复杂

方法三:孩子单链表表示法

将每个结点的孩子结点拉成一个单链表
情况一:
结点C在孩子表示法中存了2次
一次出现在下标为2的数组元素中,该数组元素同时保存了C的孩子单链表的头指针。
一次出现在结点A的孩子单链表中。
数据元素存放多次更新操作比较麻烦,更新一个数据元素,所有保存该数据元素的地方均要更新,否则信息不一致

【数据结构】树与森林(树的存储结构、森林与二叉树的转化、树与森林的遍历),数据结构,线性代数,c++,c语言

情况二:
节省存储空间方便更新操作和数据维护,每个数据元素只在数组中存放一次;
在孩子单链表中只存放这个孩子在数组中的位置
如下图所示:
结点A的孩子单链表中第一个孩子结点是下标为1的数组元素(B),第二个孩子是下标为2的数组元素(C),第三个孩子是下标为3的数组元素(D)。
【数据结构】树与森林(树的存储结构、森林与二叉树的转化、树与森林的遍历),数据结构,线性代数,c++,c语言

若既要找子孙,又要找祖先,可将孩子单链表和双亲表示法结合在一起每个数组元素的data域存放数据元素的值,pa域存放双亲结点在数组中的位置,firstchild存其孩子单链表的头指针。

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;

三、树的二叉链表(孩子-兄弟)存储表示法

[fc,data,nb]
【数据结构】树与森林(树的存储结构、森林与二叉树的转化、树与森林的遍历),数据结构,线性代数,c++,c语言

typedef structCSNode{
    ElemType data;
    structCSNode*fc, *nb;
}CSNode, *CSTree;

树中每个结点三部分:
数据域(data),长子指针域(fc),
右邻兄弟指针域(nb)

树和二叉树的转换
• 树以孩子兄弟表示法存,相当于将树转换成二叉树,但此二叉树根结点无右子树
• 好处:借助二叉树的操作实现树的操作

森林与二叉树的转换

⮚ 树采用二叉链表(孩子-兄弟)存储表示法,转换成二叉树
⮚ 森林由多棵树组成: F = ( T 1 , T 2 , … , T n ) F = ( T1, T2, …, Tn ) F=(T1,T2,,Tn); 将其每棵树转换成二叉树 B T 1 , B T 2 , … , B T n BT₁, BT₂, …, BTn BT1,BT2,,BTn;
⮚ 每棵二叉树BT的根的右子树皆为空树,从BTn开始依次将其根结点链为前一棵二叉树的根的右孩子
⮚ 将森林转换成一棵二叉树,森林的操作可借助二叉树的操作完成

森林和二叉树的转换
• 森林以孩子兄弟表示法存,相当于将森林转换成二叉树
• 好处:借助二叉树的操作实现森林的操作

树和森林的遍历

■ 树的遍历可有三条搜索路径:
⮚ 先根(次序)遍历:若树不空,则先访问根结点,然后依次先根遍历各棵子树。
⮚ 后根(次序)遍历:若树不空,则先依次后根遍历各棵子树,然后访问根结点。
⮚ 按层次遍历:若树不空,则自上而下自左至右访问树中每个结点。
【数据结构】树与森林(树的存储结构、森林与二叉树的转化、树与森林的遍历),数据结构,线性代数,c++,c语言

[fc,data,nb]

typedef structCSNode{
    int data;
    structCSNode*fc, *nb;
}CSNode, *CSTree;

树中每个结点三部分:数据域(data),长子指针域(fc),右邻兄弟指针域(nb)

先根(次序)遍历

对应二叉树的先序

//树的孩子兄弟表示法
typedef structCSNode{
    ElemType data;
    structCSNode*fc, *nb;
}CSNode, *CSTree;

//二叉树的二叉链表表示法
typedef struct BiTNode {
    ElemType  data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

void PreorderTraverse(CSTree T){
	SeqStack s ;	
	s.top=-1; 
	p = T;
	while(p){
		while(p){
			printf(%c”,p->data);
			if(p->nb)
				if(s.top==MAX-1) exit (0);
				else s.data[++s.top]=p->nb;
			p =p->fc;
		}
		if (s.top!=-1) p=s.data[s.top--];
	}
}

后根(次序)遍历(待补充)

对应二叉树的中序

按层次遍历(待补充)

叶子结点
判断是否为子孩子 fc是否为空
p->fc == NULL

森林由三部分构成:
1.森林中第一棵树的根结点;
2.森林中第一棵树的子树森林;
3.森林中其它树构成的森林。

  1. 后根(次序)遍历与对应的二叉树的中序遍历相同
  2. 先根(次序)遍历与对应的二叉树的先序遍历相同
  3. 森林的先序遍历—对应二叉树的先序遍历
  4. 森林的中序遍历—对应二叉树的中序遍历

感谢阅读!!!文章来源地址https://www.toymoban.com/news/detail-850267.html

  1. 树与二叉树知识点文章: 【数据结构】树与二叉树(递归法先序、中序、后序、层次遍历二叉树、二叉树的建立以及求树高的方法)
  2. 二叉树遍历算法的应用: 【数据结构】树与二叉树遍历算法的应用(求叶子节点个数、求树高、复制二叉树、创建二叉树、二叉树存放表达式、交换二叉树每个结点的左右孩子)

到了这里,关于【数据结构】树与森林(树的存储结构、森林与二叉树的转化、树与森林的遍历)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 《数据结构C语言版》——树、森林与二叉树的转换(超详图解)

    哈喽!这里是一只派大鑫,不是派大星。本着基础不牢,地动山摇的学习态度,从基础的C语言语法讲到算法再到更高级的语法及框架的学习。更好地让同样热爱编程(或是应付期末考试 狗头.jpg)的大家能够在学习阶段找到好的方法、路线,让天下没有难学的程序(只有秃头的程

    2024年02月10日
    浏览(38)
  • C/C++数据结构之深入了解树与二叉树:概念、存储结构和遍历

    树是一种常见的数据结构,它在计算机科学和数学中都有广泛的应用。树结构的最简单形式是二叉树,本文将深入探讨树和二叉树的概念、存储结构以及二叉树的遍历,并提供一些实际的代码示例来帮助理解这些概念。 树 (Tree) 树是一种层次性数据结构,由节点(或称为顶点

    2024年02月06日
    浏览(51)
  • 探索树形数据结构,通识树、森林与二叉树的基础知识(专有名词),进一步利用顺序表和链表表示、遍历和线索树形结构

      结点之间有分支,具有层次关系 树的定义 : 树 (tree)是n(n≥0)个有限集。 若n = 0,则称为空树; 若n 0,则它满足如下两个条件: 有且仅有一个特定的称为根(Root)的结点; 其余结点可分为m(m≥0)个互不相交的有限集T1,T2,T3,.....,Tm,其中每一个集合本身又是一棵树,并称为根的

    2024年02月01日
    浏览(53)
  • 【数据结构】树与二叉树

    树是一种 非线性的数据结构 ,它是由n(n=0)个有限结点组成一个具有层次关系的集合。 把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的 。它具有以下的特点: 有一个特殊的结点,称为根结点,根结点没有前驱结点 除根结点外,其余结点被分

    2024年02月11日
    浏览(45)
  • [数据结构] 树与二叉树

    树是由 (n(n geq 0)) 个节点组成的有限集。当 (n = 0) 时,称为空树。 任意一棵非空树应满足以下两点: (1)有且仅有一个特定的称为根的节点; (2)当 (n 1) 时,其余节点可分为 (m(m0)) 个互不相交的有限集 (T_1, T_2, dots, T_m) ,其中每个集合本身又是一棵树,称为根的

    2024年03月09日
    浏览(41)
  • 数据结构--树与二叉树

    树的定义 树是n(n =0)个节点的有限集。当n=0 时,称为空树 在任意一棵非空树中应满足 有且仅有一个特定的称为根的结点 当n1 时,其余节点可分为m(m0) 个互不相交的有限集T1,T2……Tm,其中每个集合本身又是一棵树,并且称为根的子树 树是一种逻辑结构,也是一种分层结构 树的

    2024年02月22日
    浏览(44)
  • 【数据结构】树与二叉树(中)

    目录 前言: 一、顺序存储结构: 二、堆: 1.堆的性质: 2.堆的性质: 3.堆的实现: Ⅰ.堆的初始化:  Ⅱ.堆的插入(含向上调整):  Ⅲ.堆的删除(含向下调整算法): Ⅳ.取堆顶的数据: Ⅴ.堆中的数据个数: Ⅵ.堆的判空:  Ⅶ.堆的销毁: 总结:         上篇文章中,

    2024年02月16日
    浏览(46)
  • 数据结构_树与二叉树

    目录 1. 树的基本概念 1.1 树的定义 1.2 基本术语 1.3 树的性质 1.4 相关练习 2. 二叉树的概念 2.1 二叉树的概念及其主要特性 2.2 二叉树的存储结构 2.2.1 顺序存储结构 2.2.2 链式存储结构 2.3 相关练习 3. 二叉树的遍历和线索二叉树 3.1 二叉树的遍历 3.1.1 先序遍历 3.1.2 中序遍历 3.1

    2024年02月04日
    浏览(46)
  • 数据结构与算法——树与二叉树

    😊各位小伙伴久等了,本专栏新文章出炉了!!! 我又回来啦,接下来的时间里,我会持续把数据结构与算法专栏更新完。 👉树型结构👈 是一类重要的 ✍非线性数据结构 ,其中以树和二叉树最为常用,直观来看,树是以分支关系定义的层次结构。树型结构在客观世界中

    2024年02月11日
    浏览(45)
  • 【数据结构与算法】树与二叉树

    除了之前我们讲的栈、队列、链表等线性结构,数据结构中还有着一对多的 非线性结构 ——— 树 。 树是有 n 个结点组成的有限集,当n=0时为空树,在任意一颗非空树中,有且仅有一个 特定的根结点 ;当n1时,其余结点又可以分为一棵树,称为根的 子树 。 如下图所示: A为

    2023年04月09日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包