轉換二叉樹 - > BST（保持原始樹形狀）

Question

我有一棵二叉樹某種形狀。我想將它轉換成BST搜索樹相同形狀。可能嗎？

我試過類似的方法 -

• 做階的二叉樹&放內容穿越到一個數組。然後將此映射到BST中並記住該條件（左值爲< = root < =右val）。這適用於某些情況，但對其他人無效。

P.S .:我看看這個 - Binary Trees question. Checking for similar shape。但很容易比較兩個BST在形狀上的相似性。

Answer 1

簡短的回答是：你不能。 BST要求節點遵循左邊< =當前<的規則。在你鏈接的例子中：http://upload.wikimedia.org/wikipedia/commons/f/f7/Binary_tree.svg，如果你嘗試使用相同的shap來構建BST，你會發現你不能。

但是，如果你想舒展BST的定義，以便它允許左< =當前< =權（注意，這裏目前< =權限被允許，並列爲對更嚴格的定義），您可以。對所有元素進行排序並將它們粘貼到一個數組中。現在進行按順序遍歷，用數組中的每個元素替換節點上的值。這裏有一些僞代碼：

// t is your non-BST tree, a is an array containing the sorted elements of t, i is the current index into a 
index i = 0 
create_bst(Tree t, Array a) 
{ 
    if(t is NIL) 
    return; 
    create_bst(t->left, a) 
    t->data = a[i] 
    i++ 
    create_bst(t->right, a) 
} 

但結果不是真正的BST。如果你想要一個真實的BST儘可能接近原始形狀，那麼你再次將這些元素放入一個有序數組中，但是這次將它們插入到BST中。插入它們的順序由原始樹的子樹的大小來定義。這裏有一些僞代碼：

// left is initially set to 0 
create_true_bst(Tree t, BST bt, array a, index left) 
{ 
    index i = left + left_subtree(t)->size 
    bt->insert(a[i]) 
    if(left_subtree(t)->size != 0) 
    { 
    create_true_bst(t->left, bt, a, left) 
    create_true_bst(t->right, bt, a, i + 1) 
    } 
} 

但是這並不能保證形狀是相同的。

Answer 2

如果您正確實施，則描述的方法可以保證正常工作。二叉樹上的遍歷順序是唯一的，並定義了元素的順序。如果通過價值元素進行排序，然後根據該排序他們堅持的話，那將永遠是真實的，

left subtree <= root <= right subtree 

爲每個節點，因爲這是你遍歷的順序，並考慮到你按順序對它們進行了排序。

Answer 3

我只是做兩個按順序遍歷。在第一次遍歷中，從樹中獲取值並將它們放入堆中。在第二個中，從堆中獲取值並將其放入樹中。這運行在O（n＆middot; log n）時間和O（n）空間。

Answer 4

提取樹的所有元素，然後對其進行排序，然後使用遞歸inorder過程來替換值。