擴充二叉樹

詳解

擴充二叉樹是二叉樹中的一種，是指在二叉樹中出現空子樹的位置增加空樹葉，所形成的二叉樹。

在二叉樹中出現空的子樹（包括樹葉）上增加空的樹葉，使子樹成為滿二叉樹（國際定義）的二叉樹稱之為擴充二叉樹。

從擴充的二叉樹的根到每個外部結點的路徑長度之和稱為外部路徑長度（E），擴充的二叉樹里從根到每個內部結點的路徑長度之和稱為內部路徑長度（I），它們之間的關係滿足E=I+2N（N為內部結點數）。

代碼實現

擴充二叉樹

由於先序、中序和後序序列中的任一個都不能唯一確定一棵二叉樹，所以對二叉樹做如下處理，將二叉樹的空結點用·補齊，如圖所示。我們把這樣處理後的二叉樹稱為原二叉樹的擴展二叉樹，擴展二叉樹的先序和後序序列能唯一確定其二叉樹。

現給出擴展二叉樹的先序序列，要求輸出其中序和後序序列。

輸入

擴展二叉樹的先序序列。

輸出

輸出其中序和後序序列。

輸入樣例

ABD..EF..G..C..

輸出樣例

DBFEGACDFGEBCA

代碼