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();
  }
}