下一页

本章简介
  
 　树形结构是一类重要的非线性结构。树形结构是结点之间有分支，并具有层次关系的结构。它非常类似于自然界中的树。
    　树结构在客观世界中是大量存在的，例如家谱、行政组织机构都可用树形象地表示。
    树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程。
    　本章重点讨论二叉树的存储表示及其各种运算，并研究一般树和森林与二叉树的转换关系，最后介绍树的应用实例。

树的概念

1.家族树
    　在现实生活中，有入如下血统关系的家族可用树形图表示：
        张源有三个孩子张明、张亮和张丽；
        张明有两个孩子张林和张维；
        张亮有三个孩子张平、张华和张群；
        张平有两个孩子张晶和张磊。
               

    以上表示很像一棵倒画的树。其中"树根"是张源，树的"分支点"是张明、张亮和张平，该家族的其余成员均是"树叶"，而树枝(即图中的线段)则描述了家族成员之间的关系。显然，以张源为根的树是一个大家庭。它可以分成张明、张亮和张丽为根的三个小家庭；每个小家庭又都是一个树形结构。

2.树的定义
    树的递归定义：
      树(Tree)是n(n≥0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：
(1)有且仅有一个特定的称为根(Root)的结点；
(2)其余的结点可分为m(m≥0)个互不相交的子集T_l，T₂，…，T_m，其中每个子集本身又是一棵树，并称其为根的子树(Subree)。
　　　　　　
  注意：
    　树的递归定义刻画了树的固有特性：一棵非空树是由若干棵子树构成的，而子树又可由若干棵更小的子树构成。