第第66章树形结构章树形结构6.16.1树形结构的基本概念树形结构的基本概念6.26.2二叉树的基本概念和性质二叉树的基本概念和性质6.36.3二叉树的存储结构二叉树的存储结构6.56.5二叉树的遍历二叉树的遍历6.86.8树与森林树与森林6.106.10树的应用示例－哈夫曼树树的应用示例－哈夫曼树§6.1.1§6.1.1树结构的定义树结构的定义数据对象数据对象DD：：nn个数据元素的有穷集合（个数据元素的有穷集合（nn≥≥00））数据关系数据关系R:R:n=0n=0时，称为时，称为空树空树；；n>0n>0时，它满足以下条件：时，它满足以下条件：(1)(1)有且仅有一个结点有且仅有一个结点dd00∈∈DD，满足：不存在任何，满足：不存在任何dd∈∈DD，使，使>∈∈RR。我们称它为树的。我们称它为树的根根(Root)(Root)。。(2)(2)除根结点除根结点dd00外，外，DD上每个结点上每个结点dd（若有的话），总存在一个（若有的话），总存在一个唯一的结点唯一的结点d'd'∈∈DD，，dd≠≠d'd'，使得，使得∈∈RR。。(3)(3)若若T-{d0}T-{d0}非空，则非空，则T-{d0}T-{d0}可分成可分成mm个个(m>0)(m>0)不相交的集合不相交的集合TT11,T,T22,...,T,...,Tmm，而且这些集合中的每一个又都是满足本定义的树，，而且这些集合中的每一个又都是满足本定义的树，称作称作TT的的子树子树(subTree)(subTree)。若。若T-{d0}T-{d0}为空，称为空，称TT无子树（或子无子树（或子树为空）。树为空）。((递归定义递归定义))§6.1§6.1树结构的基本概念树结构的基本概念树形结构示例及相关术语树形结构示例及相关术语ABCDEFGIJLevel1Level2Level3Level4Depth=4A(b)(c)ø(a)分支分支(Branch)(Branch)：结点之间的二元关系。：结点之间的二元关系。入度入度(InDegree)(InDegree)：：xx的前驱的个数称为的前驱的个数称为xx的入度。的入度。结点结点(Node)(Node)：数据元素＋若干个指向子树的分支。：数据元素＋若干个指向子树的分支。度度(Degree)(Degree)//出度出度(OutDegree)(OutDegree)：结点拥有的子树（后继）的个数：结点拥有的子树（后继）的个数称为该结点的度，也称为出度。称为该结点的度，也称为出度。树的度树的度：树中所有结点的：树中所有结点的度的最大值度的最大值叶子结点叶子结点(LeafNode)(LeafNode)：无后继（子树）的结点称为叶子。：无后继（子树）的结点称为叶子。分支结点分支结点(BranchNode)(BranchNode)：有后继的结点称为分枝结点。：有后继的结点称为分枝结点。层次层次(Level)(Level)：根为第：根为第11层，对任何其它结点，若它父亲为第层，对任何其它结点，若它父亲为第kk层层结点，则它为第结点，则它为第(k+1)(k+1)层结点层结点((层号为层号为k+1)k+1)。。儿子结点儿子结点(Sons)(Sons)；双亲（父亲）；双亲（父亲）(Parents)(Parents)；祖先；祖先(Ancestor)(Ancestor)；；后代后代(Descendants)(Descendants)；兄弟；兄弟(Brothers)(Brothers)；；··堂兄弟堂兄弟(Cousin)(Cousin)；；深度深度(depth)(depth)：树中的具有：树中的具有最大层号最大层号的结点的的结点的层号，称为树的深度层号，称为树的深度//高度。高度。祖辈祖辈（上层）（上层）(Forerunner)(Forerunner)：层号比结点：层号比结点xx小的结点，称为小的结点，称为xx的祖辈（上层）的祖辈（上层）后辈后辈（下层）（下层）(Latecomes)(Latecomes)：层号比结点：层号比结点xx大的结点，称为大的结点，称为xx的后辈（下层）的后辈（下层）森林森林(Forest)(Forest)：相互：相互m(mm(m≥0)≥0)不相交的树的不相交的树的集合称为森林。集合称为森林。反过来树也可以有森林来定义：任何一棵非空树是反过来树也可以有森林来定义：任何一棵非空树是一个二元组一个二元组Tree=(root,F)rootTree=(root,F)root为根结点，为根结点，FF为为子树森林子树森林有序树有序树::子树的次序不能互换子树的次序不能互换无序树无序树::子树的次序可以互换子树的次序可以互换ABCDEFGIJ线性结构与树形结构比较线性结构与树形结构比较线性结构线性结构第一个数据元素第一个数据元素（无前驱）（无前驱）最后一个数据元素最后一个数据元素（...
