二叉搜索树删除方法

我正在制作一个二叉搜索树，它按字符串键排序。每个节点由与密钥关联的无序链接信息列表组成。树是inorder（按字母顺序排列）。二叉搜索树删除方法

我已完成大部分程序，但在删除方法时遇到问题。

本质上它必须是递归的。该方法必须移除具有给定密钥的节点，以便如果“架构”是给定的字符串，则必须遍历树并移除具有“架构”作为其关键字的对应节点。

我有麻烦，因为我必须删除一个字符串。其他任务使用整数，我必须删除最高或最低值。但是，我不会删除具有最高或最低字符串值的节点，而是删除等于指定字符串的节点。

我在问的是如何去做这个方法。如果您不想提供任何实际的代码，您不必提供任何实际的代码，但是一些指针或建议会很好。

谢谢。

//My attempt: 
//Removes node with corresponding k 
public void remove(String k) { 
    rootNode = remove(rootNode, k); 
} 

//Recursive method: 
private KeyNode remove(KeyNode x, String k) { 
    if (x == null) { 
     return x; 
    } 
    //int comparison with compareTo 
    //if less than 0, left node = remove(left node, k) 
    //if greater than 0, right node = remove(right node, k) 
    //if left node and right node are both null, return null 
    //if left node is null, return left node 
    //if right node is null, return right node 
    //return 
}

来源

2015-02-06 Hiro

是在remove方法测试字符串相等您的问题？如果是这种情况，那么使用'String.equals'。 – sprinter 2015-02-06 13:45:05

你可以显示你的'Node'结构是什么样子，并提供一个简单的示例树，其中包含要删除的节点？ – Edd 2015-02-06 13:45:26

您在删除方法中的评论基本上是正确的。您可以像使用整数一样容易地将compareTo与字符串一起使用。 – sprinter 2015-02-06 13:51:04

你可以做这样的事情

public rootNode remove (String k, rootNode n) { 
    if (n == null) 
     return null; 

    if (k.compareTo(n.key)<0) 
     remove (k, n.leftChild); 
    else if (k.compareTo(n.key)>0) 
     remove (k, n.rightChild); 
    else { 
     if (n.leftChild != null && n.rightChild != null) { 
      /* n has two children, find max from left then 
      * switch it with n and remove n */ 

     } 
     else if(n.leftChild != null) { 
      /* n has a left child only then left child replaces n 
      * and n is deleted */ 


     } 
     else if(n.rightChild != null) { 
      /* n has a right child only then right child replaces n 
      * and n is deleted*/ 

     } 
     else { 
      n = null; 
     } 
    } 

}

来源

2015-02-06 15:34:02

二叉搜索树删除方法

回答

相关问题