树的邻接矩阵、双亲孩子表示法…… C++ 不知树系列之初识树 _生活百科

1. 前言树是一种很重要的数据结构，最初对数据结构的定义就是指对树和图的研究，后来才广义化了数据结构这个概念。从而可看出树和图在数结构这一研究领域的重要性。
树和图重要的原因是，它让计算机能建模出现实世界中更多领域里错综复杂的信息关系，让计算机服务这些领域成为可能。
本文将和大家聊聊树的基本概念，以及树的物理存储结构以及实现。
2. 基本概念数据结构的研究主要是从 2 点出发：

洞悉数据与数据之间的逻辑关系。
设计一种物理存储方案。除了存储数据本身还要存储数据之间的逻辑关系，并且能让基于此数据上的算法利用这种存储结构达到事半功倍的效果。

当数据之间存在一对多关系时，可以使用树来描述。如公司组织结构、家庭成员关系……

文章插图
完整的树结构除了需要描述出数据信息，还需要描述数据与数据之间的关系。树结构中，以节点作为数据的具体形态，边作为数据之间关系的具体形态。
也可以说树是由很多节点以及边组成的集合。
如果一棵树没有任何节点，则称此树为空树。如果树不为空，则此树存在唯一的根节点（root），根节点是整棵树的起点，其特殊之处在于没有前驱节点。如上图值为董事长的节点。
除此之外，树中的节点与节点之间会存在如下关系：

父子关系：节点的前驱节点称其为父节点，且只能有一个或没有（如根节点）。节点的后驱节点称其为子节点，子节点可以有多个。如上图的董事长节点是市场总经理节点的父节点，反之，市场总经理节点是董事长节点的子节点。
兄弟关系：如果节点之间有一个共同的前驱（父）节点，则称这些节点为兄弟节点。如上图的市场总经理节点和运维总经理节点为兄弟关系。
叶节点：叶节点是没有后驱（子）节点的节点。
子树：一棵树也可以理解是由子节点为根节点的子树组成，子树又可以理解为多个子子树组成…… 所以树可以描述成是树中之树式的递归关系。

如下图所示的 T 树。