Đếm các nút của cây có chuỗi có trọng số chứa một nguyên âm trong C ++

Cho một cây nhị phân với trọng số của các nút là chuỗi. Mục đích là tìm số nút có trọng số sao cho chuỗi chứa một nguyên âm. Nếu trọng số là ‘aer’ thì nó có các nguyên âm ‘a’ và ‘e’ nên nút sẽ được tính.

Ví dụ

Đầu vào

Cây sẽ được tạo sau khi nhập các giá trị được đưa ra bên dưới -

Đầu ra

Count the nodes of the tree whose weighted string contains a vowel are: 5

Giải thích

chúng ta được cung cấp với các nút cây và trọng số chuỗi được liên kết với mỗi nút. Bây giờ chúng ta kiểm tra xem chuỗi các nút có chứa các nguyên âm hay không.

Đầu vào

Cây sẽ được tạo sau khi nhập các giá trị được đưa ra bên dưới -

Đầu ra

Count the nodes of the tree whose weighted string contains a vowel are: 3

Giải thích

with the tree nodes and the string weights associated with each node. Now we check whether the string of nodes contains vowels or not.

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau -

Trong cách tiếp cận này, chúng tôi sẽ áp dụng DFS trên biểu đồ của cây để duyệt qua nó và kiểm tra xem trọng số của nút có một chuỗi chứa một nguyên âm hay không. Lấy hai vectơ Node_Weight (100) và edge_graph [100] cho mục đích này.

• Khởi tạo Node_Weight [] với trọng số của các nút.

• Tạo cây bằng cách sử dụng vector edge_graph.

• Lấy một nguyên âm biến toàn cục và khởi tạo nó bằng 0.

• Chức năng kiểm tra (string check_it) nhận chuỗi s và trả về true nếu check_it chứa một nguyên âm trong đó.

• Lấy length =check_it.length () làm số ký tự trong check_it.

• Traverse check_it sử dụng vòng lặp for từ chỉ mục i =0 đến i

• Chuyển mỗi check_it [i] thành chữ thường và được lưu trữ trong c.

• Nếu c bằng một trong các nguyên âm (‘a’, ‘e’ ‘i’, ‘o’, ‘u’) thì trả về true, còn lại thì trả về false.

• Hàm string_vowel (int node, int root) lấy một nút và nút gốc của cây và trả về số lượng các nút trong cây đã cho có trọng số chứa một nguyên âm là ký tự.

• Lấy str =Node_Weight [node].

• Nếu check (str) trả về true thì tăng nguyên âm.

• Cây ngang trong vector edge_graph [node] sử dụng vòng lặp for.

• Gọi string_vowel (nó, nút) cho nút tiếp theo trong vectơ.

• Ở cuối tất cả các hàm, chúng ta sẽ có một nguyên âm là số nút có trọng số có nguyên âm trong đó.

Ví dụ

#include <bits/stdc++.h>
using namespace std;
vector<string> Node_Weight(100);
vector<int> edge_graph[100];
int vowel = 0;
bool check(string check_it){
   int length = check_it.length();
   for(int i = 0; i <length; i++){
      char c = tolower(check_it[i]);
      if(c == 'a' ||c == 'e' ||c == 'i' ||c == 'o' ||c == 'u'){
         return true;
      }
   }
   return false;
}
void string_vowel(int node, int root){
   string str = Node_Weight[node];
   if(check(str)){
      vowel++;
   }
   for (int it : edge_graph[node]){
      if(it == root){
         continue;
      }
      string_vowel(it, node);
   }
}
int main(){
   //weight of the nodes
   Node_Weight[2] = "ae";
   Node_Weight[1] = "bcd";
   Node_Weight[4] = "io";
   Node_Weight[3] = "gfe";
   Node_Weight[8] = "tptpa";
   Node_Weight[9] = "iou";
   //create graph edge
   edge_graph[2].push_back(1);
   edge_graph[2].push_back(4);
   edge_graph[4].push_back(3);
   edge_graph[4].push_back(8);
   edge_graph[8].push_back(9);
   string_vowel(2, 2);
   cout<<"Count the nodes of the tree whose weighted string contains a vowel are: "<<vowel;
   return 0;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

Count the nodes of the tree whose weighted string contains a vowel are: 5