Метод двоичного поиска дерева Метод удаления

Я делаю двоичное дерево поиска, которое сортируется по клавише String. Каждый узел состоит из неупорядоченного связанного списка информации, которая связана с ключом. Дерево inorder (в алфавитном порядке).Метод двоичного поиска дерева Метод удаления

Я завершил большую часть программы, но проблема с методом удаления.

По существу это должно быть рекурсивным. Метод должен удалить узел с указанным ключом, так что если «Архитектура» была указана в String, я должен пройти через дерево и удалить соответствующий узел с помощью «Архитектуры» в качестве его ключа.

У меня возникли проблемы, потому что мне нужно удалить строку. В других назначениях использовались целые числа, в которых я должен удалить максимальное или минимальное значение. Однако я не удаляю узел с наивысшим или самым низким значением String, а узел, который равен указанной строке.

Все, что я прошу, - это как это сделать. Вам не нужно предоставлять какой-либо фактический код, если вы этого не сделаете, но некоторые указатели или рекомендации будут приятными.

спасибо.

//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

вас проблема с тестирования строки равенства в методе удалить? Если это так, используйте 'String.equals'. – sprinter

Можете ли вы показать, как выглядит ваша структура 'Node', и предоставить простое дерево образцов, содержащее узел, который вы хотите удалить? – Edd

ваши комментарии в методе удаления, по сути, правильны. Вы можете использовать compareTo со строками так же легко, как целые. – sprinter

вы могли бы сделать что-то вроде этого

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

Метод двоичного поиска дерева Метод удаления

ответ

Смежные вопросы