Binary Tree เป็น Binary Search Tree Conversion ใน C ++

A ต้นไม้ไบนารี เป็นต้นไม้ชนิดพิเศษที่แต่ละโหนดของต้นไม้สามารถมีโหนดย่อยได้ไม่เกินสองโหนด โหนดย่อยเหล่านี้เรียกว่าลูกด้านขวาและลูกด้านซ้าย

ต้นไม้ไบนารีอย่างง่ายคือ −

โครงสร้างการค้นหาแบบไบนารี (BST) เป็นต้นไม้ชนิดพิเศษซึ่งเป็นไปตามกฎต่อไปนี้ −

• ค่าโหนดลูกด้านซ้ายจะน้อยกว่าหมายเหตุหลักเสมอ

• โหนดย่อยที่ถูกต้องมีค่ามากกว่าโหนดหลัก

• โหนดทั้งหมดจะสร้างแผนผังการค้นหาแบบไบนารีแยกกัน

ตัวอย่างแผนผังการค้นหาแบบไบนารี (BST) −

โครงสร้างการค้นหาแบบไบนารีถูกสร้างขึ้นเพื่อลดความซับซ้อนของการดำเนินการ เช่น การค้นหา ค้นหาค่าต่ำสุดและสูงสุด

ที่นี่เราได้รับไบนารีทรีและเราต้องแปลงไบนารีทรี (BT) ไปยังแผนผังการค้นหาไบนารี (BST) . ในการแปลงนี้ ไม่ควรเปลี่ยนโครงสร้างดั้งเดิมของไบนารีทรี

มาดูตัวอย่างเพื่อทำความเข้าใจวิธีแปลง BT เป็น BST −

ป้อนข้อมูล −

ผลผลิต −

การแปลงไบนารีทรีเป็นทรีการค้นหาไบนารีนี้เกิดขึ้นโดยใช้สามขั้นตอน พวกมันคือ −

ขั้นตอนที่ 1 − จัดเก็บข้อมูลโดยลำดับการข้ามผ่านต้นไม้ไบนารีลงในอาร์เรย์ arr[] .

ขั้นตอนที่ 2 - จัดเรียงอาร์เรย์ arr[] โดยใช้เทคนิคการจัดเรียงแบบใดก็ได้

ขั้นตอนที่ 3 − ตอนนี้ ทำการสำรวจแบบไม่เรียงลำดับของต้นไม้ และคัดลอกองค์ประกอบของอาร์เรย์ไปยังโหนดของต้นไม้ทีละรายการ

ตัวอย่าง

#include<stdio.h>
#include<stdlib.h>
struct node{
   int data;
   struct node *left;
   struct node *right;
};
void Inordertraversal(struct node* node, int inorder[], int *index_ptr){
   if (node == NULL)
      return;
   Inordertraversal(node->left, inorder, index_ptr);
   inorder[*index_ptr] = node->data;
   (*index_ptr)++;
   Inordertraversal(node->right, inorder, index_ptr);
}
int countNodes(struct node* root){
   if (root == NULL)
      return 0;
   return countNodes (root->left) +
   countNodes (root->right) + 1;
}
int compare (const void * a, const void * b){
   return( *(int*)a - *(int*)b );
}
void arrayToBST (int *arr, struct node* root, int *index_ptr){
   if (root == NULL)
      return;
   arrayToBST (arr, root->left, index_ptr);
   root->data = arr[*index_ptr];
   (*index_ptr)++;
   arrayToBST (arr, root->right, index_ptr);
}
struct node* newNode (int data){
   struct node *temp = new struct node;
   temp->data = data;
   temp->left = NULL;
   temp->right = NULL;
   return temp;
}
void printInorder (struct node* node){
   if (node == NULL)
      return;
   printInorder (node->left);
   printf("%d ", node->data);
   printInorder (node->right);
}
int main(){
   struct node *root = NULL;
   root = newNode(17);
   root->left = newNode(14);
   root->right = newNode(2);
   root->left->left = newNode(11);
   root->right->right = newNode(7);
   printf("Inorder Traversal of the binary Tree: \n");
   printInorder (root);
   int n = countNodes(root);
   int *arr = new int[n];
   int i = 0;
   Inordertraversal(root, arr, &i);
   qsort(arr, n, sizeof(arr[0]), compare);
   i = 0;
   arrayToBST (arr, root, &i);
   delete [] arr;
   printf("\nInorder Traversal of the converted BST: \n");
   printInorder (root);
   return 0;
}

ผลลัพธ์

Inorder Traversal of the binary Tree:
11 14 17 2 7
Inorder Traversal of the converted BST:
2 7 11 14 17