從2d二叉搜索樹中刪除節點

Question

我想知道是否有人可以提供一些關於從2d二叉搜索樹中刪除節點的有用信息。

我理解有四種情況下，其中第一個我已經完成：

1. 刪除沒有子（葉）節點，操作簡單，只需設置指針到該節點爲空。
2. 刪除左側節點上有一個子節點且右側節點爲空的節點。
3. 刪除右節點上有一個子節點且左節點爲空的節點。
4. 刪除有兩個孩子的節點，左側和右側。

我不知道如何確切地做2,3和4.我試圖做迭代，但是，似乎並沒有工作。我假設這必須遞歸地完成。有人可以澄清一下如何完全做到這一點。這是在java中，應該沒關係:)

Answer 1

在2D樹中，所有值都存儲在葉節點中。內部節點只是作爲尋找葉節點的途徑。具體而言，內部節點定義了包含基礎數據的半平面。我們只處理數據;我們不修改數據結構本身的結構元素。所以，只有上面的情況1成立。所有其他人都無關緊要。