Строка двоичного дерева поиска Вставка/удаление/печать

Question

Я хочу вставлять, удалять и печатать строки в этом BST с использованием общедоступного метода, а не boolean или void - так что я должен вернуться.

В моем методе ввода я пытаюсь проверить на null, а также на левую и правую стороны дерева. В случае, если сравнение между меткой и строкой равно < 0, я устанавливаю left для значения текущего узла. И то же самое для правой стороны.

Мой вопрос, что я должен вернуться в конце этого метода? Я смущен этой частью, вернусь ли я в этом случае?

return false; 

Answer 1

Если вы хотите взглянуть на прочном реализации BST, вот один:

http://algs4.cs.princeton.edu/32bst/BST.java.html

Кроме того, если вы хотите, чтобы на самом деле понять, что и почему происходит там , Я предлагаю посмотреть/прочитать курсы там также.

Edit:

Ну, во-первых, давайте обратимся несколько вопросов здесь.

1. Глядя на ваш класс, вы подаете заявление, что каждый Node является Tree. Теперь это может иметь смысл, но использование Tree в качестве обертки вокруг набора связанных Nodes должно быть намного проще.

2. Говоря в так называемых условиях непрофессионала, вы можете выполнять операцию BST двумя способами, рекурсивно и итеративно. Я приведу вам пример каждого из них.

Итерационная версия:

private void addIterative(T item) { 
    if (root == null) { 
     root = new Node(item); 
     return; 
    } 

    Node parent = null; 
    Node node = root; 

    int cmp = 0; 
    while (node != null) { 
     cmp = item.compareTo(node.item); 

     if (cmp == 0) { 
      return; 
     } else if (cmp < 0) { 
      parent = node; 
      node = node.left; 
     } else { 
      parent = node; 
      node = node.right; 
     } 
    } 

    Node child = new Node(item); 

    if (cmp < 0) { 
     parent.left = child; 
    } else if (cmp > 0) { 
     parent.right = child; 
    } 
} 

Рекурсивная версия:

private Node add(Node node, T item) { 
    if (node == null) { 
     return new Node(item); 
    } 

    int cmp = item.compareTo(node.item); 

    if (cmp == 0) { 
     // it already exists 
    } else if (cmp < 0) { 
     node.left = add(node.left, item); 
    } else { 
     node.right = add(node.right, item); 
    } 

    return node; 
} 

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

С другой стороны, рекурсивная версия, так сказать, само здание. На каждой вставке вы обновляете ссылки на этот путь вниз по дереву.

Итак, итеративный - перемещение по дереву в замкнутом цикле; рекурсивный - перемещение по дереву через рекурсивные вызовы.

Ваш пример заставляет меня думать, что вы должны использовать итеративную версию добавления новых элементов. В этом случае, вы (я верю) просто обязан вернуть экземпляр Tree для метода построения цепочки, так что вы могли бы сделать что-то вроде этого:

node.insert("1").insert("2"); 

Я бы предложил вам пересмотреть, как вы смотрите на Node с и Tree s, но если это невозможно, то я думаю, вам нужно как-то обойти его.