LEON

《浙大 数据结构》二叉树的遍历

2021.11.03

三种常用遍历

  • 先序遍历
void PreOrderTraversal( BinTree BT )
{
     if( BT )  //如果BT不空
     {
        printf("%d", BT->Data);
        PreOrderTraversal( BT->Left );  //递归
        PreOrderTraversal( BT->Right );  //递归
     }
}
  • 中序遍历
void PreOrderTraversal( BinTree BT )
{
     if( BT )  //如果BT不空
     {
        PreOrderTraversal( BT->Left );  //递归
        printf("%d", BT->Data);
        PreOrderTraversal( BT->Right );  //递归
     }
}
  • 后序遍历
void PreOrderTraversal( BinTree BT )
{
     if( BT )  //如果BT不空
     {
        PreOrderTraversal( BT->Left );  //递归
        PreOrderTraversal( BT->Right );  //递归
        printf("%d", BT->Data);
     }
}

二叉树的非递归遍历

中序遍历的非递归遍历算法：

void InOrderTraversal( BinTree BT )
{  
    BinTree T=BT;
    Stack S = CreatStack( MaxSize ); /*创建并初始化堆栈S*/ 
    while( T || !IsEmpty(S) )
    {  //IsEmpty是判断堆栈空不空
        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. 若该元素所指的结点左右孩子结点非空，则将其左右孩子的指针顺序入队

实现：

void LevelOrderTraversal ( BinTree BT )
{
    Queue Q; BinTree T;
    if ( !BT ) return; /* 若是空树则直接返回 */ 
    Q = CreatQueue( MaxSize ); /*创建并初始化队列Q*/ 
    AddQ( Q, BT ); // 把根节点放到队列里去
    while ( !IsEmptyQ( Q ) ) 
    {
        T = DeleteQ( Q );  // pop出一个元素,产生的元素赋给 T指针
        printf("%d\n", T->Data); /*访问取出队列的结点*/ 
        if ( T->Left ) AddQ( Q, T->Left );
        if ( T->Right ) AddQ( Q, T->Right );
    } 
}

遍历二叉树的应用

输出二叉树中的叶子结点

void PreOrderPrintLeaves( BinTree BT ) 
{
    if( BT ) 
    {
        if ( !BT->Left && !BT->Right ) // 如果没有左右子树,就打印出来
            printf("%d", BT->Data ); 
        PreOrderPrintLeaves ( BT->Left ); 
        PreOrderPrintLeaves ( BT->Right );
    } 
}

求二叉树的高度

int PostOrderGetHeight( BinTree BT ) 
{
    int HL, HR, MaxH;
    if( BT ) 
    {
        HL = PostOrderGetHeight(BT->Left); /*求左子树的深度*/ 
        HR = PostOrderGetHeight(BT->Right); /*求右子树的深度*/ 
        MaxH = (HL > HR)? HL : HR; /*取左右子树较大的深度*/ 
        return ( MaxH + 1 ); /*返回树的深度*/
    }
    else return 0; /* 空树深度为0 */ 
}

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

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

CS