二叉树

二叉树(Binary Tree):一个有穷的结点集合

  • 集合可以为空
  • 若不为空，则它是由根结点以及它的左子树Tl和右子树Tr的两个不相交的二叉树组成
  • 二叉树五种具体基本形态
    • 空树/叶结点/只有左子树/只有右子树/同时具有左子树和右子树
    • 二叉树的子树有左右顺序之分

二叉树类型(结点分布形态的角度)

  • 斜二叉树(Skewed Binary Tree)
    • 只在一个方向上有孩子结点，实际上相当于一个线性结构
  • 完美二叉树(Perfect Binary Tree)
    • 满二叉树(Full Binary Tree)
  • 完全二叉树(Complete Binary Tree)
    • 完全二叉树和满二叉树的关系：
      • 有n个结点的二叉树，对树中结点按从上至下、从左到右顺序进行编号，编号为i(1<=i<=n)结点与满二叉树中编号为i结点在二叉树中位置相同(允许缺失最后几个结点)

二叉树的几个重要性质

  • 一个二叉树第i层的最大结点数为：2i−1,i≥12^{i-1},i\geq1
  • 深度为k的二叉树有最大结点总数(满二叉树)为：−1+2k,k≥1-1+2^k,k\geq1
  • 对任何非空二叉树T，若n0n_0表示叶结点的个数，n2n_2是度为2的非叶结点个数
    • 则二者满足关系：n0=n2+1n_0=n_2+1
      • 边总数=n−1=2n2+n1=n-1=2n_2+n_1 ——> n=2n2+n1+1n=2n_2+n_1+1
      • 结点总数=n=n0+n1+n2=n=n_0+n_1+n_2 ——> n0=n2+1n_0=n_2+1

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

类型名称：二叉树
数据对象集：一个有穷的结点集合
若不为空，则由根结点和其左、右二叉树组成
操作集：BT ∈ BinTree，Item ∈ ElementType，重要操作有：
Boolean IsEmpty(BinTree BT):判别BT是否为空;
void Traversal(BinTree BT):遍历，按某顺序访问各个结点;
BinTree CreatBinTree():创建一个二叉树;
对二叉树而言，很多算法是建立在遍历之上的(很多算法需要先将二叉树的结点元素整体先读一遍)
常用的遍历方法有：
void PreOrderTraversal(BinTree BT):先序————根、左子树、右子树;
void InOrderTraversal(BinTree BT):中序————左子树、根、右子树;
void PostOrderTraversal(BinTree BT):后序————左子树、右子树、根;
void LevelOrderTraversal(BinTree BT):层序遍历，从上到下、从左到右;

二叉树的存储结构

二叉树顺序存储实现

适合完全二叉树：

  • 按从上至下、从左到右顺序存储(完全二叉树从左到右没有空结点)
  • n个结点的完全二叉树的结点父子关系：
    • 非根结点(序号i>1)的父结点的序号是⌊i/2⌋;
    • 结点(序号为i)的左孩子结点的序号是2i，(若2i<=n，否则没有左孩子);
    • 结点(序号为i)的右孩子结点的序号是2i+1，(若2i+1<=n，否则没有右孩子);

对一般二叉树也可以采用这种结构，但需要在其相对完全二叉树而言空缺的位置上设置为空，因此会造成较多的空间浪费

二叉树链式存储实现

typedef struct TreeNode *BinTree;
typedef BinTree Position;
struct TreeNode
{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

二叉树的遍历

例：假设二叉树结构为根结点A 左子树(B(DF(E))) 右子树(C(G(H)I))

先序遍历

遍历过程为：

  • 访问根结点
  • 先序遍历其左子树
  • 先序遍历其右子树

上例先序遍历结果=>A B D F E C G H I

先序遍历递归算法

void PreOrederTraversal(BinTree BT)
{
    if(BT)
    {
        printf("%d",BT->Data);
        PreOrderTraversal(BT->Left);
        PreOrderTraversal(BT->Right);
    }
}

先序遍历非递归算法

  • 递归本质就是靠堆栈实现，因此非递归算法也可以借助堆栈
void PreOrderTraversal(BinTree BT)
{
    BinTree T=BT;                   //创建一个用于遍历的二叉树指针
    Stack S=CreateStack(MaxSize)    //创建并初始化堆栈S
    while(T||!IsEmpty(S))
    {
        while(T)                    //一直向左直到叶结点将沿途结点压入堆栈
        {
            Push(S,T);
            cout<<T->Data<<endl;    //(访问)打印结点
            T=T->Left;
        }
        if(!IsEmpty(S))
        {
            T=Pop(S);               //结点弹出堆栈(左子树先出)
            T=T->Right;             //然后转向右子树(一步)
        }
    }
}

中序遍历

遍历过程为：

  • 中序遍历其左子树
  • 访问根结点
  • 中序遍历其右子树

上例中序遍历结果=>D B E F A G H C I

中序遍历递归算法

void InOrederTraversal(BinTree BT)    
{
    if(BT)
    {
        PreOrderTraversal(BT->Left);
        printf("%d",BT->Data);
        PreOrderTraversal(BT->Right);
    }
}

中序遍历非递归算法(结构基本同先序的非递归遍历，只有访问时机不一样)：

