【数据结构】树的定义、树的存储结构

文档中心

💟作者简介：大家好呀！我是路遥叶子，大家可以叫我叶子哦！❣️
📝个人主页：【路遥叶子的博客】
🏆博主信息：四季轮换叶，一路招摇胜！
        专栏

       【安利Java零基础】

       【数据结构-Java语言描述】

🐋希望大家多多支持😘一起进步呀！~❤️
🌈若有帮助，还请【关注➕点赞➕收藏】，不行的话我再努力努力呀！💪
————————————————
⚡版权声明：本文由【路遥叶子】原创、在CSDN首发、需要转载请联系博主。
🍁想寻找共同成长的小伙伴，请点击【Java全栈开发社区】

前言

提到存储结构，可以很自然的想到顺序存储结构和链式存储结构两种。

之前介绍的所有的数据结构都是线性存储结构。本章所介绍的树结构是一种非线性存储结构，存储的是具有“一对多”关系的数据元素的集合。

图 1(A) 是使用树结构存储的集合 {A,B,C,D,E,F,G,H,I,J,K,L,M} 的示意图。对于数据 A 来说，和数据 B、C、D 有关系；对于数据 B 来说，和 E、F 有关系。这就是“一对多”的关系。

将具有“一对多”关系的集合中的数据元素按照图 1（A）的形式进行存储，整个存储形状在逻辑结构上看，类似于实际生活中倒着的树（图 1（B）倒过来），所以称这种存储结构为“树型”存储结构。

💚❤️💙💚❤️💙💚❤️💙💚❤️💙💚❤️💙💚❤️💙💚❤️💙💚❤️💙💚❤️💙💚❤️💙

🐋树的定义

🌲树的定义

树（Tree）是 n（n>=0）个结点的有限集。n=0时称为空树。在任意一颗非空树中：

有且仅有一个特定的称为根（root）的结点；

当n>1时，其余结点可分为m(m>0)个互补交互的有限集T1、T2...Tm，其中每一个集合本身又是一棵树，并称为根的子树（SubTree）。

🌲树的特点

n>0时，根节点是唯一的，不可能存在多个根节点。数据结构中的树只有一个根节点。

m>0时，子树的个数没有限制，但他们一定是互不相交的。

🌲结点的分类

结点：树的结点包含一个数据元素和若干指向其子树的分支。

结点的度（Degree）：结点拥有的子树。

叶子结点（Leaf）/终端结点：度为0的结点。

分支结点/非终端结点：度不为0的结点。

内部结点：除根节点以外，分支结点也称为内部结点。

树的度：树内各结点的度的最大值。

🌲结点之间的关系

孩子（Child）和双亲（Parent）：结点的子树的根，相应的，该结点称为孩子的双亲。（注意是双亲，不是单亲）
兄弟（sibling）：同一个双亲的孩子之间互称兄弟。
结点的祖先：从根结点到该结点所经过分支上的所有结点。
子孙：以某结点为根的子树中的任一结点都称为该节点的子孙。
无序树和有序树：如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该数为有序树，否则为无序树。
森林(fores)：m(m>=0)棵互不相较的树的集合。

💚❤️💙💚❤️💙💚❤️💙💚❤️💙💚❤️💙💚❤️💙💚❤️💙💚❤️💙💚❤️💙💚❤️💙

🐋树的存储结构

树的4种链式存放方式：

双亲链表存储结构

孩子链表存储结构

双亲孩子链表存储结构

孩子兄弟链表存储结构

⚡双亲链表存储结构

以一组地址连续的存储单元存放树中的各个结点，每个结点有两个域：
- 数据域：用于存放树中该结点的值。
- 指针域：用于存放该结点的双亲结点在存储结构中的位置。

data(数据域)	parent(指针域)
存储结点的数据信息	存储该结点的双亲所在数组中的下标

优点：查找一个指定结点的双亲结点非常容易。
缺点：查找指定结点的孩子结点，需要扫描整个链表。

⚡孩子链表存储结构

以一组地址连续的存储单元来存放树中的各个结点，每一个结点有两个域。
- 数据域：存放该结点的值
- 指针域：用于存放该结点的孩子链表的头指针。
孩子链表的孩子结点：

child(数据域)	next(指针域)
存储某个结点在表头数组中的下标	存储指向某结点的下一个孩子结点的指针

表头数组的表头结点：

data(数据域)	firstchild(头指针域)
存储某个结点的数据信息	存储该结点的孩子链表的头指针

优点：便于实现查找树中指定结点的孩子结点。
缺点：不便于查找指定结点的双亲结点。

⚡双亲孩子链表存储结构

与孩子链表存储结构类似，以一组地址连续的存储单元来存放树中的各个结点，每一个结点有三个域
- 数据域：存放该结点的值
- 父指针域：用于存放双亲结点在数组中的位置
- 子指针域：用于存放该结点的孩子链表的头指针。

⚡孩子兄弟链表存储结构

孩子兄弟链表存放，又称为“左子/右兄”二叉链式存储结构。
- 左指针：指向该结点的第一个孩子
- 右指针：指向该结点的右邻兄弟

data(数据域)	firstchild(指针域)	rightsib(指针域)
存储结点的数据信息	存储该结点的第一个孩子的存储地址	存储该结点的右兄弟结点的存储地址

💚❤️💙💚❤️💙💚❤️💙💚❤️💙💚❤️💙💚❤️💙💚❤️💙💚❤️💙💚❤️💙💚❤️💙

如果文章对您有帮助，就拿起小手赶紧给博主点赞💚评论❤️收藏💙 一下吧！

想要了解更多吗？没时间解释了，快来点一点！

路遥叶子的博客_CSDN博客-数据结构,安利Java零基础,spring领域博主https://blog.csdn.net/zsy3757486?spm=1000.2115.3001.5343

【数据结构】树的定义、树的存储结构

目录

🐋树的定义

🐋树的存储结构

前言