C ++ Найти узел с наибольшим значением в неупорядоченном дереве

Question

Я попытался найти эту проблему в stackoverflow, но не смог ее найти, поэтому извините, если она уже существует.

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

struct Node
{
private:
    Node* parent;
    list<Node> childs;
    int value;
public:
    // Getters, setters and constructors
}

struct Tree
{
private:
    Node* root;
public:
    // Getters, setters and constructors
}

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

Простите, если мой вопрос кажется глупым / глупым, но мне действительно нужна помощь

Answer 1

Вы можете использовать рекурсивный метод, который возвращает указатель на узел с максимальным значением текущего и дочернего узлов:

struct Node
{
...
  Node* getMaxNode()
  {
    Node* maxNode = this;
    for (auto& child : this->childs) {
      Node* childsMaxNode = child.getMaxNode();
      if (childsMaxNode->getValue() > maxNode->getValue())
        maxNode = childsMaxNode;
    }
    return maxNode;
  }
}

Если текущий узел не имеет дочерних узлов, он вернет указатель на текущий узел. Итак, в struct Tree вы можете реализовать что-то вроде этого:

struct Tree
{
  Node* getMax()
  {
    return this->root->getMaxNode();
  }
}