Функция, чтобы найти количество узлов ниже определенной глубины BST - PullRequest
Новая
       31

Функция, чтобы найти количество узлов ниже определенной глубины BST

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

Я пытаюсь создать функцию, которая будет подсчитывать количество узлов больше определенной глубины "k".

Вот мой код функции обхода дерева и вспомогательной функции для поиска глубина каждого узла: 

    int findDepth(BinaryNode * t, int value, int depth){

    if( t == nullptr ){
        return 0;
    }
    if( t->element == value){
        return depth;
    }
    int lowerDepth = findDepth(t->left, value, depth+1);

    if(lowerDepth != 0){
        return lowerDepth;
    }
    lowerDepth = findDepth(t->right, value, depth+1);

    return lowerDepth;

}

int countDeep( BinaryNode * t, int k ){
    int count = 0;
    if (t != nullptr){
        countDeep( t->left, k );
        if (findDepth(t, t->element, 0)){
            count++;
        }
        countDeep( t->right, k );
    }
    return count;
}

Сейчас функция всегда возвращает 0, и я не совсем уверен, почему.

1 Ответ

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

учтите это: 

int countDeep( BinaryNode * t, int k ){
    int count = 0;
    if (t != nullptr){
        countDeep( t->left, k );
        if (findDepth(t, t->element, 0)){
            count++;
        }
        countDeep( t->right, k );
    }
    return count;
}

Я не внимательно прочитал другие фрагменты кода, но эта функция возвращает либо 0, либо 1. Потому что вы отбросили возвращаемое значение в рекурсии. Эту функцию можно рассматривать как чистую функцию (хотя вы модифицируете count - ++), поэтому ее вызов без использования возвращаемого значения неверен.

Так что, если другая функция вызовет эту функцию, count функции имеют только один шанс самосинхронизироваться , я не проверял ваш код, может быть, этого «единственного случая» не существует а также.

...