Welcome   HUNAN NORMAL UNIVERSITY ACM/ICPC Judge Online
Home
FAQs
Problem Set
Practices
Online Contests
Major Exercises
OI Special
Judgement
Submit
Online Status
User Ranklist
Users
Register new
Login
Web Links
Hunan Normal University
College of Information Science and Engineering
二叉树遍历
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 93, Accepted users: 86
Problem 10166 : No special judgement
Problem description
  遍历一棵二叉树就是按某种次序系统地“访问”二叉树上的所有结点,并使每一个结点恰好被访问一次。所谓“访问”一个结点,是指对该结点的数据域进行某种处理,处理的内容依具体问题而定,通常比较简单。我们知道,遍历一个线性结构很容易,只须从开始结点出发顺序扫描每个结点即可。但是二叉树是一个非线性结构,每个结点可以有两个后继结点,因此需要寻找一种规律来系统地访问树中各结点。遍历运算的关键在于访问结点的“次序”,这种次序应保证二叉树上的每个结点均被访问一次且仅一次。
   由定义可知,一棵二叉树由三部分组成:根、左子树和右子树。因此对于二叉树的遍历也可相应地分解成三项“子任务”:
   ①访问根结点;
   ②遍历左子树(即依次访问左子树上的全部结点);
   ③遍历右子树(即依次访问右子树上的全部结点)。
   因为左、右子树都是二叉树(可以是空二叉树),对它们的遍历可以按上述方法继续分解,直到每棵子树均为空二叉树为止。由此可见,上述三项子任务的次序决定了遍历的次序。若以D、L、R分别表示这三项子任务,则共有6种可能的次序:DLR、LDR、LRD、DRL、RDL和RLD。通常限定“先左后右”,即子任务②在子任务③之前完成,这样就只剩下前三种次序,按这三种进行的遍历分别称为先根遍历(或前序遍历)、中根(或中序)遍历、后根(或后序)遍历。三种遍历方法的定义如下。
   先根遍历 若需遍历的二叉树为空,执行空操作;否则,依次执行下列操作:
   ①访问根结点;
   ②先根遍历左子树;
   ③先根遍历右子树。
   中根遍历 若需遍历的二叉树为空,执行空操作;否则,依次执行下列操作:
   ①中根遍历左子树;
   ②访问根结点;
   ③中根遍历右子树。
   后根遍历 若需遍历的二叉树为空,执行空操作;否则,依次执行下列操作:
   ①后根遍历左子树;
   ②后根遍历右子树;
   ③访问根结点。
   显然,上述三种遍历方法的区别在于执行子任务“访问根结点”的“时机”不同;若最先(最后、在中间)执行此子任务,则为先根(后根、中根)遍历。
   按某种遍历方法遍历一棵二叉树,将得到该二叉树上所有结点的访问序列。

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

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

Sample Input
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
Sample Output
Case 1:
*+xy-/a2
x+y*-a/2
xy+a2/-*
Case 2:
+23
2+3
23+
Judge Tips
  
  测试序列1对应的二叉树如图:


Submit   Clarifications   Judge Status  Problems  Ranklist 

HUNAN NORMAL UNIVERSITY ACM/ICPC Judge Online, Version 2010.5.5.final.
Web visits:2090 today,16258817 total, since 2010-05-07