二叉树的遍历PTA(详解)

心已赠人 2022-02-04 04:17 266阅读 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;
    }
    /* 你的代码将被嵌在这里 */

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

![在这里插入图片描述][20190506213330993.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)
    	{
        
    		InorderTraversal(BT->Left);
    		printf(" %c",BT->Data);
    		InorderTraversal(BT->Right);
    	}
    }
    void PreorderTraversal( BinTree BT )//先序遍历 
    {
         
    	if(BT)
    	{
        
    		printf(" %c",BT->Data);
    		PreorderTraversal(BT->Left);	
    		PreorderTraversal(BT->Right);
    	}
    }
    void PostorderTraversal( BinTree BT )//后续遍历 
    {
        
    	if(BT)
    	{
        
    		PostorderTraversal(BT->Left);	
    		PostorderTraversal(BT->Right);
    		printf(" %c",BT->Data);
    	}
    }
    void LevelorderTraversal( BinTree BT ) //层序遍历
    {
        
        BinTree p;   //定义结构体变量 
        BinTree q[20];//定义结构体数组，注意数组空间大小要适合
        int m=0,n=0; 
        if(!BT) return 0;
        else  //如果数不为空 
        {
        
            q[n++]=BT;
            while(m!=n)
            {
        
            	p=q[m++];
        		printf(" %c",p->Data);
        		if(p->Left!=NULL) q[n++]=p->Left;
        		if(p->Right!=NULL) q[n++]=p->Right;
        		//先将左右子树存放到数组中 ，再输出
        	}
      	}
    }

**层序遍历思路分析：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MjU2MjI3_size_16_color_FFFFFF_t_70]  
分析：黑三角所指的表示p,p=q\[m++\],可以看出p是按顺序将二叉树进行一个一个访问，当访问到根节点时，判断根结点是否存在左右子树，该题存在，所以将左右子树按先后顺序分别存到数组q中，然后p按顺序往后访问，每访问一个元素都要判断它是否存在左右子树，如果存在就将其左右子树按先后顺序存到q中，这样，随着p的顺序一次访问和左右结点的顺序存入，使得q数组中存放元素的特点为层序排列，当p访问到左后一个结点时，即m=n时，二叉树所有结点访问完毕，q数组中存放的是该二叉树的层序排列。  
![在这里插入图片描述][20190509105557392.gif]

[20190506213330993.jpg]: /images/20220204/074fabf9bc55434ba6734b4cb0b5c6ca.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MjU2MjI3_size_16_color_FFFFFF_t_70]: /images/20220204/1abbf7a2c85a4568afde55b29494490b.png
[20190509105557392.gif]: /images/20220204/81016ad1bdce4631b3a7f92b641e42fd.png