從BinaryTree中刪除一片樹葉

我的下面的代碼將移除一棵有兩個孩子或一個孩子的樹。但是一片葉子（一棵沒有孩子的樹）我似乎無法破解。我的BSTNode<E>也包含一個.parent，它標識它的父母。我不確定這是否有助於此實施。從BinaryTree中刪除一片樹葉

@Override 
public E delete(E target) { 
    return delete(this.root, target); 
} 

private E delete(BSTNode<E> localRoot, E target) { 
    // ... Trying to delete an item that's not in the tree? 
    if (localRoot == null) { 
     return null; 
    } 

    int compareResult = c.compare(target, localRoot.data); 

    // Traverse the tree... 
    if (compareResult < 0) { 
     return delete(localRoot.left, target); 
    } else if (compareResult > 0) { 
     return delete(localRoot.right, target); 
    } else { 
     // Found the item! Oh boy here we go! 
     E retVal = localRoot.data; 

     /* 
     * Both left and right exist under the targeted node. 
     * Find the largest child under the right side of the node. 
     * Set the largest data to the 'deleted' node, then delete that node. 
     */ 
     if (localRoot.left != null && localRoot.right != null) { 
      /* 
      * Two children, find the smallest and assign it. 
      */ 
      localRoot.data = localRoot.right.data; 
      localRoot.right = findLargestChild(localRoot.right); 
     } else if (localRoot.left != null) { 
      localRoot.data = localRoot.left.data; 
      localRoot.left = findSmallestChild(localRoot.left); 
     } else if (localRoot.right != null) { 
      localRoot.data = localRoot.right.data; 
      localRoot.right = findLargestChild(localRoot.right); 
     } else { 
      /* 
      * TODO: 
      * Remove a leaf. 
      */ 
      System.out.println("Removing leaf..." + localRoot.data.toString()); 
      localRoot = null; 
     } 

     return retVal; 
    } 
}

來源

2016-11-21 kneeki

「我的代碼將刪除一個有兩個孩子，或一個孩子的樹。刪除什麼？你想從樹中刪除一個子樹？ –

是的，每棵樹都是由一個數據值和兩個孩子（左和右）組成的節點。這些孩子不是樹就是空。我到目前爲止的代碼將移除有兩個孩子（非空的樹）或一個孩子的樹。但是，沒有孩子的樹（左右都是空）不起作用。這就是我的TODO表揚所在。 – kneeki

在葉子的情況下，您只需要將其刪除，所以只需將其父項的子項設置爲「null」即可。這樣，從樹的內部，沒有意思訪問樹葉，所以它基本上不在樹上了。這不是你期望的行爲嗎？ –

使用localRoot.parent我能刪除（null）的localRoot的父母的孩子。這感覺倒退，但它通過JUnit測試...

private E delete(BSTNode<E> localRoot, E target) { 
    // ... Trying to delete an item that's not in the tree? 
    if (localRoot == null) { 
     return null; 
    } 

    int compareResult = c.compare(target, localRoot.data); 

    // Traverse the tree... 
    if (compareResult < 0) { 
     return delete(localRoot.left, target); 
    } else if (compareResult > 0) { 
     return delete(localRoot.right, target); 
    } else { 
     // Found the item! Oh boy here we go! 
     E retVal = localRoot.data; 

     if (localRoot.right != null) { 
      /* 
      * Assign the largest value to the tree. 
      */ 
      localRoot.data = localRoot.right.data; 
      localRoot.right = findLargestChild(localRoot.right); 
     } else if (localRoot.left != null) { 
      /* 
      * Since the largest value didn't exist, assign the smallest. 
      */ 
      localRoot.data = localRoot.left.data; 
      localRoot.left = findSmallestChild(localRoot.left); 
     } else { 
      /* 
      * Remove a leaf. 
      */ 
      System.out.println("Removing leaf or left..." + localRoot.data.toString()); 
      if (c.compare(target, localRoot.parent.left.data) == 0) { 
       localRoot.parent.left = null; 
      } else { 
       localRoot.parent.right = null; 
      } 
     } 

     return retVal; 
    } 
}

來源

2016-11-21 05:17:39 kneeki

從BinaryTree中刪除一片樹葉

回答

相關問題