|
本章简介 树形结构是一类重要的非线性结构树形结构是结点之间有分支并具有层次关系的结构它非常类似于自然界中的树 树结构在客观世界中是大量存在的例如家谱行政组织机构都可用树形象地表示 树在计算机领域中也有着广泛的应用例如在编译程序中用树来表示源程序的语法结构在数据库系统中可用树来组织信息在分析算法的行为时可用树来描述其执行过程 本章重点讨论二叉树的存储表示及其各种运算并研究一般树和森林与二叉树的转换关系最后介绍树的应用实例 树的概念 家族树 在现实生活中有入如下血统关系的家族可用树形图表示 张源有三个孩子张明张亮和张丽 张明有两个孩子张林和张维 张亮有三个孩子张平张华和张群 张平有两个孩子张晶和张磊 以上表示很像一棵倒画的树其中树根是张源树的分支点是张明张亮和张平该家族的其余成员均是树叶而树枝(即图中的线段)则描述了家族成员之间的关系显然以张源为根的树是一个大家庭它可以分成张明张亮和张丽为根的三个小家庭每个小家庭又都是一个树形结构 树的定义 树的递归定义 树(Tree)是n(n≥)个结点的有限集TT为空时称为空树否则它满足如下两个条件 ()有且仅有一个特定的称为根(Root)的结点 ()其余的结点可分为m(m≥)个互不相交的子集TlT…Tm其中每个子集本身又是一棵树并称其为根的子树(Subree) 注意 树的递归定义刻画了树的固有特性一棵非空树是由若干棵子树构成的而子树又可由若干棵更小的子树构成 树的表示（）树形图表示 树形图表示是树结构的主要表示方法 树的树形图表示中结点用圆圈表示结点的名字写在圆圈旁边（有时亦可写在圆圈内） 用该定义来分析上图(a)所示的树 图中的树由结点的有限集T={ABCDEFCHIJ}所构成其中A是根结点T中其余结点可分成三个互不相交的子集 T={BEFIJ} T={C} T={DGH} TT和T是根A的三棵子树且本身又都是一棵树例如T其根为B其余结点可分为两个互不相交的的子集T={E}和T={FIJ}它们都是B的子树显然T是只含一个根结点E的树而T的根F又有两棵互不相交的子树{I}和{J}其本身又都是只含一个根结点的树 （）树的其他表示法 ① 嵌套集合表示法 是用集合的包含关系来描述树结构 上图(a)树的嵌套集合表示法如图(b) ② 凹入表表示法 类似于书的目录上图(a)树的凹入表示法如图(c) ③ 广义表表示法 用广义表的形式表示的上图(a)树的广义表表示法如图(d) （A（B（EF（IJ））CD（GH））） 树结构的基本术语 （）结点的度(Degree) 树中的一个结点拥有的子树数称为该结点的度(Degree) 一棵树的度是指该树中结点的最大度数 度为零的结点称为叶子(Leaf)或终端结点 度不为零的结点称分支结点或非终端结点 除根结点之外的分支结点统称为内部结点 根结点又称为开始结点 （）孩子(Child)和双亲(Parents) 树中某个结点的子树之根称为该结点的孩子(Child)或儿子相应地该结点称为孩子的双亲(Parents)或父亲 同一个双亲的孩子称为兄弟(Sibling) （）祖先(Ancestor)和子孙(Descendant) ①路径（path） 若树中存在一个结点序列kk…ki使得ki是ki+的双亲(≤i<j)则称该结点序列是从kl到kj的一条路径(Path)或道路 路径的长度指路径所经过的边(即连接两个结点的线段)的数目等于j 注意 若一个结点序列是路径则在树的树形图表示中该结点序列自上而下地通过路径上的每条边 从树的根结点到树中其余结点均存在一条惟一的路径 ②祖先(Ancestor)和子孙(Descendant) 若树中结点k到ks存在一条路径则称k是ks的祖先(Ancestor)ks是k的子孙(Descendant) 一个结点的祖先是从根结点到该结点路径上所经过的所有结点而一个结点的子孙则是以该结点为根的子树中的所有结点 约定 结点k的祖先和子孙不包含结点k本身 （）结点的层数(Level)和树的高度（Height） 结点的层数(Level)从根起算 根的层数为 其余结点的层数等于其双亲结点的层数加 双亲在同一层的结点互为堂兄弟 树中结点的最大层数称为树的高度(Height)或深度(Depth) 注意 很多文献中将树根的层数定义为 （）有序树(OrderedTree)和无序树(UnoderedTree) 若将树中每个结点的各子树看成是从左到右有次序的(即不能互换)则称该树为有序树(OrderedTree)否则称为无序树(UnoderedTree) 注意 若不特别指明一般讨论的树都是有序树 （）森林(Forest) 森林(Forest)是m(m≥)棵互不相交的树的集合 树和森林的概念相近删去一棵树的根就得到一个森林反之加上一个结点作树根森林就变为一棵树 树形结构的逻辑特征 树形结构的逻辑特征可用树中结点之间的父子关系来描述 （） 树中任一结点都可以有零个或多个直接后继(即孩子)结点但至多只能有一个直接前趋(即双亲)结点 （） 树中只有根结点无前趋它是开始结点叶结点无后继它们是终端结点 （） 祖先与子孙的关系是对父子关系的延拓它定义了树中结点之间的纵向次序 （） 有序树中同一组兄弟结点从左到右有长幼之分 对这一关系加以延拓规定若k和k是兄弟且k在k的左边则kl的任一子孙都在k的任一子孙的左边那么就定义了树中结点之间的横向次序 |
