資料結構
網路
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 次瀏覽
廣告