如何在二叉搜索樹中刪除具有2個子節點的節點？

  Node* findMaxNode(Node* root) 
      { 
       if(root->right == NULL) return root; 
       findMaxNode(root->right); 
      } 


      Node* DeleteNodeInBST(Node* root,int data) 
      { 
       //base case when not found or found then recursion breaks 

       if(root == NULL) return root; 
       else if(root->data > data) root->left = DeleteNodeInBST(root->left, data); 
       else if(root->data < data) root->right = DeleteNodeInBST(root->right, data); 
       else 
       { 
        //when the node to be deleted is found 
        //Four possibilities 

        //case1: When the node to be deleted has no children 
        if(root->left == NULL && root->right == NULL) 
        { 
         delete root; 
         root = NULL; 
        } 
        //case2: When the node to be deleted has ONLY LEFT child 
        else if(root->right == NULL) 
        { 
         Node* temp = root; 
         root = root->left; 
         delete temp; 
        } 
        //case3: When the node to be deleted has ONLY RIGHT child 
        else if(root->left == NULL) 
        { 
         Node* temp = root; 
         root = root->right; 
         delete temp; 
        } 
        //case4: When the node to be deleted has TWO children 
        else 
        { 
         Node* maxNode = findMaxNode(root->left);//finding the maximum in LEFT sub-tree 
         root->data = maxNode->data; //Overwriting the root node with MAX-LEFT 
         root->left = DeleteNodeInBST(root->left, maxNode->data);//deleted the MAX-LEFT node 
        } 
        return root; 
       } 

      }

來源

2015-04-04 14:44:17

+0

該程序可以工作，但使用不同的方法。有人可以說，爲什麼我被拒絕了嗎？ –

3

用於刪除一個節點有三種可能的情形..

節點是葉節點：這是一種簡單的情況，弄清楚是否這節點是父節點的左側或右側節點，併爲該側的父級設置爲null的子節點。
節點有一個孩子：建立該節點的父節點和子節點之間的直接鏈接。
節點有兩個孩子：這是有點棘手..涉及此步驟。
1. 首先找到該節點的後繼者（或前驅者）。
2. 從樹中刪除後繼者（或前驅者）。
3. 更換節點與

知道缺失的概念之前，我們應該瞭解的繼任者的觀念和前輩

繼承人的繼承（或前身）被刪除：在二進制樹的後繼節點是樹的最小節點，該節點嚴格大於此節點。

有兩種可能的情況下，以節點

一個節點有正確的兒童：在這種情況下，右子樹的最左邊的孩子將是繼任者。

節點沒有子節點：轉到父節點並查找此節點是其左子樹的一部分的節點。現在刪除邏輯

public Node sucessor(Node node) { 
Node sucessor = null; 
if (node.getRightNode() != null) { 
    Node newNode = node.getRightNode(); 
    while (newNode != null) { 
     sucessor = newNode; 
     newNode = newNode.getLeftNode(); 
    } 
} else { 
    sucessor = findRightParent(node); 
} 
return sucessor; 
} 
private Node findRightParent(Node node) { 
Node newNode = null; 
if (node.getParentNode() != null) { 
    if (node.getParentNode().getLeftNode() == node) { 
     newNode = node.getParentNode(); 
    } else { 
     newNode = findRightParent(node.getParentNode()); 
    } 
} 
return newNode; 
}

 public void deleteNode(Node node) { 
    // Node is a leaf node // 
    if(node.getLeftNode() == null && node.getRightNode() == null){ 
     if(isRightNode(node.getParentNode(), node)){ 
      node.getParentNode().setRightNode(null); 
     }else{ 
      node.getParentNode().setLeftNode(null); 
     } 
     // Only left child is there// 
    }else if(node.getLeftNode() != null && node.getRightNode() == null){ 
     if(isRightNode(node.getParentNode(), node)){ 
      node.getParentNode().setRightNode(node.getLeftNode()); 
     }else{ 
      node.getParentNode().setLeftNode(node.getLeftNode()); 
     } 
     // Only Right child is there // 
    }else if(node.getLeftNode() == null && node.getRightNode() != null){ 
     if(isRightNode(node.getParentNode(), node)){ 
      node.getParentNode().setRightNode(node.getRightNode()); 
     }else{ 
      node.getParentNode().setLeftNode(node.getRightNode()); 
     } 
     // Both Left and Right children are their// 
    }else{ 
     Node psNode = predessor(node); 
     deleteNode(psNode); 
     psNode.setParentNode(node.getParentNode()); 
     psNode.setLeftNode(node.getLeftNode()); 
     psNode.setRightNode(node.getRightNode()); 
     if(isRightNode(node.getParentNode(), node)){ 
      node.getParentNode().setRightNode(psNode); 
     }else{ 
      node.getParentNode().setLeftNode(psNode); 
     } 
    } 

    }

溶液從http://coder2design.com/binary-tree/

採取此外，他們已解釋遍歷和插入的完整的源代碼的流動。

來源

2015-07-29 10:48:24

+0

upvote for'Successor'的定義 –

0

算法：

->Find the node which need to delete (assume data is given) 
->Find the deepest node of tree 
->Replace deepest node's data with the node to be deleted 
->Delete the deepest node

Java實現：

public static void deleteTheNode(BTNode root, int data) { 
    BTNode nodeToDelete = findTheNode(root, data); 

    if (nodeToDelete == null) { 
     System.out.println("Node Does not exists in Binary Tree"); 
     return; 
    } 
    BTNode deepestNode = findDepestNodeOfBinaryTree(root); 
    nodeToDelete.setData(deepestNode.getData()); 
    _deleteTheNode(root, deepestNode); 

} 

private static void _deleteTheNode(BTNode root, BTNode node) { 
    Queue<BTNode> q = new LinkedList<>(); 
    q.offer(root); 

    while (!q.isEmpty()) { 
     BTNode temp = q.poll(); 
     if (temp.getLeft() == node) { 
      temp.setLeft(null); 
      node = null; 
      break; 
     } else if (temp.getRight() == node) { 
      temp.setRight(null); 
      node = null; 
      break; 
     } 
     if (temp.getLeft() != null) { 
      q.offer(temp.getLeft()); 
     } 
     if (temp.getRight() != null) { 
      q.offer(temp.getRight()); 
     } 
    } 
} 
//Find the deepest nodeof the binary tree 
public static BTNode findDepestNodeOfBinaryTree(BTNode root) { 
    int depth = 0; 
    BTNode deepetNode = root; 
    Stack<BTNode> nodes = new Stack<>(); 
    Stack<BTNode> path = new Stack<>(); 

    if (root == null) { 
     return null; 
    } 
    nodes.push(root); 
    while (!nodes.empty()) { 
     BTNode node = nodes.peek(); 
     if (!path.empty() && node == path.peek()) { 
      if (path.size() > depth) { 
       depth = path.size() - 1; 
       deepetNode = node; 
      } 
      path.pop(); 
      nodes.pop(); 
     } else { 
      path.push(node); 
      if (node.getRight() != null) { 
       nodes.push(node.getRight()); 
      } 
      if (node.getLeft() != null) { 
       nodes.push(node.getLeft()); 
      } 
     } 
    } 

    return deepetNode; 
}

來源

2018-01-06 05:16:00

0

查找節點的序後繼被刪除。然後複製該節點的中間繼承者的內容並刪除中繼者。（您也可以使用inorder而不是inorder後繼）

來源

2018-01-11 09:21:44

如何在二叉搜索樹中刪除具有2個子節點的節點？

回答

相關問題