Реализация рекурсивной функции Void (определение высоты дерева двоичного поиска)

Question

Мне нужно реализовать функцию void, которая вычисляет высоту каждого узла в двоичном дереве и сохраняет его в каждом узле. В Интернете я нашел несколько решений, которые по своей природе рекурсивны, но возвращают int. Примеры включают в себя (https://www.geeksforgeeks.org/write-a-c-program-to-find-the-maximum-depth-or-height-of-a-tree/). Разница между ответом модели, кроме того, что это не пустая функция, в том, что она также не сохраняет высоту в каждом узле.

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

void computeHeight(Node *n) {
  Node* ltraverser = n;
  Node* rtraverser = n;
  int lheight = 0;
  int rheight =0;

  if (n == NULL) {
   n->height = 0;
  }

  while (ltraverser->left != NULL) {
   ltraverser = ltraverser->left;
   lheight += 1;
  }

  while (rtraverser->right != NULL) {
   rtraverser = rtraverser->right;
   lheight += 1;
  }

  if (lheight > rheight) {
    n->height = lheight;
  }

  else {
    n->height = rheight;
  }

  computeHeight(n->left);
  computeHeight(n->right);
}

Для справки:

The starter code below defines a class called "Node" that has two child pointers ("left" , "right") and an integer "height" member variable. There is also a constructor Node() that initializes the children to nullptr and the height to -1.

/*
The height of a node is the number of edges in
its longest chain of descendants.

Implement computeHeight to compute the height
of the subtree rooted at the node n. Note that
this function does not return a value. You should
store the calculated height in that node's own
height member variable. Your function should also
do the same for EVERY node in the subtree rooted
at the current node. (This naturally lends itself
to a recursive solution!)

Assume that the following includes have already been
provided. You should not need any other includes
than these.

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>

You have also the following class Node already defined.
You cannot change this class definition, so it is
shown here in a comment for your reference only:

class Node {
public:
  int height; // to be set by computeHeight()
  Node *left, *right;
  Node() { height = -1; left = right = nullptr; }
  ~Node() {
    delete left;
    left = nullptr;
    delete right;
    right = nullptr;
  }
};
*/

Для проверки кода

// This function prints the tree in a nested linear format.
void printTree(const Node *n) {
  if (!n) return;
  std::cout << n->height << "(";
  printTree(n->left);
  std::cout << ")(";
  printTree(n->right);
  std::cout << ")";
}

  Node *n = new Node();
  n->left = new Node();
  n->right = new Node();
  n->right->left = new Node();
  n->right->right = new Node();
  n->right->right->right = new Node();

  computeHeight(n);

  printTree(n);
  std::cout << std::endl << std::endl;
  printTreeVertical(n);

  delete n;
  n = nullptr;

  return 0;
}

Answer 1

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

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <algorithm>

class Node {
public:
  int height;
  Node *left, *right;
  Node() { height = -1; left = right = nullptr; }
  ~Node() {
    delete left;
    left = nullptr;
    delete right;
    right = nullptr;
  }
};

void computeHeight(Node *node) {

    if (node == nullptr) {
        return;
    }

    computeHeight(node->left);
    computeHeight(node->right);

    int leftHeight = -1;
    int rightHeight = -1;

    if (node->left != nullptr) {
        leftHeight = node->left->height;
    }

    if (node->right != nullptr) {
        rightHeight = node->right->height;
    }

    node->height = std::max(leftHeight, rightHeight) + 1;
}

void printNode(Node *n, int level = 0) {
    if (n == nullptr) {
        return;
    }

    std::cout << std::string(level * 2, ' ') << "Height = " << n->height << "\n";

    printNode(n->left,  level + 1);
    printNode(n->right, level + 1);
}


int main() {
  Node *n = new Node();
  n->left = new Node();
  n->right = new Node();
  n->right->left = new Node();
  n->right->right = new Node();
  n->right->right->right = new Node();


  computeHeight(n);
  printNode(n);
}

Answer 2

Ваша ошибка в следующей части, и из-за этого ваша программа завершает работу, не показывая ошибку

if (n == NULL) {
   n->height = 0;
}

Когда n равно NULL;Вы не должны пытаться получить доступ к n-> высоте. Замените его следующим образом, и ваш код будет работать:

if (n == NULL) {
    return;
}

Кроме того, как уже упоминалось в другом ответе, когда вы хотите вычислить высоту рекурсивно, вам не нужен цикл while, просто используйте следующую рекурсивную формулу:

Height(n) = 1 + max(Height(n->left), Height(n->right))

Кроме того, по соображениям согласованности обычно высота NULL поддерева определяется как -1. Это позволяет рекурсивной формуле работать правильно.

Совет: Чтобы отладить любую программу, проще всего просто напечатать сообщения до и после вызовов функций и / или определенных строк. ,Таким образом, проверяя, какие сообщения не напечатаны, вы можете быстро определить, какие функции / строки вызывают проблему, а затем исследовать их.