Нахождение высоты недвоичного дерева с заданным определением функции - PullRequest
Новая
       9

Нахождение высоты недвоичного дерева с заданным определением функции

0 голосов
/ 23 октября 2019

У меня есть задание, чтобы найти высоту недвоичного дерева, используя данную функцию. Мы не можем изменить тип функции или параметры. Функция: unsigned height() const. Без параметров мы должны все объявить внутренне. До сих пор у меня была следующая функция: 

    template <class T> unsigned Tree<T>::height() const {
    using namespace std;


    Node *pCurr = pRoot;

    typename vector<Tree<T>::Node *>::iterator i = pCurr->children.begin();

    unsigned max = 0;

    if (pRoot == 0) {
        return max;
    }

    if (pCurr->children.empty())
    {
        return max + 1;
    }

    if (i != pCurr->children.end()) {
        i++;
        max++;
        max = max + height();
    }

    return max + 1;
}

Я знаю, что мое условие выхода из функции неверно. У меня возникают проблемы с объявлением моего базового варианта, хотя я и знаю, что логический вариант (ы) должен быть:

  • Дерево пусто: возвращать 0
  • Дерево имеет только корень: возвращено1

Это рекурсивно доходит до того базового случая, с которым у меня возникают проблемы. Я думаю, что я объединяю рекурсивные и итеративные вызовы, и это вызывает проблемы, но я не уверен.

Псевдокод выглядел следующим образом:

if (! Children.empty ())

итерация к следующему дочернему элементу

возврат при достижении конца.

Это самая близкая у меня версия. Я получил достаточно далеко, чтобы вернуть высоту одного дерева узлов, но я получаю ошибку сегментации, когда дерево имеет более одного узла. Я знаю, что это из-за условия выхода. Заранее спасибо!

...