Вывод высоты двоичного дерева отдельно

#c #binary-search-tree

Вопрос:

 int height(struct node* node) 
{ 
    /* base case tree is empty */
    if (node == NULL) 
        return 0; 
  
    /* If tree is not empty then height = 1   max of left 
      height and right heights */
    return 1   max(height(node->left), height(node->right)); 
}

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

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

Ожидаемый результат: высота слева: 1, высота справа: 3 (Cat — корневой узел)

           cat
         /    
      bear     dog
     /         /   
 alligator   dear   tiger
             /       /
            cow    lion
                   /
                 horse

Этот код должен быть написан на языке C. Корректен ли этот метод для определения высоты?

Следующий вывод, сгенерированный для перекрестной проверки дерева путем обхода по порядку

  node:alligator 
 node:bear   bear:->left  alligator
 node:cat    cat:->left  bear     cat:->right dog
 node:cow 
 node:deer   deer:->left  cow
 node:dog    dog:->left  deer     dog:->right tiger
 horse 
 lion   lion:->left  horse
 tiger      tiger:->left  lion

Ответ №1:

Если вам нужна высота слева и справа отдельно, найдите ее отдельно:

 int  left_height = height( root->left) - 1;
int right_height = height(root->right) - 1;

1. Я тоже пробовал этот способ, но он показывает одинаковое значение для всего дерева. показывает 5,5 для обоих деревьев..

2. @johnbyro Тогда проблема в другом месте, этот код в порядке.

3. пожалуйста, прочитайте формулировку проблемы. Это не так, как обычно, оно возвращает -1, если узел отсутствует, и 1, если присутствует один узел . Я не могу интерпретировать эту информацию,

4. @johnbyro Прошу прощения? Я прочитал ваш вопрос, пожалуйста, не думайте, что я этого не сделал. Вы сказали, что для одного узла результат должен быть 0 , следовательно -1 . Ваша проблема заключается в другом коде, а не в этом коде.

5. Я согласен с вами, я дополнил вопрос перекрестным выводом обхода по порядку, он показывает правильно построенное дерево

Ответ №2:

Вызов printf("%d", height(root->left)) и printf("%d", height(root->right)) на вашем корневом узле должен выполнить эту работу.

Ответ №3:

Напишите функцию-оболочку для вашей функции height :

 void printHeight(struct node* root)
{
    int leftHeight = (root==nullptr) ? 0 : height(root->left);
    int rightHeight = (root==nullptr) ? 0 : height(root->right);

    printf("left height: %d, right height: %d", leftHeight-1, rightHeight-1);
}

1. не сработало .. Корректен ли метод height(), который был указан в коде??

2. Обновлено, чтобы сделать -1 то, что, как я надеялся, вы бы назвали себя простым исправлением ошибки.

3. не сработало, я имею в виду, что он не печатает правильную высоту, как ожидалось в постановке задачи. Однако, когда я выполняю обход по порядку, он показывает, что дерево построено правильно, как и ожидалось