树(树的定义 树的术语)

有序树、无序树(有序树 无序树)

树

树型结构是以分支关系定义的层次结构，它是一种重要的非线性结构。

树形结构在客观世界中广泛存在，例如人类的家庭族谱以及各种社会组织机构都可以用树形结构来表示，又如在计算机文件管理和信息组织方面也用到树形结构。

树的定义

树是由一个或多个结点组成的有限集合 T 。 其中：

（ 1 ）一个特定的结点称为该树的根（ root ）结点 ;

（ 2 ）结点之外的其余结点可分为 m （m ≥ 0 ）个互不相交的有限集合 T 1 ,T 2 ,......,T m ，且其中每一个集合本身又是一棵树，称之为根的子树（ subtree ）。

树的术语

（1） 结点的度(Degree)

树中的一个结点拥有的子树数称为该结点的度(Degree)。

一棵树的度是指该树中结点的最大度数。

度为零的结点称为叶子(Leaf)或终端结点。

度不为零的结点称分支结点或非终端结点。

除根结点之外的分支结点统称为内部结点。

根结点又称为开始结点。

（2） 孩子(Child)和双亲(Parents)

树中某个结点的子树之根称为该结点的孩子(Child)或儿子，相应地，该结点称为孩子的双亲(Parents)或父亲。

同一个双亲的孩子称为兄弟(Sibling)。

（3）祖先(Ancestor)和子孙(Descendant)

①路径（path）

若树中存在一个结点序列k1，k2，…，ki，使得ki是ki+1的双亲(1≤i<j)，则称该结点序列是从kl到kj的一条

路径(Path)或道路。

路径的长度指路径所经过的边(即连接两个结点的线段)的数目，等于j-1。

注意：

若一个结点序列是路径，则在树的树形图表示中，该结点序列"自上而下"地通过路径上的每条边。

从树的根结点到树中其余结点均存在一条惟一的路径。

②祖先(Ancestor)和子孙(Descendant)

若树中结点k到ks存在一条路径，则称k是ks的祖先(Ancestor)，ks是k的子孙(Descendant)。

一个结点的祖先是从根结点到该结点路径上所经过的所有结点，而一个结点的子孙则是以该结点为根的

子树中的所有结点。

约定：

结点k的祖先和子孙不包含结点k本身。

（4）结点的层数(Level)和树的高度（Height）

结点的层数(Level)从根起算：

根的层数为1

其余结点的层数等于其双亲结点的层数加1。

双亲在同一层的结点互为堂兄弟。

树中结点的最大层数称为树的高度(Height)或深度(Depth)。

注意，

很多文献中将树根的层数定义为0。

（5）有序树(OrderedTree)和无序树(UnoderedTree)

若将树中每个结点的各子树看成是从左到右有次序的(即不能互换)，则称该树为有序树(OrderedTree)；

否则称为无序树(UnoderedTree)。

注意：

若不特别指明，一般讨论的树都是有序树。

（6）森林(Forest)

森林(Forest)是m(m≥0)棵互不相交的树的集合。

树和森林的概念相近。删去一棵树的根，就得到一个森林；反之，加上一个结点作树根，森林就变为一

棵树。

有序树、无序树

若将树中每个结点的各子树看成是从左到右有次序的(即不能互换)，则称该树为有序树(OrderedTree)；

否则称为无序树(UnorderedTree)。

注意：若不特别指明，一般讨论的树都是有序树。

有序树

树中任意节点的子结点之间有顺序关系，这种树称为有序树

无序树

树中任意节点的子结点之间没有顺序关系，这种树称为无序树,也称为自由树，