首页 文章

为什么删除根节点保留左子树而不是我的右子树?

提问于
浏览
0

所以我为BST实现创建了一个删除功能 . 它适用于删除叶节点的情况,以及与正确子节点相关的子树,但没有左子节点,反之亦然 .

但是,删除根节点给我带来了问题 . 我试图用它的后继替换root,然后将new root的右子设置为等于old root的右子 .

例:

50
       /  \
      /    \
     42     63
    / \    /
   /   \  55 
  21   43      
    \    \    
    23    \    
   / \    47
  /   \
 44   48

如果我要在我的程序中删除节点50,那么55将是新根,但是63会消失,但其他一切正常 .

我是否错误地重新连接节点? (从代码中的 "Problem is Here" 评论开始)

//How I display my tree
//inprder traversal
private void inOrder(Node curr){

      if(curr != null){
         //traverse left
         inOrder(curr.leftChild);

         System.out.print("\n" + curr + "->");

         //traverse right
         inOrder(curr.rightChild);
      }

   } 

public boolean deleteContact(String key){
      //Start at root node
      Node currentNode = root;
      Node parent = root;

      boolean isLeftChld = true;
      //loop over left and right subtrees
      //finds node to be deleted
      while(!key.equals(currentNode.key)){

         parent = currentNode;

         if(key.compareToIgnoreCase(currentNode.key) < 0){

            isLeftChld = true;
            currentNode = currentNode.leftChild;

         }else{

            isLeftChld = false;
            currentNode = currentNode.rightChild;

         }
         //Node never found
         if(currentNode == null){
            return false;
         }
      }

      //if the node doesnt have children
      //go ahead and delete
      if(currentNode.leftChild == null && currentNode.rightChild == null){
         if(currentNode == root){

            root = null;
         //Handle case of juss deleting leafs
         }else if(isLeftChld){//check if it was a left or right child
            //delete it
            parent.leftChild = null;

         }else{

            parent.rightChild = null;

         }

      //situation of no right child
      //handling node dissapearing
      } else if(currentNode.rightChild == null){
         if(currentNode == root){

            root = currentNode.leftChild;
         }else if (isLeftChld){

            parent.leftChild = currentNode.leftChild;

         }else{

            parent.rightChild = currentNode.leftChild;
         }

      //situation of no left child
      }else if(currentNode.leftChild == null){
         if(currentNode == root){

            root = currentNode.rightChild;

         }else if (isLeftChld){

            parent.leftChild = currentNode.rightChild;

         }else{

            parent.rightChild = currentNode.leftChild;
         }
       **Problem is Here**
      //situation of two children being involved
      //figure out which node will replace which
      } else {
         //Node temp = currentNode.rightChild;
         Node successor = minValue(currentNode.rightChild);

         if(currentNode == root){
            root = successor;

         }else if(isLeftChld){
            parent.leftChild = successor;

         }else{
            parent.rightChild = successor;
         }

         root.leftChild = currentNode.leftChild;

      }

      return true;

   }

   //Function to return min value for a root node
   //Used for delete function - finds succesor
   private Node minValue(Node root)
    {
        Node minv = root;
        while (root.leftChild != null)
        {
            minv = root.leftChild;
            root = root.leftChild;
        }
        return minv;
    }

1 回答

  • 1

    您还需要分配正确的孩子 .

    //Root is 50 [42, 63]
    
         if(currentNode == root){
            root = successor;
    
         //Root is 55 [null, null]
         }else if(isLeftChld){
            parent.leftChild = successor;
    
         }else{
            parent.rightChild = successor;
         }
    
         //Root is 55 [42, null]
         root.leftChild = currentNode.leftChild;
    

    缺少以下行:

    root.rightChild = currentNode.rightChild;
    

相关问题