Số nút lớn hơn giá trị cho trước trong cây n-ary C++

Cho cây n-ary và số n. Đếm số nút có giá trị > n.

Ví dụ: cây=[[4],[1,2],[3,5]], n=2 → 3 nút lớn hơn 2.

Giải thuật

• Struct Node: data, vector child
• Hàm getNewNode(data)
• Đệ quy getGreaterElementsCount(root, n):
  • Nếu root NULL trả 0
  • count = (root->data > n) ? 1 : 0
  • Duyệt con: count += getGreaterElementsCount(child, n)
  • Trả về count

Ví dụ minh họa

#include <bits/stdc++.h> 
using namespace std; 

struct Node { 
    int data; 
    vector<Node*> child; 
}; 

Node* getNewNode(int data) { 
    Node* temp = new Node; 
    temp->data = data; 
    return temp; 
} 

int getGreaterElementsCount(Node* root, int n) { 
    if (root == NULL) return 0; 
    int count = 0; 
    if (root->data > n) count++; 
    int nodeChildrenCount = root->child.size(); 
    for (int i = 0; i < nodeChildrenCount; i++) { 
        Node* child = root->child[i]; 
        count += getGreaterElementsCount(child, n); 
    } 
    return count; 
} 

int main() { 
    Node* root = getNewNode(1); 
    (root->child).push_back(getNewNode(2)); 
    (root->child).push_back(getNewNode(3)); 
    (root->child).push_back(getNewNode(4)); 
    (root->child[0]->child).push_back(getNewNode(5)); 
    (root->child[0]->child).push_back(getNewNode(5)); 
    (root->child[1]->child).push_back(getNewNode(6)); 
    (root->child[1]->child).push_back(getNewNode(6)); 
    (root->child[1]->child).push_back(getNewNode(7)); 
    (root->child[2]->child).push_back(getNewNode(8)); 
    (root->child[2]->child).push_back(getNewNode(8)); 
    (root->child[2]->child).push_back(getNewNode(9)); 
    int n = 2; 
    cout << getGreaterElementsCount(root, n) << endl; 
    return 0; 
} 

Đầu ra

10