PTA练习题：二叉树的遍历

悠悠 2023-02-11 04:44 3阅读 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;  
\}  
/\* 你的代码将被嵌在这里 \*/  
输出样例（对于图中给出的树）：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTczNTI0Mg_size_16_color_FFFFFF_t_70]

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 != NULL)
    	{
    		InorderTraversal(BT->Left);
    		printf(" %c",BT->Data);
    		InorderTraversal(BT->Right);
    	}
    	
    }
    void PreorderTraversal( BinTree BT )
    {
    	if(BT != NULL)
    	{
    		printf(" %c",BT->Data);
    		PreorderTraversal(BT->Left);
    		PreorderTraversal(BT->Right);
    	}
    }
    void PostorderTraversal( BinTree BT )
    {
    	if(BT != NULL)
    	{
    		PostorderTraversal(BT->Left);
    		PostorderTraversal(BT->Right);
    		printf(" %c",BT->Data);
    	}
    }
    void LevelorderTraversal( BinTree BT )
    {
    	BinTree q[100];
    	int front = 0;
    	int rear = 0;
    	if(BT != NULL)
    	{
    		q[rear++] = BT;
    	}
    	while(front != rear)
    	{
    		if(q[front]->Left != NULL)
    		{
    			q[rear++] = q[front]->Left;
    		}
    		if(q[front]->Right != NULL)
    		{
    			q[rear++] = q[front]->Right;
    		}
    		printf(" %c",q[front++]->Data);
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTczNTI0Mg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200521201245436.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTczNTI0Mg==,size_16,color_FFFFFF,t_70