Computer >> Máy Tính >  >> Lập trình >> C ++

Xây dựng cây k-ary đầy đủ từ trình duyệt được đặt hàng trước của nó trong C ++

Chúng ta được cung cấp một mảng arr [] có chứa trình tự duyệt của cây k-ary theo thứ tự. Mục đích là xây dựng cùng một cây k-ary từ nó và in ra trình duyệt sau của nó. Cây k-ary đầy đủ là cây trong đó nút gốc có 0 hoặc k con, tức là nhiều nhất k con.

Ví dụ

Đầu vào 

int arr[] = {2, 5, 1, 3, 6, 7, 2, 1 }, int size = 8, int children = 2

Đầu ra

Dưới đây là một cây đầy đủ sẽ được xây dựng với hai đứa trẻ đi ngang qua băng giá lạnh -

Xây dựng cây k-ary đầy đủ từ trình duyệt được đặt hàng trước của nó trong C ++

Giải thích

chúng ta được cung cấp với một mảng các giá trị số nguyên hoặc truyền tải thứ tự trước của atree với k con là 2. Vì vậy, cây được tạo thành sẽ có truyền tải thứ tự sau là 3 6 1 2 1 7 5 2 được xây dựng theo quy tắc cho biết truy cập tất cả các nút Cây con TRÁI, sau đó truy cập tất cả các nút Cây con RIGHT và sau đó truy cập tất cả các nút ROOT.

Đầu vào 

int arr[] = {2, 5, 1, 3, 6, 7, 2, 1 }, int size = 8, int children = 3

Đầu ra

Dưới đây là một cây k-ary đầy đủ sẽ được xây dựng với ba đứa trẻ đi ngang qua băng giá -

Xây dựng cây k-ary đầy đủ từ trình duyệt được đặt hàng trước của nó trong C ++

Giải thích

chúng ta được cung cấp với một mảng các giá trị số nguyên hoặc truyền tải thứ tự trước của atree với k con là 3. Vì vậy, cây được hình thành sẽ có truyền tải thứ tự sau là 3 6 1 2 1 7 5 2 được xây dựng theo quy tắc cho biết truy cập tất cả các nút Cây con TRÁI, sau đó truy cập tất cả các nút Cây con RIGHT và sau đó truy cập tất cả các nút ROOT.

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, đầu tiên chúng ta sẽ xây dựng cây k-ary từ mảng đã cho, lấy phần tử đầu tiên làm nút gốc. Nếu cây con bên trái trống thì cây bên phải cũng sẽ trống. Gọi đệ quy cho các cây con bên trái và bên phải và liên kết chúng.

  • Gọi cho người đăng ký (root−> left)

  • Gọi cho người đăng ký (root−> right)

  • In root−> dữ liệu

  • Lấy arr [] làm mảng đầu vào chứa truyền tải đặt hàng trước.

  • Lấy k là biến con.

  • Lấy chỉ số bắt đầu là count =0.

  • Xây dựng cây bằng cách sử dụng Tree_Node * node =create_tree (arr, size, children, count).

  • Hàm new_Node (dữ liệu int) tạo một nút mới của cây.

  • Hàm create_tree (int arr [], int N, int k, int height, int &count) tạo cây kary từ mảng arr [].

  • Nếu số lượng nút là <=0 thì trả về NULL, không có cây nào có thể được xây dựng.

  • Khởi tạo newNode =new_Node (arr [count]), phần tử đầu tiên của arr [].

  • Nếu (newNode ==NULL) cho kết quả true thì không thể có cây.

  • Traverse arr [] sử dụng vòng lặp for từ i =0 đến i

  • Nếu (count 1) thì số gia tăng cho chỉ mục tiếp theo và thêm nút này vào cây bằng cách sử dụng newNode−> root.push_back (create_tree (arr, N, k, height - 1, count)).

  • Nếu không, hãy kết thúc cây bằng cách đẩy NULL bằng newNode−> root.push_back (NULL);

  • Cuối cùng, trả lại con trỏ cho nút.

  • Hàm create_tree (int * arr, int N, int k, int count) trả về chiều cao của cây.

  • Tính chiều cao =(int) ceil (log ((double) N * (k - 1) + 1) / log ((double) k));

  • Gọi create_tree (arr, N, k, height, count) trong câu lệnh trả về cho cây ở height được tính toán ở trên.

  • Hàm postorder_traversal (Tree_Node * node, int k) in ra giao dịch trước của cây k-ary bắt nguồn từ nút.

  • Nếu nút là NULL thì không trả về gì.

  • Đảo ngược bằng cách sử dụng vòng lặp for từ i =0 đến i root [i], k);

  • In địa chỉ nút−> ở cuối vòng lặp for.

Ví dụ 

#include <bits/stdc++.h>
using namespace std;
struct Tree_Node{
   int address;
   vector<Tree_Node*> root;
};
Tree_Node* new_Node(int data){
   Tree_Node* newNode = new Tree_Node;
   newNode−>address = data;
   return newNode;
}
Tree_Node* create_tree(int arr[], int N, int k, int height, int& count){
   if(N <= 0){
      return NULL;
   }
   Tree_Node* newNode = new_Node(arr[count]);
   if (newNode == NULL){
      cout<<"Code Dumped";
      return NULL;
   }
   for(int i = 0; i < k; i++){
      if (count < N − 1 && height > 1){
         count++;
         newNode−>root.push_back(create_tree(arr, N, k, height − 1, count));
      }else{
         newNode−>root.push_back(NULL);
      }
   }
   return newNode;
}
Tree_Node* create_tree(int* arr, int N, int k, int count){
   int height = (int)ceil(log((double)N * (k − 1) + 1) / log((double)k));
   return create_tree(arr, N, k, height, count);
}
void preorder_traversal(Tree_Node* node, int k){
   if (node == NULL){
      return;
   }
   for(int i = 0; i < k; i++){
      preorder_traversal(node−>root[i], k);
   }
   cout<<node−>address<< " ";
}
int main(){
   int arr[] = {2, 5, 1, 3, 6, 7, 2, 1 };
   int size = 8;
   int children = 2;
   int count = 0;
   Tree_Node* node = create_tree(arr, size, children, count);
   cout<<"Construct the full k−ary tree from its preorder traversal are: ";
   preorder_traversal(node, children);
   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 - 

Construct the full k-ary tree from its preorder traversal are: 3 6 1 2 1 7 5 2