C++ 中 n 元树中的下一个较大元素

n 元树是每个节点有 n 个子节点的树。已知一个数字 n，我们必须找到 n 元树中的下一个较大元素。

我们可以通过遍历 n 元树并维护结果来找到解决方案。

算法

  • 创建 n 元树。
  • 初始化一个结果。
  • 编写一个函数来获取下一个较大元素。
    • 返回，如果当前节点为 null。
    • 检查当前节点数据是否大于预期的元素。
    • 如果是，则检查结果是否为空或结果是否大于当前节点数据。
    • 如果满足上述条件，则更新结果。
    • 获取当前节点子节点。
    • 遍历子节点。
      • 调用递归函数。

我们每次更新结果都会找到一个大于给定数字且小于结果的元素。它确保我们在最后得到下一个较大元素。

实现

以下是使用 C++ 实现上述算法的代码

Open Compiler
#include <bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   vector<Node*> child;
};
Node* newNode(int data) {
   Node* newNode = new Node;
   newNode->data = data;
   return newNode;
}
void findNextGreaterElement(Node* root, int x, Node** result) {
   if (root == NULL) {
      return;
   }
   if (root->data > x) {
      if (!(*result) || (*result)->data > root->data) {
         *result = root;
      }
   }
   int childCount = root->child.size();
   for (int i = 0; i < childCount; i++) {
      findNextGreaterElement(root->child[i], x, result);
   }
   return;
}
int main() {
   Node* root = newNode(10);
   root->child.push_back(newNode(12));
   root->child.push_back(newNode(23));
   root->child.push_back(newNode(45));
   root->child[0]->child.push_back(newNode(40));
   root->child[1]->child.push_back(newNode(33));
   root->child[2]->child.push_back(newNode(12));
   Node* result = NULL;
   findNextGreaterElement(root, 20, &result);
   cout << result->data << endl;
   return 0;
}

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

输出

如果运行上述代码，将会得到以下结果。

23

更新日期：2021 年 10 月 25 日

277 次浏览

职业生涯启航

完成课程即可获得认证

开始学习
广告