数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究C++ 中 n 元树中的下一个较大元素
n 元树是每个节点有 n 个子节点的树。已知一个数字 n，我们必须找到 n 元树中的下一个较大元素。
我们可以通过遍历 n 元树并维护结果来找到解决方案。
算法
- 创建 n 元树。
- 初始化一个结果。
- 编写一个函数来获取下一个较大元素。
- 返回，如果当前节点为 null。
- 检查当前节点数据是否大于预期的元素。
- 如果是，则检查结果是否为空或结果是否大于当前节点数据。
- 如果满足上述条件，则更新结果。
- 获取当前节点子节点。
- 遍历子节点。
- 调用递归函数。
我们每次更新结果都会找到一个大于给定数字且小于结果的元素。它确保我们在最后得到下一个较大元素。
实现
以下是使用 C++ 实现上述算法的代码
#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;
}输出
如果运行上述代码，将会得到以下结果。
23
更新日期：2021 年 10 月 25 日
277 次浏览
广告