สร้าง Binary Tree พิเศษจาก Inorder traversal ใน C++

เราได้รับอาร์เรย์ arr[] ที่มีการข้ามผ่านที่ไม่เป็นระเบียบของไบนารีทรี เป้าหมายคือการสร้างไบนารีทรีพิเศษจากอาร์เรย์นั้น ต้นไม้ไบนารีพิเศษคือต้นไม้ที่มีน้ำหนักของโหนดรูทมากกว่าน้ำหนักของลูกทั้งซ้ายและขวา

ตัวอย่าง

อินพุต

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

ผลลัพธ์

ไบนารีทรีพิเศษซึ่งจะถูกสร้างด้วยอินเดอร์ทราเวอร์แซลที่ให้ไว้ด้านล่าง -

คำอธิบาย

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

อินพุต

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

ผลลัพธ์

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

คำอธิบาย

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.

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้ −

ในแนวทางนี้ เราจะสร้างไบนารีทรีพิเศษจากอาร์เรย์ที่กำหนดโดยใช้องค์ประกอบสูงสุดเป็นโหนดรูท องค์ประกอบด้านซ้ายที่จะกลายเป็นส่วนหนึ่งของทรีย่อยทางซ้าย และองค์ประกอบด้านขวาที่จะกลายเป็นส่วนหนึ่งของแผนผังย่อยด้านขวา กระบวนการนี้ดำเนินการซ้ำๆ เพื่อสร้างแผนผัง

• ใช้ arr[] เป็นอาร์เรย์อินพุตที่มีการข้ามผ่านแบบไม่เรียงลำดับ

• ฟังก์ชัน new_node (ข้อมูล int) สร้างโหนดที่มีลูกซ้ายและขวาเป็น NULL

• ฟังก์ชั่น total(int arr[], int first, int last) คืนค่าดัชนีขององค์ประกอบนั้น

• ใช้สูงสุด =arr[แรก] และต่ำสุด =ก่อน

• สำรวจจากดัชนี +1 แรกจนถึงรายการสุดท้าย และหากพบว่าองค์ประกอบใด arr[i] มีค่ามากกว่าค่าสูงสุด ให้เก็บดัชนีไว้ที่ระดับต่ำสุดและอัปเดตสูงสุด

• ในตอนท้ายของ for loop ต่ำสุดจะมีดัชนีขององค์ประกอบสูงสุด

• ฟังก์ชัน create_tree (int arr[], int first, int last) สร้างไบนารีทรีพิเศษจาก arr[] แบบเรียกซ้ำ

• ถ้าก่อน>สุดท้ายก็คืนค่า NULL เนื่องจากต้นไม้จะไม่สามารถทำได้

• ใช้ temp เป็นค่าสูงสุดของอาร์เรย์โดยใช้ temp =total(arr, first, last)

• สร้างโหนดที่มี temp เป็นข้อมูล และทำให้พาเรนต์พอยน์เตอร์ชี้ไปที่โหนดนั้นสำหรับโหนดรูทของทรี

• ถ้า first==last ต้นไม้จะมีเพียงโหนดเดียว ส่งคืนพาเรนต์

• คำนวณซ้ำ parent->left =create_tree(arr, first, temp − 1);

• และ parent->right =create_tree(arr, temp + 1, last)

• ในตอนท้ายให้ส่งคืนพาเรนต์

• ฟังก์ชัน Inorder_traversal(tree_node* node) พิมพ์การข้ามผ่านของต้นไม้ที่สร้างขึ้นด้านบน

• หากโหนดเป็น NULL จะไม่ส่งคืนสิ่งใด พิมพ์ทรีย่อยทางซ้ายก่อนโดยใช้ Inorder_traversal(node−>left)

• จากนั้นพิมพ์โหนดปัจจุบัน

• จากนั้นพิมพ์แผนผังย่อยที่ถูกต้องโดยใช้ Inorder_traversal (node->right)

ตัวอย่าง

#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;
}

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -

Construct Special Binary Tree from given Inorder traversal are:
10, 20, 28, 40, 32, 31, 30