構造一個二叉樹，使得後序遍歷應該給出排序結果

Question

我知道二叉搜索樹上的順序遍歷（訪問左，訪問根，訪問權）給了我一個排序結果。但是我需要在二叉樹上進行後序遍歷（訪問左邊，訪問權，訪問根），結果應該給我排序的值。

爲了實現這一點，我該如何構建我的二叉樹？

Answer 1

由於最後訪問過根，它必須包含最大的項目。由於在右子樹之前訪問左子樹，左子樹中的所有項必須小於右子樹中的任何項。

所以要構建一個這樣的樹，你可以按如下步驟進行：如果你插入一個大於根的項，那麼這個項就成爲新的根。如果插入的項小於根，但大於左側子樹的根，請將其插入右側子樹。否則將其插入左側子樹。

Answer 2

您需要確保在樹的每個節點執行以下操作：在節點

• 值應大於 比 左子樹和右子樹的所有值。
• 左子樹中的值應該是 ，小於右子樹 中的值。

Answer 3

該子程序是在樹 插入其中樹結構是

struct tree 

{ 

int data; 
tree * left; 
tree *right; 

tree(int n) // constructor 

{ 
     data = n; 
     left = right = NULL; 
    } 
}; 

的算法爲：
1.如果樹爲空插入新的節點。
2.如果新節點的數據大於根節點的數據，則使新節點的樹根爲
。
3. else在樹的左子樹中插入新節點。

tree * insert(tree *root,int n) 

{ 

if(root == NULL) 
{ 

    root = new tree(n); 

    return root; 
} 
else 
{ 

    if(n > root -> data) 
    { 
     tree * t = new tree(n); 

     t -> left = root; 

     return t; 
    } 

    else 


    { 

     root -> left = insert(root -> left,n); 

     return root; 
    } 
    } 
} 

Answer 4

currently accepted answer給出了一個很好的在線算法。一個稍微簡單的解決方案---不在線並因此可能作弊---是在父指針中存儲排序後的鏈表。

換句話說：對數據進行排序;將最大的項目放在根中，使其中一個子樹爲空，並遞歸構造剩餘的n-1個項目的後序排序樹到另一個子樹中。

樹的高度爲n，單葉是列表的頭部，根是最後面的元素。如果你從樹葉到樹根遍歷樹，元素將形成一個遞增的序列，並且這條路徑將完全對應於後序遍歷。

Answer 5

刪除

• 若葉，然後定期刪除
• 如果只有一個兒子連兒子的父親
• 否則，刪除根，其右兒子代替它，然後連接左子樹到右子樹中最左邊的頂點。

例如：

7               6 
/\              /\ 
    3 6    =========DELETING 7 ============>   4 5 
/\/\             / 
1 2 4 5             3 
                  /\ 
                  1 2