二叉树.txt

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

二叉树

   
二叉树的定义：
        二叉树是n（n>=0）个有限结点构成的集合。n=0的树
   称为空二叉树；n>0的二叉树由一个根结点和两个互不相交
   的、分别称作左子树和右子树的子二叉树构成。

一.数据集合
       二叉树的数据集合即二叉树的结点集合，每个结点由数
   据元素和构造数据元素之间关系的指针组成。 
二.操作集合
   (1)初始化Initiate(T)：初始化二叉树T。
   (2)左插入结点InsertLeftNode(curr，x)：若当前结点curr
      非空，在curr的左子树插入元素值为x的新结点，原curr
      所指结点的左子树成为新插入结点的左子树，若插入成功
      返回新插入结点的指针，否则返回空指针。
   (3)右插入结点InsertRightNode(curr，x)：若当前结点curr
      非空，在curr的右子树插入元素值为x的新结点，原curr
      所指结点的右子树成为新插入结点的右子树，若插入成功
      返回新插入结点的指针，否则返回空指针。
   (4)左删除子树DeleteLeftTree(curr)：若当前结点curr非空，
      删除curr所指结点的左子树，若删除成功返回删除结点的
      双亲结点指针，否则返回空指针。
   (5)右删除子树DeleteRightTree(curr)：若当前结点curr非
      空，删除curr所指结点的右子树，若删除成功返回删除结
      点的双亲结点指针，否则返回空指针。
   (6)遍历二叉树Traverse(T，Visit())：若二叉树T存在则按
      某种次序访问二叉树T的每个结点，且每个结点只访问一
      次，访问结点时调用函数Visit()。二叉树的遍历次序主
      要有先序遍历次序、中序遍历次序、后序遍历次序和层序
      遍历次序四种。
   (7)撤消二叉树Destroy(T)：释放二叉树T的所有动态存储空间。
   实际上，撒消二叉树操作是遍历二叉树操作的一个具体应用。
   上面给出的操作集合只是其主要部分，实际使用的二叉树操作
集合中还包括如左删除结点、右删除结点等操作，为简洁起见，
这里未做介绍。

三.二叉树的性质
   性质1  若规定根结点的层次为0，则一棵非空二叉树的第i层
          上最多有2^i(i>=0)个结点。 
          
   性质2  若规定空树的深度为-1，则深度为k的二叉树的最大结
          点数是2^(k+1)-1(k≥-1)个。
 
   性质3  具有n个结点的完全二叉树的深度k为不超过lb(n+1)-1
          的最大整数。
          
   性质4  对于具有n个结点的完全二叉树，如果按照从上至下和
          从左至右的顺序对所有结点从0开始顺序编号，则对于
          序号为i的结点，有：
          (1)如果i>O，则序号为i的结点的双亲结点的序号为
             (i-1)／2(“／”表示整除)，如果i=0，则序号为i
             的结点为根结点，无双亲结点。
          (2)如果2i+l<n，则序号为i的结点的左孩子结点的序
             号为2i+1;如果2i+1≥n，则序号为i的结点无左孩子。
          (3)如果2i+2<n，则序号为i的结点的右孩子结点的序号
             为2i+2；如果2i+2≥n,则序号为i的结点无右孩子。
   
          性质4告诉我们，如果我们把完全二叉树按照从上至下
      和从左至右的顺序对所有结点顺序编号，则可以用一维数
      组存储完全二叉树。此时完全二叉树中任意结点的双亲结点
      序号、左孩子结点序号和右孩子结点序号均可以根据该结点
      的序号计算得出。
  
四.二叉树的设计和实现
    二叉树的存储结构主要有三种：顺序存储结构、链式存储结构
                                和仿真指针存储结构。
    1.二叉树的顺序存储结构
          由性质4可知，对于完全二叉树中任意结点i的双亲结点
      序号、左孩子结点序号和右孩子结点序号都可由公式计算得
      到。因此完全二叉树的结点可按从上至下和从左至右的次序
      存储在一维数组中，其结点之间的关系可由公式计算得到，
      这就是二叉树的顺序存储结构。
          但是，对于一般的非完全二叉树，如果仍按从上至下和
      从左至右的次序存储在一维数组中，则数组下标之间的关系
      不能反映二叉树中结点之间的逻辑关系。此时我们可首先在
      非完全二叉树中增添一些并不存在的空结点使之变成完全二
      叉树的形态，然后再用顺序存储结构存储。
          显然，对于完全二叉树，用顺序存储结构存储时既能节
      省存储空间，又能使二叉树的操作实现简单。但对于非完全
      二叉树，如果它接近于完全二叉树，即需要增加的空结点数
      目不多时，可采用顺序存储结构存储，但如果需要增加的空
      结点数太多时就不宜采用顺序存储结构存储。最坏的情况是
      右单支树，若右单支树采用顺序存储结构方法存储，则一棵
      深度为k的右单支树只有k个结点，却需分配2^k-1个存储单元。
      另外，使用中还需要识别数据域为空的情况。
    2.二叉树的链式存储结构
          二叉树的链式存储结构是用指针建立二叉树中结点之间
      的关系的。二叉树最常用的链式存储结构是二叉链。二叉链
      存储结构的每个结点包含三个域，分别是数据域data、左孩
      子指针leftChild和右孩子指针域rightChild。二叉链存储
      结构中每个结点的图示结构为：
                   leftChild  |  data  |  rightChild
    3.二叉树的仿真指针
          在使用数组存储数据元素时，我们可在存储数据元素的
      数组中增加一个或几个数组下标域，这些数组下标域的值表
      示了该数组中某个数据元素的下标。由于在数组中增加的数
      组下标域仿真了链式存储结构中的指针域，所以这种存储结
      构也称作仿真指针。
          二叉树的仿真指针存储结构是用数组存储二叉树中的结
      点，数组中每个结点除数据域外，在增加仿真指针域用于仿
      真常规指针建立二叉树结点之间的关系。