рекурсивный код для определения высоты двоичного дерева - PullRequest
Новая
       42

рекурсивный код для определения высоты двоичного дерева

0 голосов
/ 22 марта 2020

Я пытаюсь найти высоту двоичного дерева, и вот моя попытка с тем же 

#include<iostream>
#include<stack>
using namespace std;
int total = 0;
int length = -1;
class Node{
    public:
        int data;
        Node *left;
        Node *right;
        Node(int k){
            data = k;
            left = right = NULL;
        }
};
void height(Node *root){
    if(root==NULL)
        return;
    length++;
    if(length>total)
        total = length;
    height(root->left);
    height(root->right);
}
int main(){
    Node *root = new Node(3);
    root->left = new Node(4);
    root->left->left = new Node(5);
    root->right = new Node(6);
    root->right->left = new Node(7);
    height(root);
    cout<<total;
    return 0;
}

здесь длина и итог были объявлены как глобальные переменные, имеющие значения -1 и 0 соответственно. Когда я запускаю код, я получаю вывод о количестве узлов в дереве - 1 , но не о высоте дерева. Пожалуйста, дайте мне знать мою ошибку здесь.

Ответы [ 2 ]

2 голосов
/ 22 марта 2020

Конечно, вы увеличиваете length на каждом узле.

Если вы делаете это рекурсивно, это на самом деле очень просто: 

std::size_t height(Node const *root) {
    if(!root) return 0;
    return 1 + std::max(height(root->left), height(root->right));
}
0 голосов
/ 22 марта 2020

Ваш подход - скорее отступление, чем простая рекурсия. При таком подходе вы должны быть внимательны, чтобы вернуться к исходному состоянию на каждом шаге. Здесь length всегда увеличивается. Вы должны вернуть его обратно. 

void height(Node *root){
    if(root==NULL)
        return;
    length++;
    total = std::max(total,length+1); // Either this or initialize length as 0
    height(root->left);
    height(root->right);
    length--; // <--- Add this line
}
...