二叉树（C语言）_c语言 二叉树

二叉树

二叉树的定义

• 二叉树$T$：一个有穷的结点的集合。
  这个结合可以为空
  如不为空，则它由根结点和称为其 左子树$T_L$ 和 右子树$T_R$ 的两个不相交的二叉树组成。

• 二叉树具体五种基本形态。

  1. 空树
  2. 只有一个结点
  3. 只有一个结点和左子树
  4. 只有一个结点和右子树
  5. 有一个结点和左右两个子树
     

• 二叉树的子树有左右顺序之分

• 特殊二叉树

  1. 斜二叉树（Skewed Binary Tree）：只有左（右）子树的二叉树
     

  2. 完美二叉树（Perfect Binary Tree）或满二叉树（Full Binary Tree）

  

  3. 完全二叉树（Complete Binary Tree）
     有$n$个结点的二叉树，对树中的结点按从上到下、从左到右顺序进行编号，编号为$i(1\le i\le n)$结点与满二叉树中编号为$i$的结点在二叉树中位置相同
     例子：
     
     但是下面这个不是完全二叉树：
     

二叉树的几个重要性质

• 一个二叉树第$i$层的最大结点数为：$2^{i-1},i\ge 1$。

• 深度为$k$的二叉树有最大结点总数为：$2^{k-1},k\ge i$

• 对任意非空二叉树$T$,若$n_0$表示叶结点的个数，$n_1$表示度为1的非叶结点，$n_2$表示度为2的非叶结点的个数那么两者满足关系$n_0=n_2+1$。
  从边的角度考虑，边的总数:

  1. 除了根结点，每个结点之上都连着一条边：$n_0+n_1+n_2$
  2. 每个结点下面都有0条、1条或者2条边：$0\times n_0+1\times n_1+2\times n_2$

  所以有：
  $$n_0+n_1+n_2=0\times n_0+1\times n_1+2\times n_2$$
  化简得：
  $$n_0=n_2+1$$

二叉树的抽象数据类型定义

• 数据名称：二叉树
• 数据对象集：一个有穷的节点集合。
  若不为空，则由根结点和其左、右二叉子树组成。
• 操作集：$BT\in BinTree$,$Item\in ElementType$，重要操作有：
  1. Boolean IsEmpty(BinTree BT)：判断BT是否为空；
  2. void Traversal(BinTree BT)：遍历，按某顺序访问每个结点；
     1. void PreOrderTraversal(BinTree BT)：先序—根、左子树、右子树；
     2. void InOrderTraversal(BinTree BT)：中序—左子树、根、右子树；
     3. void PostOrderTraversal(BinTree BT)：后序—左子树、右子树、根；
     4. void LevelOrderTraversal(BinTree BT)：层次遍历—从上到下，从左到右。
  3. BinTree CreatBinTree()：创建一个二叉树。

二叉树的存储结构

1. 顺序存储结构

   • 完全二叉树：按从上至下、从左到右顺序存储$n$个结点的完全二叉树的结点父子关系
     
     • 非根结点$(序号i>1)$的父结点序号是$i/2$;
     • 结点$(序号为i)$的左孩子结点的序号是$2i$（$2i\le n$，否则没有左孩子）；
     • 结点$(序号为i)$的右孩子结点的序号是$2i+1$（$2i+1\le n$，否则没有右孩子）；
   • 非完全二叉树（一般二叉树）：将一般的二叉树补充成对应的完全二叉树之后，也可以采用上面的方法，只不过会造成空间的浪费。
     

2. 链式存储结构
   

   

   struct TreeNode{
       ElementType Data;
       struct TreeNode *Left;
       struct TreeNode *Right;
   };
   typedef struct TreeNode *BinTree;
   1
   2
   3
   4
   5
   6

二叉树的遍历

二叉树遍历的核心问题：二维结构的线性化

