一、树的基本概念
树是由n(n≥0)个结点组成的有限集合。若n=0,则称为空树;若n>0,则称为非空树,在任一棵非空树中,满足以下条件:
-
有一个特定的称为根(root)的结点。它只有直接后继,但没有直接前驱。
-
除根结点以外的其他结点可以划分为m(m≥0)个互不相交的有限集合T0,T1,…,Tm-1,且每个集合Ti(i=0,1,…,m-1)本身又是一棵树,称为根的子树。即树T0,T1,…,Tm-1称为这个根结点的子树。
由此可知,树的定义是一个递归的定义,因为树的定义中又用到了树的概念。
从定义中看出树结构具有以下特点:
-
有且仅有一个结点没有直接前驱,即根结点。
-
除根结点之外,其余所有结点有且仅有一个直接前驱结点。
-
包括根结点在内,每个结点可以有多个(或零个)直接后继结点。
从此可见,树形结构的特点是数据元素之间存在着一对多的关系。
树的结构如下图所示:
树结构示意图:
在树结构示意图(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}。
树的三个子树:
二、树的基本术语
-
树的结点
树的结点是指树中的一个数据元素,一般用一个字母表示。
-
结点的度
一个结点包含子树的数目,称为该结点的度。
-
树叶(叶子)
度为 0 的结点,称为叶子结点或树叶,也叫终端结点。
-
分支结点(非终端结点)
除叶子结点外的所有结点,称为分支结点。通常又将除根结点之外的分支结点称为内部结点。
-
孩子结点
若结点 X 有子树,则子树的根结点为 X 的孩子结点,也称为孩子。树结构示意图(c)中 A 的孩子为 B、C、D。
-
双亲结点
若结点 X 有子女 Y,则 X 为 Y 的双亲结点。
-
祖先结点
一个结点的祖先是从根结点到该结点路径上所经过的所有结点。树结构示意图(c)中 K 的祖先结点是 A、B、E。
-
子孙结点
某一结点的直接后继(子女)和间接后继(子女的子女)为该结点子孙。树结构示意图(c)中 D 的子孙是 H、I、M。
-
兄弟结点
具有同一个双亲的结点,称为兄弟结点。不具有同一个双亲但有共同祖先的结点是堂兄弟。
-
结点的层次
从根结点开始定义,根为第一层,根的孩子为第二层,以此类推。
-
树的高度(深度)
树中结点所处的最大层数称为树的高度,如空树的高度为 0,只有一个根结点的树高度为 1。
-
树的度
树中结点度的最大值称为树的度。
-
有序树
若一棵树中所有子树从左到右的排序是有顺序的,不能颠倒次序,称该树为有序树。
-
无序树
若一棵树中所有子树的次序无关紧要,则称为无序树。
-
森林(树林)
若干棵(有限棵)互不相交的树组成的集合称为森林。一棵树可以看成一个特殊的森林。树与森林的关系如下:任何一棵非空树,删去根结点就变成了森林;反之,给森林增加一个统一的根结点,森林就变成一棵树。
三、树的表示
-
树形结构表示法
参考树结构示意图 -
凹入表示法
-
嵌套集合表示法
-
广义表表示法
对树结构示意图所示的树结构,用广义表表示法可表示为:A(B(E(J,K,L),F),C(G),D(H(M),I))