這個二叉搜索樹算法如何遞歸

-1

我有以下的二叉搜索樹，根節點20.我試圖回答的問題是，如果我們應用功能t = deleteRoot(t)，新的價值是什麼根節點以及其直接的左側和右側子節點（例如，當前的根節點爲20，即時左側子節點11和直接右側子節點32）。爲了解決這個問題，我在過去的2個小時裏至少寫了10頁，但遞歸正在殺死我。有人可以幫助我想象這一點 - 即某種思維方式，可以讓我處理遞歸。我並不擅長可視化遞歸如何工作，但我可以稍微實現它。非常感謝。順便說一句，答案是根節點：21左子11和右子32 這個二叉搜索樹算法如何遞歸

我嘗試：

的問題告訴我們先從t=deleteRoot(t)。

parent = node containing 25 
succ = node containing 21 
succval = 21

然後我們得到

t = TreeDelete(t, succval)

然後我得到一個有點失落至於TreeDelete功能是如何工作的

t->left = TreeDelete(t->left, key) ...etc

deleteRoot（樹T）功能

// delete root of tree 
Tree deleteRoot(Tree t) 
{ 
    Link newRoot; 
    // if no subtrees, tree empty after delete 
    if (t->left == NULL && t->right == NULL) { 
     free(t); 
     return NULL; 
    } 
    // if only right subtree, make it the new root 
    else if (t->left == NULL && t->right != NULL) { 
     newRoot = t->right; 
     free(t); 
     return newRoot; 
    } 
    // if only left subtree, make it the new root 
    else if (t->left != NULL && t->right == NULL) { 
     newRoot = t->left; 
     free(t); 
     return newRoot; 
    } 
    // else (t->left != NULL && t->right != NULL) 
    // so has two subtrees 
    // - find inorder successor (grab value) 
    // - delete inorder successor node 
    // - move its value to root 
    Link parent = t; 
    Link succ = t->right; // not null! 
    while (succ->left != NULL) { 
     parent = succ; 
     succ = succ->left; 
    } 
    int succVal = succ->value; 
    t = TreeDelete(t,succVal); 
    t->value = succVal; 
    return t; 
}

樹TreeDelete（樹T，密鑰K）功能：

Tree TreeDelete(Tree t, Key k) 
{ 
    Tree deleteRoot(Tree); 

    if (t == NULL) 
     return NULL; 
    int diff = cmp(k,key(t->value)); 
    if (diff == 0) 
     t = deleteRoot(t); 
    else if (diff < 0) 
     t->left = TreeDelete(t->left, k); 
    else if (diff > 0) 
     t->right = TreeDelete(t->right, k); 
    return t; 
}

來源

2017-11-11 Programmer

我們先從'T = deleteRoot（噸）'其中't'是初始根節點（20）按照圖。其餘的從那裏開始。 – Programmer

當子樹被刪除時，父節點會發生什麼？不會被設置爲空嗎？ – Arash

@ 4386427：因爲2 * 21 = 42？ ;-) – alk

順便說一句，答案是根節點：21左子11和右子32

那麼，這是一個解決方案，但不是唯一的解決方案。

18與左孩子11和右孩子32也將是一個解決方案。

當刪除根，新的根可以被選擇作爲

在左子樹的最高數

或

的在右子樹中的最低數量

因此，複製所選的no de到當前根目錄。然後刪除選定的節點。如果所選節點有子節點，則可以遞歸地重複該過程。

來源

2017-11-11 09:54:22 4386427

在缺失的情況下，如果要刪除的節點有兩個孩子：

找到繼任者或前任
替換爲接班人的內容節點/前身
呼叫刪除後繼/前身（這樣的尺寸將遞減）
返回節點

後繼是右側子樹上的最高元素，而前一個元素是左側子樹上的最低元素。在你的情況下，後繼將是21和前身是18.

來源

2017-11-11 11:31:21 bitnahian

這個二叉搜索樹算法如何遞歸

回答

相關問題