Phần tử lớn hơn tiếp theo trong cây n-ary trong C ++

Cây n-ary là cây có n nút con cho mỗi nút. Chúng ta được cho một số n và chúng ta phải tìm phần tử lớn hơn tiếp theo từ cây n-ary.

Chúng ta có thể tìm ra giải pháp bằng cách duyệt qua n-ary tree và duy trì kết quả.

Thuật toán

• Tạo cây n-ary.
• Khởi tạo một kết quả.
• Viết một hàm để lấy phần tử lớn hơn tiếp theo.
  • Quay lại nếu nút hiện tại là rỗng.
  • Kiểm tra xem dữ liệu nút hiện tại có lớn hơn phần tử mong đợi hay không.
  • Nếu có, hãy kiểm tra xem kết quả là trống hay kết quả lớn hơn dữ liệu nút hiện tại.
  • Nếu điều kiện trên thỏa mãn, hãy cập nhật kết quả.
  • Nhận các nút con hiện tại.
  • Lặp lại các phần con.
    • Gọi hàm đệ quy.

Chúng tôi đang cập nhật kết quả mỗi khi chúng tôi tìm thấy một phần tử lớn hơn số đã cho và nhỏ hơn kết quả. Nó đảm bảo rằng cuối cùng chúng ta nhận được phần tử lớn hơn tiếp theo.

Thực hiện

Sau đây là cách thực hiện thuật toán trên trong 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;
}

Đầu ra

Nếu bạn chạy đoạn mã trên, thì bạn sẽ nhận được kết quả sau.

23