|
树是n(n≥0)个结点的有限集合。当n=0时称为空树。在任一非空树(n>0)中,有且仅有一个称为根的结点;其余结点可分为m(m≥0)个互不相交的有限集T1,T2,…,Tm,其中每个集合又都是一棵树,并且称为根结点的子树。
|
|
|
树的定义是递归的,它表明了树本身的固有特性,也就是一棵树由若干棵子树构成,而子树又由更小的子树构成。该定义只给出了树的组成特点,若从数据结构的逻辑关系角度来看,树中元素之间有明显的层次关系。对树中的某个结点,它最多只和上一层的一个结点(即其双亲结点)有直接关系,而与其下一层的多个结点(即其子树结点)有直接关系,如下图所示。通常,凡是分等级的分类方案都可以用具有严格层次关系的树结构来描述。
|
|
|
|
|
.双亲、孩子和兄弟:结点的子树的根称为该结点的孩子,相应地,该结点称为其子结点的双亲。具有相同双亲的结点互为兄弟。例如,上图中,结点A是树根,B、C、D是A的孩子结点,B、C、D互为兄弟;B是E、F的双亲,E、F互为兄弟。
|
|
|
.结点的度:一个结点的子树的个数记为该结点的度。例如,上图中,A的度为3,B的度为2,C的度为0,D的度为1。
|
|
|
.叶子结点:也称为终端结点,指度为零的结点。例如,上图中,E、F、C、G都是叶子结点。
|
|
|
.内部结点:度不为零的结点称为分支结点或非终端结点。除根结点之外,分支结点也称为内部结点。例如,上图中,B、D都是内部结点。
|
|
|
.结点的层次:根为第一层,根的孩子为第二层。以此类推,若某结点在第i层,则其孩子结点就在第i+1层。例如,上图中,A在第1层,B、C、D在第2层,E、F和G在第3层。
|
|
|
.树的高度:一棵树的最大层次数记为树的高度(或深度)。例如,上图所示树的高度为3。
|
|
|
.有序(无序)树:若将树中结点的各子树看成是从左到右具有次序的,即不能交换,则称该树为有序树,否则称为无序树。
|
|
|
|