1. 先序遍历
   递归实现：

   1. 访问根结点；
   2. 先序遍历其左子树；
   3. 先序遍历其右子树。

   void PreOrderTraversal(BinTree BT)
   {
       if(BT)
       {
           printf("%d",BT->Data);//先访问根结点
           PreOrderTraversal(BT->Left);//先序遍历左子树
           PreOrderTraversal(BT->Right);//先序遍历左子树
       }
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9

   非递归实现（堆栈实现）：

   1. 遇到一个结点，访问它，把它压栈，并去遍历它的左子树；
   2. 当左子树遍历结束后，从栈顶弹出这个结点；
   3. 然后按其右指针再去遍历该结点的右子树。

   void PreOrderTraversal(BinTree BT)
   {
       BinTree T=BT;
       Stact S = CreatStack(MaxSize);//创建并初始化堆栈
       while( T || !IsEmpty(S) )
       {
           //一直向左并将沿途结点压入堆栈
           while(T)
           {
               printf("%5d",T->Data);//（访问）打印结点
               Push(S,T);
               T=T->Left;
           }
           if(!IsEmpty(S))
           {
               T=Pop(s);//结点弹出堆栈
               T=T->Right;//转向右子树
           }
       }
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20

   例如：
   遍历顺序：A B D F E C G H I
   

2. 中序遍历
   递归实现：

   1. 中序遍历其左子树；
   2. 访问根结点；
   3. 中序遍历其右子树。

   void InOrderTraversal(BinTree BT)
   {
       if(BT)
       {
           InOrderTraversal(BT->Left);//中序遍历其左子树
           printf("%d",BT->Data);//先访问根结点
           InOrderTraversal(BT->Right);//中序遍历其右子树
       }
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9

   非递归实现（堆栈实现）：

   1. 遇到一个结点，就把他压栈，并去遍历他的左子树；
   2. 当左子树遍历结束后，从栈顶弹出这个结点并访问它；
   3. 然后按其右指针再去遍历该结点的右子树。

   void InOrderTraversal(BinTree BT)
   {
       BinTree T=BT;
       Stact S = CreatStack(MaxSize);//创建并初始化堆栈
       while( T || !IsEmpty(S) )
       {
           //一直向左并将沿途结点压入堆栈
           while(T)
           {
               Push(S,T);
               T=T->Left;
           }
           if(!IsEmpty(S))
           {
               T=Pop(s);//结点弹出堆栈
               printf("%5d",T->Data);//（访问）打印结点
               T=T->Right;//转向右子树
           }
       }
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20

   例如：
   遍历顺序：D B E F A G H C I

   

3. 后序遍历
   递归实现：

   1. 后序遍历其左子树；
   2. 后序遍历其右子树；
   3. 访问根结点。

   void PostOrderTraversal(BinTree BT)
   {
       if(BT)
       {
           PostOrderTraversal(BT->Left);//后序遍历其左子树
           PostOrderTraversal(BT->Right);//后序遍历其右子树
           printf("%d",BT->Data);//先访问根结点
       }
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9

   非递归实现（堆栈实现）：
   后序遍历的顺序是左结点–右结点–根结点，用额外的一个堆栈按顺序存储结点，最后在将所有结点出栈并访问，因为堆栈有先进后出的特点，所有进栈的顺序为根结点–右结点–左结点。观察先序遍历的非递归实现，可以知道访问结点顺序为根结点–左结点–右结点，与进栈顺序差别只是左右结点的访问顺序不同，所以可以利用先序遍历的算法，只要先遍历右子树再遍历左子树，这样结点访问顺序就变成了根结点–右结点–左结点，在把访问用进栈代替，就可以用额外的一个堆栈按照根结点–右结点–左结点的顺序进栈，将所有结点进栈之后，依次出栈，并访问，就会按照左结点–右结点–根结点的顺序访问结点了。

   void PostOrderTraversal(BinTree BT)
   {
       BinTree T=BT;
       Stact S1 = CreatStack(MaxSize);//创建并初始化堆栈S1
       Stact S2 = CreatStack(MaxSize);//创建并初始化堆栈S2，用于按照顺序存储所有结点
       while( T || !IsEmpty(S1) )
       {
           //一直向右并将沿途结点压入堆栈
           while(T)
           {
               Push(S2,T);//进栈，用于存储所有结点
               Push(S1,T);
               T=T->Right;
           }
           if(!IsEmpty(S1))
           {
               T=Pop(S1);//结点弹出堆栈
               T=T->Left;//转向左子树
           }
       }
       //出栈并访问
       while(!IsEmpty)
       {
           T=Pop(S2);
           printf("%d\n",T->Data);
       }
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21
   22
   23
   24
   25
   26
   27

   例如：
   遍历顺序：D E F B H G I C A

   

• 观察可以发现：先序、中序和后序遍历过程中经过结点的路线是一样的，只是访问各结点的时机不同。

• 层序遍历

  • 从结点访问其左、右结点

  • 访问左儿子后，右儿子结点怎么办？

    • 需要一个存储结构保存暂时不访问的结点
    • 存储结构：堆栈、队列

  • 队列实现：遍历从根结点开始，首先将根结点入队，然后开始执行循环：结点出队、访问该结点、其左右儿子入队。
    基本过程：先根结点入队，然后：

    1. 从队列中取出一个元素；
    2. 访问该元素所指结点；
    3. 若该元素所指结点的左、右孩子结点非空，则将其左、右孩子的指针顺序入队。

    void LevelOrderTraversal(BinTree BT)
    {
        Queue Q;
        BinTree T;
        //如果树是空的则直接返回
        if(!BT)
        {
            return;
        }
        Q=CreatQueue(MaxSize);//创建并初始化队列Q
        AddQ( Q , BT );//将根结点入队
        while(!IsEmptyQ(Q))
        {
            T=Delete(Q);
            printf("%d\n",T->Data);//访问取出队列的结点
            if(T->Left)
            {
                AddQ(Q,T->Left);
            }
            if(T->Right)
            {
                AddQ(Q,T->Right);
            }
        }
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25

遍历二叉树的应用

1. 输出二叉树中的叶子结点

   • 在二叉树的遍历算法中增加检测结点的“左右子树是否都为空”。

     void PreOrderTraversal(BinTree BT)
     {
         if(BT)
         {
             if(!BT->Left&&!BT->Right)
             {
             printf("%d",BT->Data);//在先序遍历的代码基础上，给访问加个条件，只有叶子结点才访问。
             }
             PreOrderTraversal(BT->Left);//先序遍历左子树
             PreOrderTraversal(BT->Right);//先序遍历左子树
         }
     }
     1
     2
     3
     4
     5
     6
     7
     8
     9
     10
     11
     12

2. 求二叉树的高度
   二叉树的告诉等于左、右子树高度最大的那个加一。
   

   int PostOrderGetHeight(BinTree BT)
   {
       int HL=0,HR=0,MaxH=0;
       if(BT)
       {
           HL=PostOrderGetHeight(BT->Left);//求左子树深度
           HR=PostOrderGetHeight(BT->Right);//求右子树深度
           MaxH=(HL>HR)?HL:HR;//取左右子树较大的深度
           return (MaxSize+1);//返回树的告诉
       }
       else
       {
           return 0;//空树返回深度为0
       }
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15

3. 二元运算表达式树及其遍历

   二元运算表达式树：叶结点是运算数，非叶结点是运算符号，用于描述一个表达式。

   

   • 三种遍历可以得到三种不同的访问结果：
     1. 先序遍历得到前缀表达式：$++a\ast bc\ast +\ast defg$
     2. 中序遍历得到中缀表达式：$a+b\ast c+d\ast e+f\ast g$（并不准确，因为没有加括号，所以会受到优先级的影响）
     3. 后序遍历得到后缀表达式：$abc\ast +de\ast f+g\ast +$

4. 由两种遍历确定二叉树
   问：已知三种遍历中的任意两种遍历序列，能否唯一确定一棵二叉树呢？
   答：不一定，两种遍历序列里必须要有中序遍历才行。

   • 先序和中序遍历来确定一棵二叉树
     1. 根据先序遍历序列第一个结点确定根结点；
     2. 根据根结点在中序遍历序列中分割出两个子序列；
     3. 对左子树和右子树分别递归使用相同的方法继续分解。
   • 后序和中序遍历来确定一棵二叉树与上面类似。