一、树的基本概念

树是由n(n≥0)个结点组成的有限集合。若n=0,则称为空树;若n>0,则称为非空树,在任一棵非空树中,满足以下条件:

  1. 有一个特定的称为根(root)的结点。它只有直接后继,但没有直接前驱。

  2. 除根结点以外的其他结点可以划分为m(m≥0)个互不相交的有限集合T0,T1,…,Tm-1,且每个集合Ti(i=0,1,…,m-1)本身又是一棵树,称为根的子树。即树T0,T1,…,Tm-1称为这个根结点的子树。

由此可知,树的定义是一个递归的定义,因为树的定义中又用到了树的概念。

从定义中看出树结构具有以下特点:

  1. 有且仅有一个结点没有直接前驱,即根结点。

  2. 除根结点之外,其余所有结点有且仅有一个直接前驱结点。

  3. 包括根结点在内,每个结点可以有多个(或零个)直接后继结点。

从此可见,树形结构的特点是数据元素之间存在着一对多的关系。

树的结构如下图所示:

树结构示意图:
树结构示意图

在树结构示意图(c)中,树的根结点为 A,该树还可以分为 3 个互不相交的子集T0、T1、T2,具体请参见图“树的三个子树”,其中,T0 ={B,E,F,J,K,L},T1 ={C,G},T2 ={D,H,I,M},而T0、T1、T2又可以分解成若干棵不相交子树。例如,T0可以分解成T00、T01两个不相交子集,T00 ={E,J,K,L},T01 ={F},而 T00 又可以分为 3 个不相交子集T000、T001、T002,其中,T000 ={J},T001 ={K},T002 ={L}。

树的三个子树:
树的三个子树

二、树的基本术语

  1. 树的结点

    树的结点是指树中的一个数据元素,一般用一个字母表示。

  2. 结点的度

    一个结点包含子树的数目,称为该结点的度。

  3. 树叶(叶子)

    度为 0 的结点,称为叶子结点或树叶,也叫终端结点。

  4. 分支结点(非终端结点)

    除叶子结点外的所有结点,称为分支结点。通常又将除根结点之外的分支结点称为内部结点。

  5. 孩子结点

    若结点 X 有子树,则子树的根结点为 X 的孩子结点,也称为孩子。树结构示意图(c)中 A 的孩子为 B、C、D。

  6. 双亲结点

    若结点 X 有子女 Y,则 X 为 Y 的双亲结点。

  7. 祖先结点

    一个结点的祖先是从根结点到该结点路径上所经过的所有结点。树结构示意图(c)中 K 的祖先结点是 A、B、E。

  8. 子孙结点

    某一结点的直接后继(子女)和间接后继(子女的子女)为该结点子孙。树结构示意图(c)中 D 的子孙是 H、I、M。

  9. 兄弟结点

    具有同一个双亲的结点,称为兄弟结点。不具有同一个双亲但有共同祖先的结点是堂兄弟。

  10. 结点的层次

    从根结点开始定义,根为第一层,根的孩子为第二层,以此类推。

  11. 树的高度(深度)

    树中结点所处的最大层数称为树的高度,如空树的高度为 0,只有一个根结点的树高度为 1。

  12. 树的度

    树中结点度的最大值称为树的度。

  13. 有序树

    若一棵树中所有子树从左到右的排序是有顺序的,不能颠倒次序,称该树为有序树。

  14. 无序树

    若一棵树中所有子树的次序无关紧要,则称为无序树。

  15. 森林(树林)

    若干棵(有限棵)互不相交的树组成的集合称为森林。一棵树可以看成一个特殊的森林。树与森林的关系如下:任何一棵非空树,删去根结点就变成了森林;反之,给森林增加一个统一的根结点,森林就变成一棵树。

三、树的表示

  1. 树形结构表示法
    参考树结构示意图

  2. 凹入表示法

    凹入表示法

  3. 嵌套集合表示法

    树的嵌套集合表示法

  4. 广义表表示法
    对树结构示意图所示的树结构,用广义表表示法可表示为:

    A(B(E(J,K,L),F),C(G),D(H(M),I))

用户头像
登录后发表评论