在 JavaScript 樹中刪除節點

樹是一種非線性資料結構，它包含節點和邊；其中邊充當兩個節點之間的連結，節點在其內部儲存值。

遍歷是一種過程，它將檢索樹中每個節點的資料並按指定的順序列印它們。

下面列出了三種類型的樹遍歷：

  • 中序遍歷 - 中序技術將遵循路徑(左 → 根 → 右)。

  • 前序遍歷 - 前序技術將遵循路徑(根 → 左 → 右)。

  • 後序遍歷 - 後序技術將遵循路徑(左 → 右 → 根)。

從樹中刪除節點

從樹中刪除節點這個術語基本上是一個過程，在這個過程中，一個節點被刪除並形成一個新的形狀。但在某些其他情況下，它會消除它們之間的連結，並替換為樹中的其他節點。

通常，記憶體（儲存）中不會有任何樹狀結構。它們是記憶體中隨機放置的元素（節點），我們試圖藉助指標（邊）將它們連線起來。

如果我們需要刪除一個元素，需要分離附加到它的指標並將其分配給相應的元素。

考慮下面的示例：

在上述情況下，我們嘗試刪除一個節點(40)，該節點附加了一個子節點。如果要刪除的節點只有一個子節點，它將複製該子節點到該節點並刪除該子節點。

可以從樹中刪除節點。其中有三種可能的刪除節點的情況。以下列出了這些情況。

場景 1 - 如果要刪除的節點是葉子節點，則在這種情況下可以將其簡單地從樹中刪除。

演算法

如果節點是葉子節點

  • 從樹中刪除節點。

場景 2 - 如果要刪除的節點只有一個子節點，它將複製其子節點到該節點並刪除該子節點。

演算法

如果節點有一個子節點

  • 找到它的子節點，假設為 c_node。
  • 將其設定為 node → data = c_node。
  • 再次刪除子節點。

場景 3 - 如果要刪除的節點有兩個子節點。

  • 首先，找到節點的中序後繼，並將它的值複製到要刪除的節點，然後刪除中序後繼節點。

演算法

如果節點同時具有左子節點和右子節點

  • 在右子樹中找到最小的節點，假設為 min_node。
  • 將其設定為 node → data = min_node。
  • 再次刪除 min_node。

示例

在下面的示例中，我們實現了一個二叉搜尋樹，並在其中插入了足夠數量的節點。我們對給定的樹執行了刪除操作。我們還在從樹中刪除選定節點後執行了中序遍歷。

<!DOCTYPE html>
<html>
   <head>
      <script>
         class Node {
            constructor(item) {
               this.key = item;
               this.left = this.right = null;
            }
         }

         let root = null;
         function deleteKey(key) {
            root = deleteRecursive(root, key);
         }
         function deleteRecursive(root, key) {
            if (root == null)
               return root;
            if (key < root.key)
               root.left = deleteRecursive(root.left, key);
            else if (key > root.key)
               root.right = deleteRecursive(root.right, key);
            else {
               if (root.left == null)
                  return root.right;
               else if (root.right == null)
                  return root.left;
               root.key = minimumValue(root.right);
               root.right = deleteRecursive(root.right, root.key);
            }
            return root;
         }
         function minimumValue(root) {
            let minValue = root.key;
            while (root.left != null) {
               minValue = root.left.key;
               root = root.left;
            }
            return minValue;
         }
         function insert(key) {
            root = insertRec(root, key);
         }
         function insertRec(root, key) {
            if (root == null) {
               root = new Node(key);
               return root;
            }
            if (key < root.key)
               root.left = insertRec(root.left, key);
            else if (key > root.key)
               root.right = insertRec(root.right, key);
            return root;
         }
         function inorder() {
            InorderRecursion(root);
         }
         function InorderRecursion(root) {
            if (root != null) {
               InorderRecursion(root.left);
               document.write(root.key + " ");
               InorderRecursion(root.right);
            }
         }
         insert(90);
         insert(40);
         insert(10);
         insert(50);
         insert(100);
         insert(70);
         insert(60);
         insert(80);
         insert(120);
         document.write("After inserting the above nodes In-order will be: <br>");
         inorder();
         document.write("<br>Delete the node 10<br><br>");
         deleteKey(10);
         document.write("In-order after node 10 is deleted from the tree <br>");
         inorder();
         document.write("<br>Delete the node 40<br><br>");
         deleteKey(40);
         document.write("In-order after node 40 is deleted from the tree <br>");
         inorder();
         document.write("<br>Delete the node 90<br><br>");
         deleteKey(90);
         document.write("After removing the above nodes, the In-order will be as follows: <br>");
         inorder();
      </script>
   </head>
   <body>
   </body>
</html>

輸出

上述指令碼的輸出將是：

After inserting the above nodes In-order will be:
10 40 50 60 70 80 90 100 120

Delete the node 10

In-order after node 10 is deleted from the tree
40 50 60 70 80 90 100 120

Delete the node 40

In-order after node 40 is deleted from the tree
50 60 70 80 90 100 120

Delete the node 90

After removing the above nodes, the In-order will be as follows:
50 60 70 80 100 120

更新於: 2022-11-18

2K+ 瀏覽量

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告

© . All rights reserved.