Поиск в двоичном дереве (BT) Not BST

Question

Я пытаюсь выполнить операцию поиска в BT. Например:

 3 (Root) 
    5  1 
6 2 0 8 

Это мой БТ, и это код, который я написал для поиска.

Node* search(Node *root,int key) 
{ 
    if(root) 
    { 
     if(root->key==key) 
     { 
      cout<<root->key<<endl; 
      return root; 
     } 
     search(root->left,key); 
     search(root->right,key); 
    } 
} 

Сво предзаказ обход с условием, что, когда я нахожу нужный мне узел, я должен вернуть его. Например, если я вызываю поиск (корень, 2), поиск должен возвращать указатель Node * к узлу, содержащему значение 2.

Я считаю, что когда мой код возвращается после выполнения условия, он возвращается только к внешнему вызов n не выходит полностью. Например, если A вызывает B вызывает C, n, то есть возврат в C, он возвращает значение B, а не функцию, которая называется A.

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

Любая помощь оценена!

Answer 1

Вопрос 1: вам не нужно возвращать значение, если вы не нашли требуемое значение. return NULL; в конце вашей функции.

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

Node* r = search(root->right, key); 
if (r) return r; 

Answer 2

Node* search(Node *root, int key){ 
    if(root){ 
     if(root->key == key){ 
      return root; 
     } 
     Node *ret; 
     (ret = search(root->left, key)) || (ret = search(root->right, key)); 
     return ret; 
    } 
    return NULL; 
} 

Answer 3

Добавить функцию выхода после того, как условие выполняется, чтобы уменьшить накладные расходы program.Also добавить условие не найден

if(root->key==key) 
    { 
     cout<<root->key<<endl; 
     return root; 
     exit(-1); 
    }