algorithm - traverse - print binary tree using stack



從預訂單和後序列表中重建樹 (5)

考慮這樣一種情況:你有兩個節點列表,其中你知道的一個是一個樹的前序遍歷的表示,另一個是同一樹的後序遍歷的表示。

我相信可以從這兩個列表中精確地重建樹,我想我有一個算法來做,但還沒有證明。 由於這將成為碩士項目的一部分,我需要絕對確定它是可能的和正確的(數學證明)。 然而,它不會成為該項目的重點,所以我想知道是否有一個來源(即紙張或書籍)我可以引用證明。 (也許在TAOCP?有人可能知道這部分嗎?)

簡而言之,我需要在可引用資源中使用經過驗證的算法,該算法可以從其前後順序遍歷中重構樹。

注意:有問題的樹可能不是二進制的,或者是平衡的,或任何使它太容易的東西。

注意2:僅使用預訂單或後序列表會更好,但我認為不可能。

注3:節點可以有任意數量的子節點。

注4:我只關心兄弟姐妹的順序。 當只有一個孩子時,左或右並不重要。


Answer #1

預購和後序並不唯一地定義樹。

通常,單個樹遍歷不會唯一地定義樹的結構。 例如,正如我們所看到的,對於以下兩個樹,一個inorder遍歷產生[1,2,3,4,5,6]。

    4                     3
   / \                   / \
  2   5                 2   5
 / \   \               /   / \
1   3   6             1   4   6

對於預訂和後序遍歷存在相同的模糊性。 上面第一棵樹的前序遍歷是[4,2,1,3,5,6]。 這是一個具有相同前序遍歷的不同樹。

    4
   / \
  2   1
     / \
    3   6
     \
      5

類似地,我們可以很容易地構造另一個樹,其後序遍歷[1,3,2,6,5,4]匹配上面第一棵樹的遍歷。


Answer #2

假設節點具有唯一名稱,預訂和後序遍歷足以重建樹。 創建算法的關鍵是要理解這一點

X是Y的祖先,如果X在前序中在Y之前,並且在後序中在Y之後。

鑑於此,我們總能找到任何節點的所有後代。 X的後代總是緊跟在前序中的X之後,並且在後序中的X之前。 因此,一旦我們知道我們對生成以X為根的子樹感興趣,我們就可以提取以X為根的子樹的前序和後序遍歷。這一直導致遞歸算法,一旦我們意識到X之後的節點必須是它最左邊的孩子,如果它是一個後代。

還有一個基於堆棧的實現,它迭代預訂節點,並在任何節點上保留任何候選節點作為下一個預訂節點的直接父節點。 對於每個預訂節點,重複彈出堆棧外的所有節點,這些節點不是下一個預訂節點的父節點。 使該節點成為堆棧頂級節點的子節點,並將子節點推入堆棧。


Answer #3

將任意樹T視為四元組(A,B, CD ),其中A是根節點,B是第一個子節點的根節點, C是B的任何非空子節點的向量, D是B的任何非空兄弟的向量.CD的元素本身就是樹。

A,B, CD中的任何一個都可以是空的。 如果B為空,那麼必須是CD ; 如果A,那麼一切。

由於節點是唯一的,因此包含在CD內任何位置的節點集是不相交的,並且都不包含A或B.

函數pre()post()生成以下形式的有序序列:

pre(T) = [A,B, pre( Cpre( D ]

post(T) = [ post( C ,B, post( D ,A]

其中應用於向量的函數被定義為通過依次將函數應用於每個元素而得到的序列的串聯。

現在考慮一下案例:

  • 如果A為空,則兩個函數的輸出都是空序列[]
  • 如果B為空,則兩個函數的輸出只是[A]
  • 如果CD為空,則前(T) = [A,B]和後(T) = [B,A]
  • 如果只有C為空,則前(T) = [A,B, D' ]和後(T) = [B, D'' ,A](其中素數表示D中包含的節點的一些排列)
  • 如果D為空,則前(T) = [A,B, C' ]和後(T) = [ C'' ,B,A]
  • 如果沒有空,則pre(T) = [A,B, C'D' ]和post(T) = [ C'' ,B, D'' ,A]

在所有情況下,我們可以通過使用A和B(如果存在)作為分隔符,明確地將兩個輸出序列的成員劃分為適當的子序列。

那麼問題是,我們還能分割矢量序列嗎? 如果可以,那麼每個都可以遞歸處理,我們就完成了。

由於pre()的結果將始終是以A節點開始的序列鏈,並且post()的結果將始終是以A節點結尾的序列鏈,我們確實可以將它們分開, 前提是A節點從來都不是空的。

對於具有固定子節點的二元(或實際上任何)樹,可以獨立地為空,這就是該過程落下的地方。 然而,在我們的例子中,我們已經定義了CD只包含非空節點,因此保證重建工作。

嗯,我想是的,無論如何。 顯然這只是一個論點,而不是一個正式的證據!


Answer #4

從前序和後序遍歷構造一般二元樹是不可能的(見本文)。 但是如果知道二叉樹是完整的,我們就可以構造沒有歧義的樹。 讓我們藉助以下示例來理解這一點。

讓我們將兩個給定的數組視為pre [] = {1,2,4,8,9,5,3,6,7}和post [] = {8,9,4,5,2,6,7 ,3,1}; 在pre []中,最左邊的元素是樹的根。 由於樹已滿且數組大小超過1. pre []中1旁邊的值必須是root的子級。 所以我們知道1是根,2是小孩。 如何在左子樹中找到所有節點? 我們知道2是左子樹中所有節點的根。 post []中2之前的所有節點必須位於左子樹中。 現在我們知道1是根,元素{8,9,4,5,2}在左子樹中,元素{6,7,3}在右子樹中。

              1
            /   \
           /      \
 {8, 9, 4, 5, 2}     {6, 7, 3}

我們遞歸地遵循上述方法並得到以下樹。

      1
    /   \
  2       3
/  \     /  \

4 5 6 7 /
8 9


Answer #5

正如其他人已經指出的那樣,只能通過使用前後順序遍歷來重建二叉樹。 單個子節點具有模糊遍歷,無法識別它是左還是右子,例如考慮遵循預訂和後序遍歷:預訂:a,b後序b,a

它可以生成以下兩種樹

aa \ / bb根本不可能知道b是左邊還是右邊的孩子,而沒有任何額外的信息,如inorder遍歷。





traversal