Глубина узла в двоичном дереве

Question

Я написал следующую функцию, которая возвращает глубину конкретного узла двоичного дерева. Рассмотрим дерево здесь: если я попрошу глубину узла 5, я должен получить ответ 3, от пути 1 -> 2 -> 5.

Это не работает; Я получаю 0, хотя я возвращаю высоту из функции.

Здесь «данные» - это значение, значение глубины которого должно быть найдено, а корень - корневой узел дерева. Начальное значение высоты равно 1 (корневой узел - уровень 1).

int height_target(node *root,int data,int height){ if(root==NULL) return 0; 

if(root->info==data) 
return height; 

height_target(root->left,data,height+1); 
height_target(root->right,data,height+1); 
} 

Answer 1

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

Вам необходимо убрать и вернуть максимум левых & правильных подзаголовков.

---

EDIT: удалить последнее предложение ...

Таким образом, вам необходимо вернуть значение из любого вызова (слева или справа) находит нужный узел. Вы ничего не вернули. Что-то вроде:

ldepth = height_target(root->left , data, height+1); 
if (ldepth > 0) 
    return ldepth; 
rdepth = height_target(root->right, data, height+1); 
if (rdepth > 0) 
    return rdepth; 
return 0; 

Это будет возвращать в ветви успешно найти нужный узел, и 0 в противном случае.

Answer 2

Вы ничего не делаете со значением, возвращаемым с высоты_трассы.

Предположительно вы хотите что-то вроде:

return std::max(height_target(root->left,data,height+1), 
       height_target(root->right,data,height+1)); 

Answer 3

Я думаю, вы получите 0 в качестве answwer, потому что условие if(root->info==data) никогда не удовлетворяется, если не существует узел со значением, равным данных. Если вы получите 0 в качестве ответа, было бы так, что «данных», которые вы ищете в двоичном дереве, нет.

Answer 4

Хорошо. Думаю, я понял. Попробуйте с помощью функции, как это:

void height_target(node* root,int data,int height,int& h) 
{ 
    if(root==NULL) 
    return; 

    if(root->info==data) 
    h=height; 

    height(root->left,data,height+1,h); 
    height(root->right,data,height+1,h); 

} 

Я думаю, что вы supposend, что не может быть двух одинаковых значений в дереве

Answer 5

Это не работает;

Вот один из возможных решений в код: (обновлено - этот код в настоящее время составляет)

Резюме - последние две строк ваших результатов коды отменяемых во время «decursion» (когда рекурсия разгадки).

int height_target(node* current, int data, int height) 
{ 
    int retVal = 0; 

    do { 

     if (nullptr == current) 
     break; // 0 indicates not found 

     if (current->info == data) { retVal = height; break; } 
     // found the node at 'height'; now de-curse 

     retVal = height_target (current->left, data, height+1); 
     if (retVal) break; // found data in left branch 

     retVal = height_target(current->right, data, height+1); 
     if(retVal) break; // found data in right branch 

    }while(0); 

    return retVal; 
} 

Представьте ваш поиск элемент найден 5 слоев «вверх», так что высокая рекурсия возвращает 5.

На слое 4, данные не были найдены, так что ваш код, то искал как левую ветвь и правая ветвь.

С любой ветвью, когда ваш код возвращен (из уровня 5) со значением «5», ваш код просто отменил результат.

---

В этом возможном решении я проверил retVal после возвращения с левой или с правой стороны. Теперь, если возвращаемое значение (из уровня 5) не равно нулю, функция вернет ненулевое значение; в конечном счете, вытащив значение из стека, полностью назад «вниз» до нижней части вашей рекурсии.

Возможно упрощенным след вызов может иллюстрировать:

height_target (., ., 1); // first call, data not found at root 
| height_target (., ., 2); // recursive call, data not found 
| | height_target (., ., 3); // recurse, not found 
| | | height_target (., ., 4); // recurse, not found 
| | | | height_target (., data, 5); // found! 'decursion' begins 
| | | | | 
| | | | returns 5 // height 5 returns 5 
| | | returns 5 // height 4 return 5 
| | returns 5 // height 3 returns 5 
| returns 5 // height 2 returns 5 
returns 5 // height 1 returns 5 

Первый звонок теперь возвращает 5.

Answer 6

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

Рассмотрим:

#include <iostream> 

int f(int args) { 
    if (args == 3) 
     return args; 
    f(args + 1); 
    std::cout << args << "\n"; 
} 

int main() { 
    f(0); 
} 

http://ideone.com/59Dl7X

Ваш компилятор должен предупреждал вас о функции не возвращает значение.

То, что вы хотите что-то вроде этого:

static const size_t NODE_NOT_FOUND = 0; 

size_t height_target_impl(node *root, int data, size_t height) 
{ 
    if (root == nullptr) 
     return NODE_NOT_FOUND; 

    if (root->info == data) 
     return height; 

    int branch_height = height_target_impl(root->left, data, height + 1); 
    if (branch_height != NODE_NOT_FOUND) 
     return branch_height; 
    return height_target_impl(root->right, data, height + 1); 
} 

size_t height_target(node* root, int data) 
{ 
    return height_target_impl(root, data, 1); 
} 

Вызывается как:

int h = height_target(root, data); 

Это возвращает значение 0, если узел не найден или 1 на основе высоты а, с 1, указывающие данные, были найдены в корневом узле.