  • 遇到一个结点，将其压栈，并遍历左子树
  • 当左子树遍历结束后，从栈顶弹出这个结点并访问它
  • 按其右指针再去中序遍历该结点的右子树
void InOrderTraversal(BinTree BT)
{
    BinTree T=BT;
    Stack S=CreateStack(MaxSize)  
    while(T||!IsEmpty(S))
    {
        while(T)                 
        {
            Push(S,T);
            T=T->Left;
        }
        if(!IsEmpty(S))
        {
            T=Pop(S);             
            cout<<T->Data<<endl;        
            T=T->Right;          
        }
    }
}

后序遍历

遍历过程为：

  • 后序遍历其左子树
  • 后序遍历其右子树
  • 访问根结点

上例后序遍历结果=>D E F B H G I C A

后序递归遍历算法

void PostOrederTraversal(BinTree BT)
{
    if(BT)
    {
        PostOrderTraversal(BT->Left);
        PostOrderTraversal(BT->Right);
        printf("%d",BT->Data);
    }
}

后序非递归遍历算法(非递归写法与前序中序的思路并不完全一致)

  • 算法1:采用双堆栈，使用一个堆栈记录另一个堆栈使用根右左的顺序时元素的入栈顺序，然后将该堆栈的元素逆序输出
void PostOrderTraversal(BinTree BT)
{
    BinTree T=BT;
    Stack S1,S2;
    S1=S2=CreateStack(MaxSize)  
    while(T||!IsEmpty(S))
    {
        while(T)                 
        {
            Push(S1,T);
            Push(S2,T);
            T=T->Right;
        }
        if(!IsEmpty(S1))
        {
            T=Pop(S1);   
            T=T->Left;         
        }   
    }
    while(!IsEmpty(S2))
    {
        T=Pop(S2);
        cout<<T->Data<<endl;
    }
}
  • 算法2:单堆栈实现后序遍历
void PostOrderTraversal(BinTree BT)
{
    BinTree T,pre;
    Stack S;
    T=pre=BT;
    while(T||!IsEmpty(S1))
    {
        while(T)
        {
            Push(S,T);
            T=T->Left;
        }
        if(!IsEmpty(S2))
        {
            T=Pop(S1);  
            if(!T->Right||pre=T->Right)
            {
                cout<<T->Data<<endl;
                pre=T;
            }
            else
            {
                Push(S,T);
                T=T->Right;
            }
        }
    }
}

先序、中序和后序遍历过程：
遍历过程中经过结点的路线一样(都是先先向左走，走到头以后回到根，然后再向右走)只是访问(如打印)各结点的时机不同

层序遍历

二叉树遍历的核心问题：二维结构的线性化(二维的树转化为一维的线性访问序列)

  • 从结点访问其左、右孩子结点
  • 访问左孩子后，右孩子怎么办
    • 链表存在的一大问题：后面的结点不知道前面结点的位置
    • 需要一个存储结构保存暂时不访问的结点
    • 存储结构：堆栈、队列
      • 两种存储结构都可以，只不过堆栈的目的是保存自身，队列是保存右孩子结点

非递归算法：队列实现

  • 遍历从根结点开始，首先将根结点入队，然后执行循环：结点出队列、访问该结点、左右孩子入队
  • 遍历过程为：
    • 从队列中取出一个元素，访问该元素所指结点
    • 若该元素所指结点的左、右孩子结点非空，则将其左、右孩子的指针顺序入队

上例层序遍历结果=>A B C D F G I E H

void LevelOrderTraversal(BinTree BT)
{
    Queue Q;
    BinTree T=BT;
    Q=CreateQueue(MaxSize);
    AddQ(Q,T);
    while(IsEmptyQ(Q))
    {
        T=DeleteQ(Q);
        cout<<T->Data<<endl;
        if(T->Left)AddQ(Q,T->Left);
        if(T->Right)AddQ(Q,T->Right);
    }
}

递归算法：求出二叉树高度，逐层遍历，以每层高度控制递归深度

void onelevelTraversal(BinTree BT,int height){
    if(!BT||!height)return NULL;
    else if(height==1){
        cout<<BT->Data;
        return;
    }
    onelevelTraversal(BT->Left,h-1);
    onelevelTraversal(BT->Right,h-1);
}
void LevelOrderTraversal(BinTree BT){
    int height=Getheight(BT);
    for(int i=1;i<=height;i++)onelevelTraversal(BT,i);
}

层序遍历的另一种思路：由于二叉树的特点，设根结点的下标为i，则左孩子结点的下标2* i，右孩子结点的下标为2* i+1
使用前序中序遍历的方法，在遍历时将孩子结点用数组存储(适用于完全二叉树情况)

void LevelOrderTraversal(BinTree BT,int i,int* levelorder) //i的初值为1
{  
    levelorder[i]=BT->Data;
    if(BT->Left)LevelOrderTraversal(BT->Left,i*2);
    if(BT->Right)LevelOrderTraversal(BT->Right,i*2+1);
}

从宏观角度来看：

