Использование рекурсивно возвращаемой ссылки на узел в дереве не позволяет вносить изменения в сам узел - PullRequest
Новая
       18

Использование рекурсивно возвращаемой ссылки на узел в дереве не позволяет вносить изменения в сам узел

0 голосов
/ 27 ноября 2009

Мой класс структур данных работает с деревьями. Мы реализуем 3-арное дерево, содержащее 2 значения со ссылкой на левый, средний и правый узлы (левое поддерево меньше значения 1, среднее поддерево находится между значением 1 и значением 2, правое поддерево больше значения 2 ). Для класса Tree был предоставлен интерфейс, и методы поиска, вставки и удаления должны быть рекурсивными. Код клиента, с которым это будет проверено, многократно использует метод вставки для создания дерева, и корень запускается как null.

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

Я почти уверен, что это связано с тем, как ссылки и значения работают в Java (аналогично C #, как описано в этой статье Jon Skeet ); учитывая ограничения, как я должен изменить это, чтобы разрешить вставки в дерево? Ниже приведен текущий метод вставки в класс дерева вместе с аналогичным закрытым методом. 

public void insert(AnyType newData)
{
    // If insert node is null, make a new node with newData as first key
    TernaryNode<AnyType> insert_node = findNode(newData, root);
    if (insert_node == null)
    {
        insert_node = new TernaryNode<AnyType>(newData);
    }
    else
    {
        // Get the key that is equal if the insert node is not null
        if (insert_node.getKey1() == null)
        {
            insert_node.setKey1(newData);
        }
        else
        {
            insert_node.setKey2(newData);
        }
    }// end else
}// end insert

private TernaryNode<AnyType> findNode(AnyType item, TernaryNode<AnyType> node)
{
    TernaryNode<AnyType> current_node = node;
    if (current_node != null)
    {
        if (current_node.getKey1() != item &&
                current_node.getKey2() != item)
        {
            // Comparator checks left
            if (compare.compare(current_node.getKey1(), item) <= -1)
            {
                return findNode(item, current_node.left);
            } // Comparator checks right
            else  if (compare.compare(current_node.getKey2(), item) >= 1)
            {
                return findNode(item, current_node.right);
            }// Comparator checks middle
            else
            {
                return findNode(item, current_node.middle);
            }
        }// end while
    }// end if
    // Return current node even if it is null
    return current_node;
}// end findNode

Ответы [ 2 ]

1 голос
/ 27 ноября 2009

Если вы не назначаете что-либо члену root, оно никогда не получит значение. Вероятно, вам нужен какой-то внешний контейнер для вашего дерева, аналогично тому, как XML-документ (который также является деревом) имеет внешний Document объект, который отличается от фактического корневого узла документа.

0 голосов
/ 27 ноября 2009 
    TernaryNode<AnyType> insert_node = findNode(newData, root);
    if (insert_node == null)
    {
            insert_node = new TernaryNode<AnyType>(newData);
            root = insert_node;
    }
...