树的定义、树的存储结构

xlc5202022年5月19日
大约 5 分钟约 1406 字

树的定义、树的存储结构

前言

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

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

img

  • 图 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时称为空树。在任意一颗非空树中:

  1. 有且仅有一个特定的称为根(root)的结点;****
  2. 当n>1时,其余结点可分为m(m>0)个互补交互的有限集T1、T2...Tm,其中每一个集合本身又是一棵树,并称为根的子树**(SubTree)**。

img

🌲树的特点

  • n>0时,根节点是唯一的,不可能存在多个根节点。数据结构中的树只有一个根节点
  • m>0时,子树的个数没有限制,但他们一定是互不相交

🌲结点的分类

  • 结点:树的结点包含一个数据元素和若干指向其**子树的分支****。
  • 结点的度(Degree):结点拥有的子树
  • 叶子结点(Leaf)/终端结点:****度为0的结点。
  • 分支结点/非终端结点:****度不为0的结点。
  • **内部结点:**除根节点以外,分支结点也称为内部结点。
  • 树的度:树内各结点的度的最大值

img

🌲结点之间的关系

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

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

🐋树的存储结构

树的4种链式存放方式:

  1. 双亲链表存储结构**

  2. 孩子链表存储结构**

  3. 双亲孩子链表存储结构**

  4. 孩子兄弟链表存储结构**

img

⚡双亲链表存储结构

  • 以一组地址连续的存储单元存放树中的各个结点,每个结点有两个域
    • 数据域:用于存放树中该结点的
    • 指针域:用于存放该结点的双亲结点在存储结构中的位置。
data(数据域)parent(指针域)
存储结点的数据信息存储该结点的双亲所在数组中的下标

img

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

⚡孩子链表存储结构

  • 以一组地址连续的存储单元来存放树中的各个结点,每一个结点有两个域。
    • 数据域:存放该结点的
    • 指针域:用于存放该结点的孩子链表的头指针
  • 孩子链表的孩子结点:
child(数据域)next(指针域)
存储某个结点在表头数组中的下标存储指向某结点的下一个孩子结点的指针
  • 表头数组的表头结点:
data(数据域)firstchild(头指针域)
存储某个结点的数据信息存储该结点的孩子链表的头指针

img

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

⚡双亲孩子链表存储结构

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

img


⚡孩子兄弟链表存储结构

  • 孩子兄弟链表存放,又称为**“左子/右兄”**二叉链式存储结构。
    • 左指针:指向该结点的第一个孩子
    • 右指针:指向该结点的右邻兄弟
data(数据域)firstchild(指针域)rightsib(指针域)
存储结点的数据信息存储该结点的第一个孩子的存储地址存储该结点的右兄弟结点的存储地址

img

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