다음 C++의 n-ary 트리에서 더 큰 요소

<시간/>

n-ary 트리는 각 노드에 대해 n개의 자식이 있는 트리입니다. 숫자 n이 주어지고 n-ary 트리에서 다음으로 큰 요소를 찾아야 합니다.

n-ary 트리를 순회하고 결과를 유지함으로써 해를 찾을 수 있습니다.

알고리즘

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

출력

위의 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.