|
本章简介 树形结构是一类重要的非线性结构树形结构是结点之间有分支并具有层次关系的结构它非常类似于自然界中的树 树结构在客观世界中是大量存在的例如家谱行政组织机构都可用树形象地表示 树在计算机领域中也有着广泛的应用例如在编译程序中用树来表示源程序的语法结构;在数据库系统中可用树来组织信息; 在分析算法的行为时可用树来描述其执行过程 本章重点讨论二叉树的存储表示及其各种运算并研究一般树和森林与二叉树的转换关系最后介绍树的应用实例 树的概念 家族树 在现实生活中有入如下血统关系的家族可用树形图表示 张源有三个孩子张明张亮和张丽; 张明有两个孩子张林和张维; 张亮有三个孩子张平张华和张群; 张平有两个孩子张晶和张磊 以上表示很像一棵倒画的树其中树根是张源树的分支点是张明张亮和张平该家族的其余成员均是树叶而树枝(即图 中的线段)则描述了家族成员之间的关系显然以张源为根的树是一个大家庭它可以分成张明张亮和张丽为根的三个小家庭; 每个小家庭又都是一个树形结构 树的定义 树的递归定义 树(Tree)是n(n≥)个结点的有限集TT为空时称为空树否则它满足如下两个条件 ()有且仅有一个特定的称为根(Root)的结点; ()其余的结点可分为m(m≥)个互不相交的子集T l T …T m 其中每个子集本身又是一棵树并称其为根的 子树 (Subree) 注意 树的递归定义刻画了树的固有特性一棵非空树是由若干棵子树构成的而子树又可由若干棵更小的子树构成 |
