第第66章树形结构章树形结构6
1树形结构的基本概念树形结构的基本概念6
2二叉树的基本概念和性质二叉树的基本概念和性质6
3二叉树的存储结构二叉树的存储结构6
5二叉树的遍历二叉树的遍历6
8树与森林树与森林6
10树的应用示例－哈夫曼树树的应用示例－哈夫曼树§6
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,
,Tmm，而且这些集合中的每一个又都是满足本定义的树，，而且这些集合中的每一个又都是满足本定义的树，称作称作TT的的子树子树(subTree)(subTree)
若T-{d0}T-{d0}为空，称为空，称TT无子树（或子无子树（或子树为空）
((递归定义递归定义))§6
1树结构的基本概念树结构的基本概念树形结构示例及相关术语树形结构示例及相关术语ABCDEFGIJLevel1Level2Level3Level
