給定預構造遍歷的構造樹

給出了一種特殊類型的樹，其中所有樹葉標記爲L，其他標記爲N。每個節點可以有0個或最多2個節點。給出樹的前序遍歷。給定預構造遍歷的構造樹

給出一個算法從這個遍歷中構建樹。

2011-02-05 TopCoder

你可以給一個輸入和輸出的樣本？預計哪種格式？ – 2011-02-05 18:03:08

在發佈之前，通常認爲最好是至少將您的家庭作業複述一遍。告訴我們一些關於你試過的東西以及你卡在哪裏的幫助。這是一個問題和答案的地方，而不僅僅是「爲我寫代碼」。 – 2011-02-05 18:03:36

這是序遍歷算法：

Preorder(T) 
    if (T is not null) 
    print T.label 
    Preorder(T.left) 
    Preorder(T.right)

讓我們試着去尋找的NNLLNL輸入的算法。

顯然首先打印根的標籤。所以你知道根有標籤N。現在算法在左子樹上遞歸。根據輸入，這也是N。在左邊的子樹上遞增，即L。現在你必須回溯，因爲你已經到了一片葉子。輸入中的下一個位置也是L，所以當前節點有一個標有L的右側子節點。回溯一次。再次回溯，因爲你已經添加了當前節點的所有孩子（最多2個孩子）。現在你又在根。你必須正確，因爲你已經離開了。根據輸入，這是N。所以根的正確孩子是N。那個左邊的孩子將是L。這是你的樹：

 N 
    / \ 
    N  N 
/\ /
    L L L

請注意，該解決方案不一定是唯一的，但這會給你一個可能的解決方案。

僞代碼：

k = 0 
input = ... get preorder traversal vector from user ... 
Reconstruct(T) 
    if input[k] == N 
    T = new node with label N 
    k = k + 1 
    Reconstruct(T.left) 
    Reconstruct(T.right) 
    else 
    T = new node with label L 
    T.left = T.right = null 
    k = k + 1

調用具有空節點。

後續問題：給定包含不同節點標籤的二叉樹的前序遍歷和次序遍歷，如何唯一地重構樹？

來源

2011-02-05 19:56:12 IVlad

給定預構造遍歷的構造樹

回答

相關問題