数据结构之树的概念[2]

凹入表表示法

广义表表示法

树的有关术语

度（Degree）一个结点拥有的子树数称为该结点的度

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

叶子（Leaf）和分支结点度为零的结点称为叶子或终端结点度不为零的结点称为分支结点或非终端结点除根结点之外的分支结点统称为内部结点根结点又称为开始结点

双亲（Parents）和孩子（Child）树中某个结点的子树之根称为该结点的孩子或儿子相应地该结点称为孩子的双亲或父亲

兄弟（Sibling）和堂兄弟同一个双亲的孩子称为兄弟双亲在同一层的结点互为堂兄弟

路径（Path）若树中存在一个结点序列kk…kj使得kj是ki+的双亲（≤i＜j）则称该结点序列是从ki到kj的一条路径或道路

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

祖先（Ancestor）和子孙（Descendant）一个结点的祖先是指从树的根到该结点所经分枝上的所有结点（包括根结点）一个结点的子树的所有结点都称为该结点的子孙

结点的层数（Level）是从根起算设根的层数为其余结点的层数等于其双亲结点的层数加

树的高度（Height）树中结点的最大层数称为树的高度或深度（Depth）

有序树（Ordered Tree）和无序树（Unordered Tree）若将树中每个结点的各子树看成是从左到右有次序的（即不能互换）则称该树为有序树否则称为无序树

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

对树中每个结点而言其子树的集合即为森林反之给一个森林加上一个结点使原森林的各棵树成为所加结点的子树便得到一棵树

[] []