Problem 1063 --二元樹鏈表存儲的二元樹

1063: 二元樹鏈表存儲的二元樹

Time Limit: 1 Sec  Memory Limit: 32 MB
Submit: 7  Solved: 6
[Submit][Status][Web Board]

Description

樹形結構是一類重要的非線性資料結構,其中以樹和二元樹最為常用。對於每一個結點至多只有兩棵子樹的樹,稱其為二元樹。二元樹的鏈式存儲結構是一類重要的資料結構,其形式定義如下:
而二元樹的前序、中序遍歷是非常重要的能夠訪問二元樹所有結點的算法,下面分別列出一種先序遍歷和兩種中序遍歷的算法。
第一種中序遍歷的方法(算法6.3):
第二種中序遍歷的方法(算法6.2):
通過讀入一個字符串,建立二元樹的算法如下:
在本題中,將會給出一個按照先序遍歷得出的字符串,空格代表空的子節點,大寫字母代表節點內容。請通過這個字符串建立二元樹,並按照題目描述中的一種先序遍歷和兩種中序遍歷的算法分別輸出每一個非空節點。

Input

輸入只有一行,包含一個字符串S,用來建立二元樹。保證S為合法的二元樹先序遍歷字符串,節點內容只有大寫字母,且S的長度不超過100。

Output

共有三行,每一行包含一串字符,表示分別按先序、中序、中序得出的節點內容,每個字母後輸出一個空格。請注意行尾輸出換行。

Sample Input

ABC  DE G  F   

Sample Output

A B C D E G F 
C B E G D F A 
C B E G D F A 

HINT


遍歷是二元樹各種操作的基礎,可以在遍歷的過程中對節點進行各種操作。通過二元樹的遍歷,可以建立二元樹。而先序、中序和後序遍歷分別具有各自的特點,是探索二元樹性質的絕佳“武器”。

Source

[Submit][Status]