data structure

1. 树的定义

树是 n 个结点的有限集合,n=0 时,称为空树,这是一种特殊情况。在任意一颗非空树中应该满足

  1. 有且仅有一个根
  2. 子结点可作为根结点形成自己的子树

所以,树的定义是递归的,是一种递归的数据结构。树作为一种逻辑结构,同时也是一种分层结构,具有以下特点

  1. 树的根结点没有前驱结点,除根结点外的所有结点有且仅有一个前驱结点。
  2. 树中所有结点可以有零个或多个后继结点。

树适合于表示具有层次结构的数据。树中的某个结点(除根结点外)最多只和上一层的一个结点(即其父结点)有直接关系,根结点没有直接上层结点,因此在 n 个结点的树中有 n-1 条边,而树中每个结点与其下一层的零个或多个结点(即其子女结点)有直接关系。

2. 基本术语

  1. 根结点 A 到结点 K 的唯一路径上的任意结点,称为结点 K 的祖先结点(反过来称为子孙结点)。路径中最接近结点 K 的结点被称为双亲结点(反过来称为孩子结点)。根 A 是树中唯一没有双亲的结点,有相同双亲的结点称为兄弟结点。

  2. 树中一个结点的子结点个数称为该结点的度,树中结点的最大度数称为树的度。

  3. 度大于 0 的结点称为分支结点(又称为非终端结点);度为 0(没有子女结点)的结点称为叶子结点(又称终端结点)。在分支结点中,每个结点的分支数就是该结点的度。

  4. 结点的深度、高度和层次

    结点的层次从树根开始定义,根结点为第一层(有些教材定义为第 0 层),它的子结点为第二层,以此类推。

    结点的深度是从根结点开始自顶向下逐层累加的。

    结点的高度是从叶结点开始自底向上逐层累加的。

    树的高度(又称深度)是树中结点的最大层数。

  5. 有序树和无序树。树中结点的子树从左到右是有次序的,不能交换,这样的树称为有序树,有序树中,一个结点的子结点按从左到右的顺序出现是有关联的,反之则称为无序树 。

  6. 路径和路径长度。树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的,而路径长度是路径上所经过的边的个数。

    注意 :由于树中的分支是有向的,即从双亲结点指向孩子结点,所以树中的路径是从上向下的,同一个双亲结点的两个孩子结点之间不存在路径。

  7. 森林。森林是 m 棵互不相交的树的集合。森林的概念与树的概念十分相近,因为只要把树的根结点删去就成了森林。反之,只要给 n 棵独立的树加上一个结点,并把这 n 棵树作为该结点的子树,则森林就变成了树。

注意 :上述概念无须死记硬背,灵活运用即可。