ในกรณีของ Binary Tree ที่กำหนด ให้แปลงเป็น Binary Search Tree เพื่อให้โครงสร้างดั้งเดิมของ Binary Tree ไม่เสียหาย
โซลูชันนี้จะใช้ชุด C++ STL แทนโซลูชันที่ใช้อาร์เรย์
ตัวอย่าง
ตัวอย่างที่ 1
ป้อนข้อมูล
11 / \ 3 8 / \ 9 5
ผลผลิต
9 / \ 5 11 / \ 3 8
ตัวอย่างที่ 2
ป้อนข้อมูล
11 / \ 31 16 / \ 21 6
ผลผลิต
16 / \ 11 21 / \ 6 31
วิธีแก้ปัญหา
-
เราต้องคัดลอกรายการของไบนารีทรีในชุดในขณะที่ดำเนินการข้ามผ่าน สิ่งนี้กินเวลา O(n log n) โปรดทราบว่าการตั้งค่าใน C++ STL (ไลบรารีเทมเพลตมาตรฐาน) นั้นใช้งานโดยใช้แผนผังการค้นหาไบนารีแบบปรับสมดุลตนเอง เช่น ต้นไม้สีแดงดำ ต้นไม้ AVL เป็นต้น
-
ไม่จำเป็นต้องเรียงลำดับชุดเนื่องจากมีการใช้ชุดใน C ++ ในการสร้างแผนผังการค้นหาไบนารีที่ปรับสมดุลตนเองเนื่องจากการดำเนินการแต่ละอย่าง เช่น การแทรก การค้นหา การลบ ฯลฯ จะใช้เวลา O(log n)
-
ตอนนี้ เราสามารถคัดลอกองค์ประกอบของชุดทีละรายการได้อย่างง่ายดายตั้งแต่เริ่มต้นจนถึงต้นไม้ ขณะที่ดำเนินการข้ามผ่านต้นไม้แบบไม่เรียงลำดับ ควรใช้ความระมัดระวัง เช่น ในการคัดลอกแต่ละรายการของชุดตั้งแต่เริ่มต้น อันดับแรก ให้คัดลอกไปยังแผนผังในขณะที่ดำเนินการข้ามผ่านแบบไม่เรียงลำดับ จากนั้นจึงลบออกจากชุดด้วย
-
ในปัจจุบัน โซลูชันที่กล่าวถึงข้างต้นนั้นง่ายกว่าและนำไปใช้ได้ง่ายกว่าการแปลงทรีไบนารีเป็นทรีไบนารีเป็นแผนผังการค้นหาแบบไบนารีที่อธิบายไว้ที่นี่
มีการอธิบายโปรแกรมต่อไปนี้ เพื่อแปลงไบนารีทรีเป็นไบนารีการค้นหาทรี (BST) โดยใช้ชุด
ตัวอย่าง
/* CPP program for converting a Binary tree to BST implementing sets as containers. */
#include <bits/stdc++.h>
using namespace std;
struct Node1 {
int data;
struct Node1 *left, *right;
};
// function for storing the nodes in set while performing inorder traversal.
void storeinorderInSet(Node1* root1, set<int>& s){
if (!root1)
return;
// Left subtree is visited first
storeinorderInSet(root1->left, s);
Order of O(logn) for sets is taken by insertion
s.insert(root1->data);
// We visit the right subtree
storeinorderInSet(root1->right, s);
} // Time complexity = O(nlogn)
// function for copying elements of set one by one to the tree while performing inorder traversal
void setToBST(set<int>& s, Node1* root1){
// base condition
if (!root1) return;
// We first move to the left subtree and update elements
setToBST(s, root1->left);
// iterator initially pointing to the starting of set
auto it = s.begin();
// We copy the element at sarting of set(sorted) to the tree.
root1->data = *it;
// now we erase the starting element from set.
s.erase(it);
// now we move to right subtree and update elements
setToBST(s, root1->right);
}
// T(n) = O(nlogn) time
// We convert Binary tree to BST.
void binaryTreeToBST(Node1* root1){
set<int> s;
// We populate the set with the tree's inorder traversal data
storeinorderInSet(root1, s);
// At present sets are by default sorted as they are used
implementing self-balancing BST
// We copy elements from set to the tree while inorder traversal
which makes a BST
setToBST(s, root1);
}
// Time complexity = O(nlogn),
// Auxiliary Space = O(n) for set.
// helper function for creating a node
Node1* newNode(int data){
// dynamically allocating memory
Node1* temp = new Node1();
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// function for doing inorder traversal
void inorder(Node1* root1){
if (!root1)
return;
inorder(root1->left);
cout<< root1->data << " ";
inorder(root1->right);
}
int main(){
Node1* root1 = newNode(6);
root1->left = newNode(8);
root1->right = newNode(10);
root1->right->left = newNode(11);
root1->left->left = newNode(2);
root1->left->right = newNode(7);
root1->right->right = newNode(12);
/* Building tree given in the following figure
6
/ \
8 10
/\ / \
2 7 11 12 */
// We convert the above Binary tree to BST
binaryTreeToBST(root1);
cout<< "Inorder traversal of BST is: " << endl;
inorder(root1);
return 0;
} ผลลัพธ์
Inorder traversal of BST is: 1 5 6 7 9 10 11
ความซับซ้อนของเวลาแสดงเป็น :O(n Log n)
Auxiliary Space แสดงเป็น :(n)
