1. 前言树是一种很重要的数据结构，最初对数据结构的定义就是指对树和图的研究 ， 后来才广义化了数据结构这个概念 。从而可看出树和图在数结构这一研究领域的重要性 。
树和图重要的原因是，它让计算机能建模出现实世界中更多领域里错综复杂的信息关系，让计算机服务这些领域成为可能 。
本文将和大家聊聊树的基本概念，以及树的物理存储结构以及实现 。
2. 基本概念数据结构的研究主要是从 2 点出发：
- 洞悉数据与数据之间的逻辑关系 。
- 设计一种物理存储方案 。除了存储数据本身还要存储数据之间的逻辑关系，并且能让基于此数据上的算法利用这种存储结构达到事半功倍的效果 。
文章插图
完整的
树结构除了需要描述出数据信息 ， 还需要描述数据与数据之间的关系 。树结构中，以节点作为数据的具体形态，边作为数据之间关系的具体形态 。也可以说树是由很多
节点以及边组成的集合 。如果一棵树没有任何节点，则称此树为空树 。如果树不为空，则此树存在唯一的根节点
（root） ， 根节点是整棵树的起点，其特殊之处在于没有前驱节点 。如上图值为董事长的节点 。除此之外，树中的节点与节点之间会存在如下关系：
- 父子关系：节点的前驱节点称其为父节点 ， 且只能有一个或没有（如根节点） 。节点的后驱节点称其为子节点 ， 子节点可以有多个 。如上图的
董事长节点是市场总经理节点的父节点，反之 ，市场总经理节点是董事长节点的子节点 。 - 兄弟关系： 如果节点之间有一个共同的前驱（父）节点，则称这些节点为兄弟节点 。如上图的
市场总经理节点和运维总经理节点为兄弟关系 。 - 叶节点： 叶节点是没有后驱（子）节点的节点 。
- 子树：一棵树也可以理解是由子节点为根节点的子树组成，子树又可以理解为多个子子树组成…… 所以树可以描述成是树中之树式的递归关系 。
T 树。
文章插图
可以理解为
T1和T2子树组成 。
文章插图
T1、T2又可以认为是由它的子节点为根节点的子子树组成，以此类推，一直到叶节点为止 。树的相关概念：
- 节点的度： 一个节点含有子树的个数称为该节点的度 。
- 树的度：一棵树中，最大的节点的度称为树的度 。
- 节点的层次：同级的节点为一个层次 。根节点为第
1层，根的子节点为第2层，以此类推 。 - 树的高（深）度： 树中节点最大的层次 。如上图中的树的最大层次为
4。
- 无序树：树中的结点之间没有顺序关系，这种树称为无序树 。
- 有序树：树中任意节点的子节点之间有左右顺序关系 。如下图，任一节点的左子节点值小于右子节点值 。
文章插图
- 二叉树：如果任一节点最多只有
2个子节点，则称此树结构为二叉树 。上图的有序树也是一棵二叉树 。
- 完全二叉树：一棵二叉树至多只有最下面两层的节点的子结点可以小于
2。并且最下面一层的节点都集中在该层最左边的若干位置上 。
- 满二叉树：除了叶节点，其它节点的子结点都有
2个 。如上图中的树也是满二叉树 。
邻接矩阵和邻接表的形式存储树 。3.1 邻接矩阵存储邻接矩阵是顺序表存储方案 。
3.1.1 思路流程
- 给树中的每一个节点从小到大进行编号 。如下图 ， 树共有
11个节点 。
文章插图
