内存:128  时间:1

题目描述

遍历一棵二叉树就是按某种次序系统地“访问”二叉树上的所有结点,并使每一个结点恰好被访问一次。所谓“访问”一个结点,是指对该结点的数据域进行某种处理,处理的内容依具体问题而定,通常比较简单。我们知道,遍历一个线性结构很容易,只须从开始结点出发顺序扫描每个结点即可。但是二叉树是一个非线性结构,每个结点可以有两个后继结点,因此需要寻找一种规律来系统地访问树中各结点。遍历运算的关键在于访问结点的“次序”,这种次序应保证二叉树上的每个结点均被访问一次且仅一次。
   由定义可知,一棵二叉树由三部分组成:根、左子树和右子树。因此对于二叉树的遍历也可相应地分解成三项“子任务”:
   ①访问根结点;
   ②遍历左子树(即依次访问左子树上的全部结点);
   ③遍历右子树(即依次访问右子树上的全部结点)。
   因为左、右子树都是二叉树(可以是空二叉树),对它们的遍历可以按上述方法继续分解,直到每棵子树均为空二叉树为止。由此可见,上述三项子任务的次序决定了遍历的次序。若以D、L、R分别表示这三项子任务,则共有6种可能的次序:DLR、LDR、LRD、DRL、RDL和RLD。通常限定“先左后右”,即子任务②在子任务③之前完成,这样就只剩下前三种次序,按这三种进行的遍历分别称为先根遍历(或前序遍历)、中根(或中序)遍历、后根(或后序)遍历。三种遍历方法的定义如下。
   先根遍历 若需遍历的二叉树为空,执行空操作;否则,依次执行下列操作:
   ①访问根结点;
   ②先根遍历左子树;
   ③先根遍历右子树。
   中根遍历 若需遍历的二叉树为空,执行空操作;否则,依次执行下列操作:
   ①中根遍历左子树;
   ②访问根结点;
   ③中根遍历右子树。
   后根遍历 若需遍历的二叉树为空,执行空操作;否则,依次执行下列操作:
   ①后根遍历左子树;
   ②后根遍历右子树;
   ③访问根结点。
   显然,上述三种遍历方法的区别在于执行子任务“访问根结点”的“时机”不同;若最先(最后、在中间)执行此子任务,则为先根(后根、中根)遍历。
   按某种遍历方法遍历一棵二叉树,将得到该二叉树上所有结点的访问序列。

输入

输入的第一行包含单独的一个数字T,表示测试序列的数目;
  以下T个部分,每个部分一个测试序列;
  每个测试序列的第一行包含一个整数N(0 < N ≤ 1000),表示二叉树的节点数;
  接下来N行,每行按照这样如下的格式依次描述每个节点:
  字符数据 左孩子序号 右孩子序号
  其中节点的字符数据是一个单字符,如果左/右孩子不存在,用0表示其序号。

输出

  对应每个测试序列,输出以下四行:
  Case #:   ‘#’是从一开始的测试序列号;
  先序遍历的结果
  中序遍历的结果
  后序遍历的结果

样例输入

2
8
* 2 3
+ 4 5
– 0 6
x 0 0
y 0 0
/ 7 8
a 0 0
2 0 0
3
+ 2 3
2 0 0
3 0 0

样例输出

Case 1:
*+xy-/a2
x+y*-a/2
xy+a2/-*
Case 2:
+23
2+3
23+

提示

代码如下

#include <stdio.h>
#include <stdlib.h>
typedef struct treenode
{
   char date;
   int l,r;
   struct treenode *lch,*rch;
}node;
node *set(int n)
{
  char x;
  int a,b,i,j;
  node *p;
  node *q[1000];
   p=(node *)malloc(sizeof(node));
   q[1]=p;
   getchar();
   scanf("%c%d%d",&x,&a,&b);
   p->date=x;
   p->l=a;
   p->r=b;
   p->lch=NULL;
   p->rch=NULL;
   q[1]=p;
  for(i=2;i<=n;i++)
  {
    p=(node *)malloc(sizeof(node));
	q[i]=p;
    getchar();
    scanf("%c%d%d",&x,&a,&b);
    p->date=x;
    p->l=a;
    p->r=b;
	p->lch=NULL;
	p->rch=NULL;
	for(j=1;j<=i;j++)
	{
		if(q[j]->l!=0)
		{
			q[j]->lch=p;
			q[j]->l=0;
			break;
		}
		if(q[j]->r!=0)
		{
			q[j]->rch=p;
			q[j]->r=0;
			break;
		}
	}
  }	
  return q[1];
}
void preoder(node *p)
{
if(p!=NULL)
{ printf("%c",p->date);
    preoder(p->lch);
preoder(p->rch);
}
}
void inoder(node *p)
{
    if(p!=NULL)
	{ 
    inoder(p->lch);
        printf("%c",p->date);
    inoder(p->rch);
}
}
void postoder(node *p)
{
    if(p!=NULL)
{ 
    postoder(p->lch);
postoder(p->rch);
        printf("%c",p->date);
}
}
int main()
{
int m,n,i;
node *head;
scanf("%d",&m);
    for(i=1;i<=m;i++)
{
scanf("%d",&n);
head=set(n);
printf("Case %d:",i);
        printf("\n");
preoder(head);
printf("\n");
inoder(head);
printf("\n");
postoder(head);
printf("\n");
}
return 0;
}

代码来源于互联网,仅供参考!