树.txt

数据结构是计算机学科的一门核心课程。数据结构课程的 任务是讨论现实世界中数据的各种逻辑结构、在计算机中的存 储结构以及实现各种操作的算法等问题。掌握如何组织数据、 如何存储数据和如何处理数据的基

树
   

树是由n(n≥0)个结点构成的集合。n＝0的树称为空树；对n>O
的树T有：
    (1)有一个特殊的结点称为根结点，根结点没有前驱结点；
    (2)当n>l时，除根结点外其他结点被分成m(m>0)个互不相交的
       集合T1，T2,…，Tm，其中每一个集合Ti(1≤i≤m)本身又
       是一棵结构和树类同的子树。
   显然树是递归定义的。因此，在树结构(以及二叉树结构)的算
法中将会频繁地出现递归。
   树结构表示了数据元素之间的层次关系。

下面介绍树的其他一些常用术语。
    结点：由数据元素和构造数据元素之间关系的指针组成。
    结点的度：结点所拥有的子树的个数称为该结点的度。
    叶结点：度为0的结点称为叶结点，叶结点也称作终端结点。
    分支结点：度不为0的结点称为分支结点，分支结点也称作非终
              端结点。显然，一棵树中除叶结点外的所有结点都
              是分支结点。
    孩子结点：树中一个结点的子树的根结点称作这个结点的孩子
              结点。孩子结点也称作后继结点。
    双亲结点：若树中某结点有孩子结点，则这个结点就称作它的
              孩子结点的双亲结点。双亲结点也称作直接前驱结点。
    兄弟结点：具有相同的双亲结点的结点称为兄弟结点。
    树的度：树中所有结点的度的最大值称为该树的度。
    结点的层次：从根结点到树中某结点所经路径上的分支数称为
                该结点的层次。根结点的层次规定为o，这样其他
                结点的层次就是它的双亲结点的层次加1。
    树的深度；树中所有结点的层次的最大值称为该树的深度。
    无序树：树中任意一个结点的各孩子结点之间的次序构成无关紧
            要的树称为无序树。通常树指无序树。
    有序树：树中任意一个结点的各孩子结点有严格排列次序的树称
            为有序树。二叉树是一种有序树，因为二叉树中每个结
            点的孩子结点都确切地定义为是该结点的左孩子结点或
            是该结点的右孩子结点。
    森林：m(m≥o)棵树的集合称为森林。自然界中树和森林的概念
          差别很大，但在数据结构中树和森林的概念差别很小。从
          定义可知，一棵树由根结点和m个子树组成，若把树中的
          根结点删除，则树就变成了包含m棵树的森林。当然，根
          据定义，一棵树也可以称作森林。
   
    树的抽象数据类型
    1.数据集合
          树的数据集合即数的结点集合，每个结点由数据元素和构造
      数据元素之间关系的指针组成。
    2.操作集合
    （1）创建数Create(T): 创建数T。
    （2）撤消树Destroy(T): 释放树T的所有动态存储空间。
    （3）双亲结点Parent(T,curr): 若树T存在，则返回树T中当前结
         点curr的双亲结点指针，否则返回空指针
    （4）左孩子结点LeftChild(T,curr): 若树T存在且当前指针curr
         存在，则返回当前结点curr的左孩子结点（或称作第一个孩
         子结点）指针，否则返回空指针。
    （5）右兄弟结点RightChild(T,curr): 若树T存在且当前指针curr
         存在，则返回当前结点curr的右兄弟结点指针，否则返回空
         指针。
    （6）遍历树Traverse(T,Visit()): 若树T存在，则按某种遍历方
         法访问树T的每个结点，且每个结点只访问一次，访问结点时
         调用函数Visit()。树的遍历方法主要有先根遍历方法，后根
         遍历方法和层序遍历方法三种。