[科普中国]-树形数据结构

简介

在计算机科学中，树（tree）是一种抽象数据类型（ADT）或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>0）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

每个节点有零个或多个子节点；

没有父节点的节点称为根节点；

每一个非根节点有且只有一个父节点；

除了根节点外，每个子节点可以分为多个不相交的子树；

树形数据结构是一类重要的非线性数据结构。树形数据结构在计算机领域中有着广泛应用，如在编译程序中，可用树来表示源程序的语法结构。1又如在数据库系统中，树形数据结构也是信息的重要组织形式之一。以及在文件管理中，多级目录结构就采用树形数据结构。

相关术语1、结点(Node)：表示树中的数据元素，由数据项和数据元素之间的关系组成。在图中，共有10个结点。
2、结点的度(Degree of Node)：结点所拥有的子树的个数，在图中，结点A的度为3。
3、树的度(Degree of Tree)：树中各结点度的最大值。在图5.1中，树的度为3。
4、叶子结点(Leaf Node)：度为0的结点，也叫终端结点。在图5.1中，结点E、F、G、H、I、J都是叶子结点。
5、分支结点(Branch Node)：度不为0的结点，也叫非终端结点或内部结点。在图5.1中，结点A、B、C、D是分支结点。
6、孩子(Child)：结点子树的根。在图中，结点B、C、D是结点A的孩子。
7、双亲(Parent)：结点的上层结点叫该结点的双亲。在图中，结点B、C、D的双亲是结点A。
8、祖先(Ancestor)：从根到该结点所经分支上的所有结点。在图中，结点E的祖先是A和B。
9、子孙(Descendant)：以某结点为根的子树中的任一结点。在图中，除A之外的所有结点都是A的子孙。
10、兄弟(Brother)：同一双亲的孩子。在图5.1中，结点B、C、D互为兄弟。
11、结点的层次(Level of Node)：从根结点到树中某结点所经路径上的分支数称为该结点的层次。根结点的层次规定为1，其余结点的层次等于其双亲结点的层次加1。

12、堂兄弟(Sibling)：同一层的双亲不同的结点。在图中，G和H互为堂兄弟。
13、树的深度(Depth of Tree)：树中结点的最大层次数。在图5.1中，树的深度为3。

14、无序树(Unordered Tree)：树中任意一个结点的各孩子结点之间的次序构成无关紧要的树。通常树指无序树。

15、有序树(Ordered Tree)：树中任意一个结点的各孩子结点有严格排列次序的树。二叉树是有序树，因为二叉树中每个孩子结点都确切定义为是该结点的左孩子结点还是右孩子结点。

16、森林(Forest)：m(m≥0)棵树的集合。自然界中的树和森林的概念差别很大，但在数据结构中树和森林的概念差别很小。从定义可知，一棵树有根结点和m个子树构成，若把树的根结点删除，则树变成了包含m棵树的森林。当然，根据定义，一棵树也可以称为森林。

多级目录结构对于大型文件系统，通常采用三级或三级以上的目录结构，以提高对目录的检索速度和文件系统的性能。多级目录结构又称为树型目录结构，主目录在这里被称为根目录，把数据文件称为树叶，其它的目录均作为树的结点。下图示出了多级目录结构。图中，用方框代表目录文件，圆圈代表数据文件。在该树型目录结构中，主(根)目录中有三个用户的总目录项 A、 B 和 C。 在 B 项所指出的 B 用户的总目录 B 中， 又包括三个分目录 F、 E 和

D，其中每个分目录中又包含多个文件。如 B 目录中的 F 分目录中，包含 J 和 N 两个文件。为了提高文件系统的灵活性，应允许在一个目录文件中的目录项既是作为目录文件的 FCB，又是数据文件的 FCB，这一信息可用目录项中的一位来指示。例如，在图 6-19 中，用户 A的总目录中，目录项 A 是目录文件的 FCB，而目录项 B 和 D 则是数据文件的 FCB。2