|
|
|
树（tree）是n（n≥0）个结点的有限集。n=0的树称为空树；当n≠0时，树中的结点应该满足以下两个条件：
|
|
|
|
|
|
（2）其余结点分成m （m≥0）个互不相交的有限集合T1,T2,…,Tm，其中每一个集合又都是一棵树，称T1,T2,…，Tm为根结点的子树。
|
|
|
|
以上定义是一个递归定义，它反映了树的固有特性，因为一棵树是由根和它的子树构成，而子树又是由子树的根和更小的子树构成。如下图所示的树中，A是根结点，其余结点分成三个互不相交的子集：S1=｛B，E，F｝, S2=｛C｝，S3=｛D, G，H，I，J，K｝,这三个集合分别构成了A的三棵子树；在S3构成的子树中，D是根结点，D又具有三棵子树，这三棵子树的根结点分别是G，H和I；对于结点G和I，它们的子树均为空。
|
|
|
|
|
|
|
|
图中树的表示类似于自然界中一棵倒长的树，“树型结构”由此得名，这种表示方法比较形象、直观，因而容易为人们所接受，是树的一种最常用的表示方法。树型结构除以上表示方法外，还有括号表示法、凹入表示法和嵌套集合表示形式。下图给出了上图中树的这三种表示形式。
|
|
|
|
|
|
|
|
在下图的树中，采用线段连接两个相关联的结点，如A和B，D和H等。其中A和D是上端结点，B和H是下端结点。称A、D分别是B、H的双亲（或父母或前件），B和H分别为A和D的子女（或孩子或后件）。由于E和F的双亲为同一结点，称E和F互为兄弟。在任何一棵树中，除根结点外，其他任何一个结点有且仅有一个双亲，有0个或多个子女，且它的子女恰巧为其子树的根结点。将一结点拥有的子女数称为该结点的度，树中所有结点度的最大值称为树的度。称树中连接两个结点的线段为树枝。在树中，若从结点Ki开始沿着树枝自上而下能到达结点Kj，则称从Ki到Kj存在一条路径，路径的长度等于所经过的树枝的条数。在下图中，从结点A到结点J存在一条路径，路径的长度为3；从D到K也存在一条路径，路径的长度为2。将从树根到某一结点Ki的路径中Ki前所经过的所有结点称为Ki的祖先；反之，以某结点Ki为根的子树中的任何一个结点都称为Ki的子孙。下图中，A、D、H均为J和K的祖先，而G、H、I、J和K均为D的子孙。
|
|
|
|
树中结点的层次：从树根开始定义，根结点为第一层，根的子女结点构成第二层，依次类推，若某结点Kj位于第i层，则其子女就位于第i+1层。称树中结点的最大层次数为树的深度或高度。下图中，A结点位于第一层，B、C、D位于第2层，E、F、G、H和I位于第三层等，整棵树的高度为4。
|
|
|
|
|
|
|
|
如果树中任意结点的子树均看成是从左到右有次序的，不能随意交换，则称该树是有序树；否则称之为无序树。如下图所示的两棵树，若看成是有序树，它们是不等价的；若看成是无序树，两者相等。
|
|
|
|
|
|
|
|
由m（m≥0）棵互不相交的树构成的集合称为森林。森林和树的概念十分相近，每个结点的子树的集合即为一个森林；而在森林中的每棵树之上加一个共同的根，森林就成为了一棵树。
|
|
|
|
二叉树（Binary Tree）是另一种树型结构，它的特点是每个结点至多只有两棵子树，在二叉树中不存在度大于2的结点，并且二叉树的子树有左右之分，它的次序是不能任意颠倒的。
|
|
|
