|
|
|
树是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。
|
|
|
|
.有序（无序）树：若将树中结点的各子树看成是从左到右具有次序的，即不能交换，则称该树为有序树，否则称为无序树。
|
|
|
|
|
