Бинарное дерево поиска не дает результатов (C ++)

Question

Я работаю над некоторыми алгоритмами двоичного дерева и мне нужна функция "найти узел с помощью searchindex ...".Дизайн для триодов в основном

class TreeNode {
  int index; // some identifier
  TreeNode *left;
  TreeNode *right;
}

, а дерево определяется указателем на корневой узел.

Моя реализация для функции поиска:

void Tree::searchNode(TreeNode * root, int nodeIndex, TreeNode *resultNode){
/* Recursive search */

  if (root->index == nodeIndex) {
            resultNode = root;
  } else {

    /*  search children if the current node is not a leaf */

    if(!root->isLeaf()) {
        this->searchNode(root->left,nodeIndex,resultNode);
        this->searchNode(root->right,nodeIndex,resultNode);
        }
  }
}

Аргументы: * root является корневым узлом дерева, nodeIndex является поисковым индексом, а * resultNode являетсяуказатель на найденный (или нет) узел в дереве.

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

Другой класс с деревом buildingTree в качестве члена использует функцию поиска следующим образом:

TreeNode *resultNodePtr = NULL;
this->buildingTree->searchNode(this->buildingTree->rootPtr, 
                               currentNodeIndex, resultNodePtr);

// do sth. with resultNodePtr if != NULL

Я создаю * resultNodePtr в стеке, потому что он мне просто нужен временно внутри функции.Это сделано правильно?Однако: функция не работает. resultNodePtr всегда равно NULL, даже если дерево содержит узел с поисковым индексом.Я очень тщательно отлаживал шаг за шагом, он правильно определяет

(root->index == nodeIndex)

, но

  resultNode = root; 

не работает (я хочу, чтобы resultNode указывал на тот же адрес root указывает на).Отладчик говорит, что resultNode до присвоения 0x0, корневой узел - некоторый адрес, после присвоения resultNode остается 0x0.

Должен ли я перегружать оператор = в этом случае для класса TreeNode?

Я пробовал:

TreeNode & TreeNode::operator=(const TreeNode & oldTreeNode){
 *this = oldTreeNode;
 return *this;
 // ignore childs for now
}

Я не эксперт, но этот оператор= кажется тривиальным.Влияет ли это на назначение двух указателей TreeNode * node1 = * node2 на всех?

Может быть, вы можете мне помочь.Спасибо за чтение, ценю вашу помощь.Если я сам найду решение, я опубликую его здесь.

С уважением, Марк

Answer 1

Поскольку вы передаете resultNode в функцию как указатель по значению , его исходное значение никогда не изменяется. Думайте о TreeNode* буквально как о не более чем числе, представляющем адрес памяти; когда вы переназначаете его:

resultNode = root;

Это изменяет копию, которая searchNode имеет, но не оригинальный указатель в коде, который вызывает searchNode. Возьмите этот более простой пример:

void Foo(int x)
{
    x = 100;
}

void Bar()
{
    int x = 0;
    Foo(x);
    // at this point, x is still 0
}

Значение

resultNode не меняется с NULL по той же причине, что x не изменяется с 0 при вызове функции Bar. Чтобы устранить эту проблему, передайте указатель как указатель на указатель или указатель по ссылке:

void Tree::searchNode(TreeNode* root, int nodeIndex, TreeNode*& resultNode)
{
    // same code
}

... или:

void Tree::searchNode(TreeNode* root, int nodeIndex, TreeNode** resultNodePtr)
{
    // assign to *resultNodePtr instead
}

Answer 2

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

Ваш алгоритм выглядит отлично:)