  • 前序、中序、后序遍历属于DFS
  • 层序遍历属于BFS

遍历二叉树的应用

输出二叉树中的叶子结点

  • 在二叉树的遍历算法中增加检测结点的“左右子树是否都为空”
void PreOrederTraversal(BinTree BT)
{
    if(BT)if(!BT->Left&&!BT->Right)
    {
        printf("%d",BT->Data);
        PreOrderTraversal(BT->Left);
        PreOrderTraversal(BT->Right);
    }
}

求二叉树的高度

int Getheight(BinTree BT)
{
    int HL=0,HR=0,MaxH;
    if(BT)
    {
        HL=PostOrderTraversal(BT->Left);
        HR=PostOrderTraversal(BT->Right);
        MaxH=(HL>HR)?HL:HR;                 //注意这里只能是后序遍历
        return MaxH+1;
    }
    return 0;
}

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

  • 叶子结点是操作数，非叶结点是运算符
  • 三种遍历可以得到三种不同的访问结果：
    • 先序遍历得到前缀表达式，如：+ + a * b c * + * d e f g
    • 中序遍历得到中缀表达式，如：a + b * c + d * e + f * g
      • 中缀表达式会受到运算符优先级的影响，所以直接遍历的结果可能不符合本来的运算规则
    • 后序遍历得到中缀表达式，如：a b c * + d e * f + g * +

已知三种遍历中任意两种遍历序列，能否唯一确定一棵二叉树

  • 其中必须要有中序序列才行
  • 如果没有中序序列，则对一组双亲和孩子结点来说无法确定是左孩子还是右孩子
  • 例：先序和中序遍历序列确定一棵二叉树
    • 根据先序遍历序列第一个结点确定根结点
    • 根据根结点在中序遍历序列中分割出左右两个子序列
    • 对左子树和右子树分别递归使用相同方法继续分解
    • 类似的，后序和中序遍历序列也可以确定一棵二叉树

例：二叉树先序序列中序序列转后序序列，后序序列中序序列转先序序列

int preorder[]={'A','B','D','E','C','F','G'},
inorder[]={'D','B','E','A','F','C','G'},
postorder[]={'D','E','B','F','G','C','A'};
void post(int root,int start,int end){
    if(start>end)return;
    int i=start;
    for(;inorder[i]!=preorder[root];i++);
    post(root+1,start,i-1);
    post(root+1+i-start,i+1,end);
    cout<<(char)inorder[i]<<' ';
}
void pre(int root,int start,int end){
    if(start>end)return;
    int i=end;
    for(;inorder[i]!=postorder[root];i--);
    cout<<(char)inorder[i]<<' ';
    pre(root-1-end+i,start,i-1);
    pre(root-1,i+1,end);
}

例：中序和前序序列建树(中序和后序同理)

BinTree CreateBintree(BinTree BST,int pres,int pree,int ins,int ine){
    if(pree-pres<0)return nullptr;
    int pos;
    BST=new struct TreeNode(tpreorder[pres]);
    for(pos=ins;tinorder[pos]!=tpreorder[pres];pos++);
    BST->left=CreateBintree(BST->left,pres+1,pres+pos-ins,ins,pos-1);
    BST->right=CreateBintree(BST->right,pres+pos-ins+1,pree,pos+1,ine);
    return BST;
}

二叉树遍历演示

/* 浙江大学mooc数据结构示例程序 */
#include<cstdio>
typedef int ELementType;
typedef struct BinNode* BinTree;
struct BinNode
{
    ELementType Data;
    BinTree Left,Right;
};
typedef struct Queue* List;
struct Queue
{
    int Maxsize;
    List rear,front;
};
struct Queue CreatQueue();
void AddQ(Queue,BinTree);
bool IsEmpty(Queue);
BinTree DeleteQ(Queue);
void InorderTraversal( BinTree BT )
{
    if( BT ) {
        InorderTraversal( BT->Left );
        /* 此处假设对BT结点的访问就是打印数据 */
        printf("%d ", BT->Data); /* 假设数据为整型 */
        InorderTraversal( BT->Right );
    }
}

void PreorderTraversal( BinTree BT )
{
    if( BT ) {
        printf("%d ", BT->Data );
        PreorderTraversal( BT->Left );
        PreorderTraversal( BT->Right );
    }
}

void PostorderTraversal( BinTree BT )
{
    if( BT ) {
        PostorderTraversal( BT->Left );
        PostorderTraversal( BT->Right );
        printf("%d ", BT->Data);
    }
}

void LevelorderTraversal ( BinTree BT )
{ 
    Queue Q; 
    BinTree T;

    if ( !BT ) return; /* 若是空树则直接返回 */
  
    Q = CreatQueue(); /* 创建空队列Q */
    AddQ( Q, BT );
    while ( !IsEmpty(Q) ) {
        T = DeleteQ( Q );
        printf("%d ", T->Data); /* 访问取出队列的结点 */
        if ( T->Left )   AddQ( Q, T->Left );
        if ( T->Right )  AddQ( Q, T->Right );
    }
}