第六章 数据结构之非线性结构

第一节 树的概念

教学课件下载

一、树的定义
    树是一种常见的非线性的数据结构。
    树的定义：树是n(n>0)个结点的有限集，这个集合满足以下条件：
    ⑴ 有且仅有一个结点没有前驱（父亲结点），该结点称为树的根；
    ⑵ 除根外，其余的每个结点都有且仅有一个前驱；
    ⑶ 除根外，每一个结点都通过唯一的路径连到根上。这条路径由根开始，而未端就在该结点上，且除根以外，路径上的每一个结点都是前一个结点的后驱（儿子结点）；

二、结点的分类
    在树中，一个结点包含一个元素以及所有指向其子树的分支。
    结点一般分成三类:
    ⑴ 根结点：没有前驱的结点。在树中有且仅有一个根结点。如上图（b）中的r；
    ⑵ 分支结点：除根结点外，有后驱的结点称为分支结点。如上图（b）中的a，b，c，x，t，d，i。分支结点亦是其子树的根；
    ⑶ 叶结点：没有后驱的结点称为树叶。如上图（b）中的w，h，e，f，s，m，o，n，j，u为叶结点。由树的定义可知，树叶本身也是其父结点的子树。 根结点到每一个分支结点或叶结点的路径是唯一的。例如上图（b）中，从根r到结点i的唯一路径为rcti。

三、有关度的定义
    ⑴ 结点的度：一个结点的子树数目称为该结点的度。在上图（b）中，结点i度为3，结点t的度为2，结点b的度为1。显然，所有树叶的度为0。
    ⑵ 树的度：所有结点中最大的度称为该树的度。图（b）中的树的度为3。

四、树的深度（高度）
    树是分层次的。结点所在的层次是从根算起的。根结点在第一层，根的后件在第二层，其余各层依次类推。即若某个结点在第k层，则该结点的后件均处在第k+1层。
    图（b）中的树共有五层。在树中，父结点在同一层的所有结点构成兄弟关系。树中最大的层次称为树的深度，亦称高度。图（b）中树的深度为5。

五、森林
    所谓森林，是指若干棵互不相交的树的集合。
    如图（b）去掉根结点r，其原来的三棵子树Ta，Tb，Tc的集合{Ta，Tb，Tc}就为森林，这三棵子树的具体形态如图（c）。 

六、有序树和无序树
    按照树中同层结点是否保持有序性，可将树分为有序树和无序树。如果树中同层结点从左而右排列，其次序不容互换，这样的树称为有序树；如果同层结点的次序任意，这样的树称为无序树。