สร้างต้นไม้ k-ary แบบเต็มจากการข้ามผ่านของการสั่งซื้อล่วงหน้าใน C++

เราได้รับอาร์เรย์ arr[] ที่มีการส่งผ่านคำสั่งล่วงหน้าของทรี k-ary ตามลำดับ เป้าหมายคือการสร้างต้น k-ary เดียวกันจากนั้นพิมพ์การข้ามผ่านรายการภายหลัง ต้นไม้ k−ary แบบเต็มคือต้นไม้ที่โหนดรูทมีลูก 0 หรือ k ลูก เช่น มากที่สุด k ลูก

ตัวอย่าง

อินพุต

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

ผลลัพธ์

ต้นไม้ k−ary เต็มรูปแบบซึ่งจะสร้างโดยเด็กสองคนจากการข้ามเส้นทางล่วงหน้าจะได้รับด้านล่าง -

คำอธิบาย

เราได้รับอาร์เรย์ของค่าจำนวนเต็มหรือการข้ามผ่านคำสั่งล่วงหน้าของ atree ที่มีลูก k ซึ่งก็คือ 2 ดังนั้น ต้นไม้ที่ก่อตัวขึ้นจะมีการข้ามผ่านภายหลังเป็น 3 6 1 2 1 7 5 2 ซึ่งสร้างขึ้นตามกฎที่ระบุว่า เยี่ยมชมโหนดทรีย่อย LEFT ทั้งหมด จากนั้นไปที่โหนดทรีย่อยขวาทั้งหมด จากนั้นไปที่โหนดรูททั้งหมด

อินพุต

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

ผลลัพธ์

ต้นไม้ k−ary เต็มรูปแบบซึ่งจะสร้างด้วยลูกสามคนจากการข้ามเส้นทางล่วงหน้าจะได้รับด้านล่าง -

คำอธิบาย

เราได้รับอาร์เรย์ของค่าจำนวนเต็มหรือการข้ามผ่านของคำสั่งล่วงหน้าของ atree ที่มีลูก k ซึ่งก็คือ 3 ดังนั้น ต้นไม้ที่ก่อตัวขึ้นจะมีการข้ามผ่านภายหลังเป็น 3 6 1 2 1 7 5 2 ซึ่งสร้างขึ้นตามกฎที่ระบุว่า เยี่ยมชมโหนดทรีย่อย LEFT ทั้งหมด จากนั้นไปที่โหนดทรีย่อยขวาทั้งหมด จากนั้นไปที่โหนดรูททั้งหมด

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

ในแนวทางนี้ ก่อนอื่นเราจะสร้าง k-ary tree จากอาร์เรย์ที่กำหนดโดยใช้องค์ประกอบแรกเป็นโหนดรูท หากทรีย่อยด้านซ้ายว่างเปล่า ทรีย่อยด้านขวาก็จะว่างเปล่าด้วย เรียกทรีย่อยซ้ายและขวาซ้ำแล้วซ้ำอีก สำหรับการข้ามผ่านคำสั่งภายหลัง เราใช้ทรีย่อยทางซ้าย จากนั้นทรีย่อยทางขวา จากนั้นพิมพ์น้ำหนักของโหนด

• โทรสั่ง (root−>left)

• โทรสั่ง (root->ขวา)

• พิมพ์ root->data

• ใช้ arr[] เป็นอาร์เรย์อินพุตที่มีการส่งผ่านคำสั่งล่วงหน้า

• ใช้ k เป็นเด็กตัวแปร

• ใช้ดัชนีเริ่มต้นเป็น count=0

• สร้างแผนผังโดยใช้ Tree_Node* node =create_tree(arr, size, children, count)

• ฟังก์ชัน new_Node(ข้อมูล int) สร้างโหนดใหม่ของต้นไม้

• ฟังก์ชัน create_tree(int arr[], int N, int k, int height, int&count) สร้าง kary tree จากอาร์เรย์ arr[].

• หากจำนวนโหนดเป็น <=0 ให้คืนค่า NULL จะไม่สามารถสร้างแผนผังได้

• เริ่มต้น newNode =new_Node(arr[count]) องค์ประกอบแรกของ arr[]

• ถ้า (newNode ==NULL) ให้ผลลัพธ์เป็น จริง จะไม่มีแผนผังใดเกิดขึ้นได้

• Traverse arr[] ใช้ for loop จาก i=0 ถึง i

• ถ้า (นับ 1) ให้เพิ่มจำนวนสำหรับดัชนีถัดไปและเพิ่มโหนดนี้ในทรีโดยใช้ newNode−>root.push_back(create_tree(arr, N, k, height − 1, count))

• มิฉะนั้นจะสิ้นสุดทรีด้วยการกด NULL โดยใช้ newNode−>root.push_back(NULL);

• ในตอนท้าย ให้คืนตัวชี้ไปที่โหนด

• ฟังก์ชัน create_tree(int* arr, int N, int k, int count) คืนค่าความสูงของต้นไม้

• คำนวณความสูง=(int)ceil(log((double)N * (k − 1) + 1) / log((double)k));

• เรียก create_tree(arr, N, k, height, count) ในคำสั่ง return สำหรับ tree ที่ความสูงคำนวณด้านบน

• ฟังก์ชัน postorder_traversal(โหนด Tree_Node*, int k) พิมพ์การสั่งซื้อล่วงหน้าของต้นไม้ k−ary ที่รูทที่โหนด

• หากโหนดเป็น NULL จะไม่ส่งคืนสิ่งใด

• สำรวจโดยใช้ for loop จาก i=0 ถึง iroot[i], k);

• พิมพ์ node->address ที่ส่วนท้ายของ for loop.

ตัวอย่าง

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

ผลลัพธ์

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

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