6-2 二叉树的遍历（25 分）

╰半夏微凉° 2022-04-22 03:30 162阅读 0赞

本题要求给定二叉树的4种遍历。

## 函数接口定义： ##

void InorderTraversal( BinTree BT );
    void PreorderTraversal( BinTree BT );
    void PostorderTraversal( BinTree BT );
    void LevelorderTraversal( BinTree BT );

其中BinTree结构定义如下：

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

要求4个函数分别按照访问顺序打印出结点的内容，格式为一个空格跟着一个字符。

裁判测试程序样例：
    
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef char ElementType;
    typedef struct TNode *Position;
    typedef Position BinTree;
    struct TNode{
        ElementType Data;
        BinTree Left;
        BinTree Right;
    };
    
    BinTree CreatBinTree(); /* 实现细节忽略 */
    void InorderTraversal( BinTree BT );
    void PreorderTraversal( BinTree BT );
    void PostorderTraversal( BinTree BT );
    void LevelorderTraversal( BinTree BT );
    
    int main()
    {
        BinTree BT = CreatBinTree();
        printf("Inorder:");    InorderTraversal(BT);    printf("\n");
        printf("Preorder:");   PreorderTraversal(BT);   printf("\n");
        printf("Postorder:");  PostorderTraversal(BT);  printf("\n");
        printf("Levelorder:"); LevelorderTraversal(BT); printf("\n");
        return 0;
    }
    /* 你的代码将被嵌在这里 */

![在这里插入图片描述][20181101223601727.jpg]

## 输出样例（对于图中给出的树）： ##

Inorder: D B E F A G H C I
    Preorder: A B D F E C G H I
    Postorder: D E F B H G I C A
    Levelorder: A B C D F G I E H

void InorderTraversal( BinTree BT ){
        
        if(BT){
        
            if(BT->Left)InorderTraversal(BT->Left);
            printf(" %c",BT->Data);
            if(BT->Right)InorderTraversal(BT->Right);
        }
    }
    void PreorderTraversal( BinTree BT ){
        
        if(BT){
        
            printf(" %c",BT->Data);
            if(BT->Left)PreorderTraversal(BT->Left);
            if(BT->Right)PreorderTraversal(BT->Right);
        }
    }
    void PostorderTraversal( BinTree BT ){
        
        if(BT){
        
            if(BT->Left)PostorderTraversal(BT->Left);
            if(BT->Right)PostorderTraversal(BT->Right);
            printf(" %c",BT->Data);
        }
    }
    void LevelorderTraversal( BinTree BT ){
        
        BinTree que[101],t;
        int head=0,rear=0;
        if(BT){
        
            que[rear++]=BT;
            while(head!=rear){
        
                t=que[head++];
                printf(" %c",t->Data);
                if(t->Left)que[rear++]=t->Left;
                if(t->Right)que[rear++]=t->Right;
            }
        }
    }

[20181101223601727.jpg]: /images/20220422/0bfbebc6dcd345ae925787b87c2db200.png