1.树的概念
树是一种数据结构，它是由n(n>＝0)个有限节点组成的一个具有层次关系的集合，把它叫做“树”是因为它看起来像一棵倒挂的树。也就是说，它是根朝上，而叶朝下的。它具有以下的特点:每个节点有零个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每个子节点可以分为多个不相交的子树。
图12－5 树
树是n(n>＝0)个结点的有限集T。T为空时称为空树，若不为空，则它满足如下两个条件:(1)有且仅有一个特定的称为根(Root)的结点；(2)其余的结点可分为m(m>＝0)个互不相交的子集T l，T2，…，Tm，其中每个子集本身又是一棵树，称为根的子树(Subtree)。
树的递归定义表明了树的固有特性:一棵非空树是由若干棵子树构成的，而子树又可由若干棵更小的子树构成。
例如，有如图12－5所示的一棵树。
根据树的定义T＝{A，B，C，D，E，F，G，H}，其中A是根的结点，T中其余结点分别分成三个互不相交的子集，即T1＝{B}，T2＝{C，E，F，G，H}，T3＝{D}。T1、T2和T3是三棵根为A的子树；T2含有T21＝{E}，T22＝{F，G，H}两棵子树。
2.树的基本术语
若一个结点有子树，那么该结点称为子树根的“双亲”，子树的根是该结点的“孩子”。有相同双亲的结点互为“兄弟”。一个结点的所有子树上的任何结点都是该结点的后裔。从根结点到某个结点的路径上的所有结点都是该结点的祖先，以图12－6为例。(www.xing528.com)
结点的度:结点拥有的子树的数目，图12－6中结点C的度为2。
叶子:度为零的结点，图12－6中D、E、F都是叶子结点
树的度:树中结点的最大的度，图12－6中结点C的度最大，为2，因此树的度为2。
层次:根结点的层次为1，其余结点的层次等于该结点的双亲结点的层次加1。
树的高度:树中结点的最大层次，图12－6中树的高度为3。
无序树:如果树中结点的各子树之间的次序是不重要的，可以交换位置。
有序树:如果树中结点的各子树之间的次序是重要的，不可以交换位置。
森林:由0个或多个不相交的树组成。对森林加上一个根，森林即成为树；删去根，树即成为森林。
图12－6 树结构图
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
