数据结构之树及树的存储

——————————————本栏目旨在交流计算机知识————————————————— 上一章节，我们介绍了线性的数据结构：表，栈，队列。接下来，我们将进入下一章节——树结构的学习。 首先，我们先介绍一下树的基本概念： 结点**：使⽤树结构存储的每一个数据元素都被称为“结点”。例如图中的A就是一个结点。 根结点**：有一个特殊的结点，这个结点没有前驱，我们将这种结点称之为根结点。 ⽗结点（双亲结点）、子结点和兄弟结点**：对于ABCD四个结点来说，A就是BCD的⽗结点，也称之为双亲结点。 ⽽BCD都是A的子结点，也称之为孩子结点。对于BCD来说，因为他们都有同一个爹，所以它们互相称之为兄弟结 点。 叶子结点**：如果一个结点没有任何子结点，那么此结点就称之为叶子结点。 层级**： 每一同辈分的节点称为同一层级。 结点的度**：结点拥有的子树的个数，就称之为结点的度。 树的度**：在各个结点当中，度的最⼤值。为树的度。 树的深度或者⾼度：结点的层次从根结点开始定义起，根为第一层，根的孩子为第二层。依次类推。 高度**：每一条路径的深度。 树的高度**：最深的路径的高度。 不同于线性结构的一条到底，树结构是一种逐渐扩散的结构。我们算法中的dfs与bfs就是用树的原理来完成的。在树结构中，我们不再关心客观全局的先后绝对位置，而是关心每个节点本身的前置与后继，前驱节点我们称为：双亲节点（父节点），后继节点我们称为：孩子节点（子节点）。（特殊的，有时候我们称同一层级的不同元素为兄弟元素，隔着两代的称为祖父节点，再往前则为祖先节点了） 下面我们来介绍一下主流的几种树的表示方法： 1、双亲表示法：（此表示法找双亲会效率很高，但是找孩子的效率很低）

双亲表示法的实现形式是以顺序表存储结构为基本方法来实现，主体思想是：利用顺序表存储，其表元素用数据和父节点构成：

特点分析：根结点没有双亲，所以位置域设置为-1

知道一个结点，找他的⽗结点，非常容易，O(1)级

找孩子节点，必须遍历整个表

如图：

​​​​​​​

2、孩子表示法（此表示法找双亲会效率很高，但是找孩子的效率很低）

如图所示，孩子表示法是基于链表的结构实现的，我们实现的具体思路为：先构建一个链表的基础结构体，然后再声明一个结构体数组用来存储每一个节点，然后向有子树的节点为表头从左到右形成描述下一层的链表，作为查找孩子的索引。直到叶子节点为止。

这样，每当我们需要寻找某个节点的孩子节点时，那么我们就可以通过链表很容易的找到孩子元素了，而不是运用遍历这种耗时费力的朴素方法。但是这种孩子表示法很难寻找双亲，效率低。

进阶版————双亲表示法与孩子表示法合二为一：

如图所示：我们依然是用一个结构体来储存基本数据类型，但是，我们多声明了一个int类型用来标识该节点的父类节点，以弥补孩子表示法难以找寻父类的缺点。

好了，现在我们已然 完成了基本表示法的讲解，下面，我们来介绍一下拓展板块的表示法： 孩子兄弟表示法

上文，我们已然介绍了兄弟即为同层的不同节点，那么，如果我们想找寻节点的兄弟的时候，前文所述的表示法就不太够用了，于是我们可以尝试构建以下的结构：

• 在树结构中，同一层的节点互为兄弟节点。例如普通树中，节点 A、B 和 C 互为兄弟节点，⽽节点 D、E 和 F 也 互为兄弟节点。*

• 所谓孩子兄弟表示法，指的是⽤将整棵树⽤二叉链表存储起来，具体实现方案是：从树的根节点开始，依次存储各 个结点的孩子结点和兄弟结点。 在二叉链表中，各个结点包含三部分内容：*

​​​​​​​ ​​​​​​​ * *

孩子兄弟表示法，旨在以左孩子右兄弟的方法来表示节点之间的关系，通过这样的二叉结构我们可以很好的寻找孩子和兄弟：在以孩子兄弟表示法构建的二叉链表中，如果要查找结点 x 的所有孩子，则只要根据该结点的 firstchild 指针找到 它的第一个孩子，然后沿着孩子结点的 nextsibling 指针不断地找它的兄弟结点，就可以找到结点 x 的所有孩子。 好了，以上就是树及树的存储的基本知识结构原理了，希望能够给你带来帮助！