【Data Structure】树(Trees)

Posted by 西维蜀黍 on 2019-05-24, Last Modified on 2023-11-13

树(Tree)

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

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

树(Tree)是由多个节点(Node)的集合组成,每个节点又有多个与其关联的子节点(Child Node)。子节点就是直接处于节点之下的节点,而父节点(Parent Node)则位于节点直接关联的上方。树的根(Root)指的是一个没有父节点的单独的节点。

所有的树都呈现了一些共有的性质:

  1. 只有一个根节点;
  2. 除了根节点,所有节点都有且只有一个父节点;
  3. 无环。将任意一个节点作为起始节点,都不存在任何回到该起始节点的路径。(正是前两个性质保证了无环的成立。

树中使用的术语

  • 节点(Node):使用树结构存储的每一个数据元素都被称为“节点”。例如,上图(A)中,数据元素 A 就是一个节点;

  • 树根节点(根节点,Root Node):每一个非空树都有且只有一个被称为根的节点。上图(A)中,节点A就是整棵树的根节点。 树根的判断依据为:如果一个节点没有父节点,那么这个节点就是整棵树的根节点。

  • 子节点(Child Nodes):节点所拥有子树的根节点称为该节点的子节点。

  • 父节点(双亲节点,Parent Node):如果节点拥有子节点,则该节点为子节点的父节点。

  • 兄弟节点(Sibling Node):与节点拥有相同父节点的节点。

  • 子孙节点(Descendant Node):节点向下路径上可达的节点。

  • 叶子节点(Leaf Node):如果某节点没有任何子节点,那么此节点称为叶子节点(叶节点)。例如上图(A)中,节点 K、L、F、G、M、I、J 都是这棵树的叶子节点。

  • 度(Degree):节点拥有子树的数量。

  • 边(Edge):两个节点中间的链接。

  • 路径(Path):从节点到子孙节点过程中的边和节点所组成的序列。

  • 层级(Level):根为 Level 0 层,根的子节点为 Level 1 层,以此类推。

  • 高度(Height)/深度(Depth):树中层的数量。比如只有 Level 0,Level 1,Level 2 则高度为 3。

对于上图(A)中的节点 A、B、C、D 来说,A 是 B、C、D 节点的父节点(也称为“双亲节点”),而 B、C、D 都是 A 节点的子节点(也称“孩子节点”)。对于 B、C、D 来说,它们都有相同的父节点,所以它们互为兄弟节点

子树和空树

子树:如上图(A)中,整棵树的根节点为节点 A,而如果单看节点 B、E、F、K、L 组成的部分来说,也是棵树,而且节点 B 为这棵树的根节点。所以称 B、E、F、K、L 这几个节点组成的树为整棵树的子树;同样,节点 E、K、L 构成的也是一棵子树,根节点为 E。

注意:单个节点也是一棵树,只不过根节点就是它本身。上图(A)中,节点 K、L、F 等都是树,且都是整棵树的子树。

知道了子树的概念后,树也可以这样定义:树是由根节点和若干棵子树构成的。

空树:如果集合本身为空,那么构成的树就被称为空树。空树中没有节点。

补充:在树结构中,对于具有同一个根节点的各个子树,相互之间不能有交集。例如,上图(A)中,除了根节点 A,其余元素又各自构成了三个子树,根节点分别为 B、C、D,这三个子树相互之间没有相同的节点。如果有,就破坏了树的结构,不能算做是一棵树。

节点的度(Degrees)和层次(Levels)

节点的度(Degrees)

对于一个节点,拥有的子树数(节点有多少分支)称为节点的度(Degree)。例如,上图(A)中,根节点 A 下分出了 3 个子树,所以,节点 A 的度为 3。

一棵树的度是树内各节点的度的最大值。上图(A)表示的树中,各个节点的度的最大值为 3,所以,整棵树的度的值是 3。

节点的层次(Levels)

节点的层次:从一棵树的树根开始,树根所在层为第一层,根的孩子节点所在的层为第二层,依次类推。对于上图(A)来说,A 节点在第一层,B、C、D 为第二层,E、F、G、H、I、J 在第三层,K、L、M 在第四层。

一棵树的深度(高度)是树中节点所在的最大的层次。上图(A)树的深度为 4。

如果两个节点的父节点虽不相同,但是它们的父节点处在同一层次上,那么这两个节点互为堂兄弟。例如,上图(A)中,节点 G 和 E、F、H、I、J 的父节点都在第二层,所以之间为堂兄弟的关系。

有序树和无序树

如果树中节点的子树从左到右看,谁在左边,谁在右边,是有规定的,这棵树称为有序树;反之称为无序树

在有序树中,一个节点最左边的子树称为"第一个孩子",最右边的称为"最后一个孩子"。

拿上图(A)来说,如果其本身是一棵有序树,则以节点 B 为根节点的子树为整棵树的第一个孩子,以节点 D 为根节点的子树为整棵树的最后一个孩子。

森林

由 m(m >= 0)个互不相交的树组成的集合被称为森林。上图(A)中,分别以 B、C、D 为根节点的三棵子树就可以称为森林。

前面讲到,树可以理解为是由根节点和若干子树构成的,而这若干子树本身是一个森林,所以,树还可以理解为是由根节点和森林组成的。用一个式子表示为:

Tree =(root,F)

其中,root 表示树的根节点,F 表示由 m(m >= 0)棵树组成的森林。

树的表示方法

除了上图(A)表示树的方法外,还有其他表示方法:

上图(A)是以嵌套的集合的形式表示的(集合之间绝不能相交,即图中任意两个圈不能相交)。

上图(B)使用的是凹入表示法(了解即可),表示方式是:最长条为根节点,相同长度的表示在同一层次。例如 B、C、D 长度相同,都为 A 的子节点,E 和 F 长度相同,为 B 的子节点,K 和 L 长度相同,为 E 的子节点,依此类推。

最常用的表示方法是使用广义表的方式。上图(A)用广义表表示为:

(A, (B(E(K, L), F), C(G), D(H(M), I, J)))

Reference