二叉树的遍历PTA(详解)_湖南信息学院 彭琛

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

函数接口定义：

void InorderTraversal( BinTree BT );
void PreorderTraversal( BinTree BT );
void PostorderTraversal( BinTree BT );
void LevelorderTraversal( BinTree BT );
1
2
3
4

其中BinTree结构定义如下：

typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};
1
2
3
4
5
6
7

要求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;
}
/* 你的代码将被嵌在这里 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

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

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
1
2
3
4

代码：

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;
    		//先将左右子树存放到数组中 ，再输出
    	}
  	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

层序遍历思路分析：

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