Tạo cây nhị phân đặc biệt từ truyền tải Inorder cho trước trong C ++

Chúng tôi được cung cấp một mảng arr [] chứa truyền tải cấp độ của một cây nhị phân. Mục đích là để xây dựng một cây nhị phân đặc biệt từ mảng đó. Cây nhị phân đặc biệt là cây có trọng số của nút gốc lớn hơn trọng số của cả cây con trái và phải của nó.

Ví dụ

Đầu vào

int arr[] = {10, 20, 28, 40, 32, 31, 30}

Đầu ra

Cây nhị phân đặc biệt sẽ được xây dựng với inordertraversal đã cho được đưa ra bên dưới -

Giải thích

we are given with an array of integer values or the inorder traversal of a tree. So, the special tree formed is 10, 20, 28, 40, 32, 31, 30

Đầu vào

int arr[] = {10, 20, 25, 28, 40, 32, 31, 30, 35}

Đầu ra

The special binary tree which will be constructed with the given inorder
traversal is given below −

Giải thích

we are given with an array of integer values or the inorder traversal of a tree. So, the special tree formed is 10, 20, 25, 28, 40, 32, 31, 30, 35.

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 ta sẽ xây dựng cây nhị phân đặc biệt từ mảng đã cho, lấy phần tử lớn nhất làm nút gốc. Các phần tử bên trái sẽ trở thành một phần của cây con bên trái và các phần tử bên phải sẽ trở thành một phần của cây con bên phải. Quá trình này được thực hiện đệ quy để xây dựng cây.

• Lấy arr [] làm mảng đầu vào có chứa trình duyệt inorder.

• Hàm new_node (int data) tạo một nút có nút con bên trái và bên phải là NULL.

• Hàm total (int arr [], int first, int last) trả về chỉ số của phần tử đó.

• Lấy cao nhất =arr [đầu tiên] và thấp nhất =đầu tiên.

• Duyệt từ chỉ mục +1 đầu tiên cho đến chỉ mục cuối cùng và nếu tìm thấy bất kỳ phần tử nào arr [i] nhiều hơn mức cao nhất thì hãy lưu chỉ mục của nó ở mức thấp nhất và cập nhật cao nhất.

• Ở cuối vòng lặp for thấp nhất sẽ chứa chỉ mục của phần tử cao nhất.

• Hàm create_tree (int arr [], int first, int last) xây dựng cây nhị phân đặc biệt từ arr [] một cách đệ quy.

• Nếu đầu tiên> cuối cùng thì trả về NULL vì cây sẽ không thể thực hiện được.

• Lấy tạm thời là giá trị lớn nhất của mảng bằng cách sử dụng temp =total (arr, first, last).

• Tạo một nút với dữ liệu tạm thời và tạo một con trỏ cha trỏ tới nó cho nút gốc của cây.

• Nếu đầu tiên ==cuối cùng thì cây sẽ chỉ có một nút. Trả lại phụ huynh.

• Tính toán đệ quy cha-> left =create_tree (arr, first, temp - 1);

• Và cha−> right =create_tree (arr, temp + 1, last).

• Cuối cùng, hãy trả lại giá trị gốc.

• Hàm Inorder_traversal (tree_node * node) in truyền qua inorder của cái được tạo ở trên.

• Nếu nút là NULL thì không trả về gì. Khác in cây con bên trái trước khi sử dụng Inorder_traversal (node−> left).

• Sau đó in nút hiện tại.

• Sau đó in cây con bên phải bằng Inorder_traversal (node−> right).

Ví dụ

#include <bits/stdc++.h>
using namespace std;
int total(int arr[], int first, int last);
class tree_node{
   public:
   int data;
   tree_node* left;
   tree_node* right;
};
tree_node* new_node(int data);
tree_node* create_tree (int arr[], int first, int last){
   if(first > last){
      return NULL;
   }
   int temp = total(arr, first, last);
   tree_node *parent = new_node(arr[temp]);
   if(first == last){
      return parent;
   }
   parent−>left = create_tree(arr, first, temp − 1);
   parent−>right = create_tree(arr, temp + 1, last);
   return parent;
}
int total(int arr[], int first, int last){
   int highest = arr[first];
   int lowest = first;
   for(int i = first + 1; i <= last; i++){
      if(arr[i] > highest){
         highest = arr[i];
         lowest = i;
      }
   }
   return lowest;
}
tree_node* new_node (int data){
   tree_node* newNode = new tree_node();
   newNode−>data = data;
   newNode−>left = NULL;
   newNode−>right = NULL;
   return newNode;
}
void Inorder_traversal(tree_node* node){
   if (node == NULL){
      return;
   }
   Inorder_traversal(node−>left);
   cout<<node−>data<<" ";
   Inorder_traversal (node−>right);
}
int main(){
   int arr[] = {10, 20, 28, 40, 32, 31, 30};
   int size = sizeof(arr)/sizeof(arr[0]);
   tree_node *root = create_tree(arr, 0, size − 1);
   cout<<"Construct Special Binary Tree from given Inorder traversal are: "<<"\n";
   Inorder_traversal(root);
   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 Special Binary Tree from given Inorder traversal are:
10, 20, 28, 40, 32, 31, 30