Trong trường hợp Cây nhị phân nhất định, hãy chuyển đổi nó thành Cây tìm kiếm nhị phân theo cách giữ nguyên cấu trúc ban đầu của Cây nhị phân.
Bộ C ++ STL sẽ được sử dụng bởi giải pháp này thay vì giải pháp dựa trên mảng.
Ví dụ
Ví dụ 1
Đầu vào
11 / \ 3 8 / \ 9 5
Đầu ra
9 / \ 5 11 / \ 3 8
Ví dụ 2
Đầu vào
11 / \ 31 16 / \ 21 6
Đầu ra
16 / \ 11 21 / \ 6 31
Giải pháp
-
Chúng ta phải sao chép các mục của cây nhị phân trong một tập hợp trong khi thực hiện chuyển ngang inorder. Điều này tiêu tốn O (n log n) thời gian. Lưu ý rằng bộ trong C ++ STL (Thư viện mẫu chuẩn) được triển khai bằng Cây tìm kiếm nhị phân tự cân bằng như Cây màu đen đỏ, Cây AVL, v.v.
-
Không cần sắp xếp tập hợp vì các tập hợp trong C ++ được sử dụng để triển khai cây tìm kiếm nhị phân Tự cân bằng do mỗi thao tác như chèn, tìm kiếm, xóa, v.v. tiêu tốn O (log n) thời gian.
-
Bây giờ, chúng ta có thể dễ dàng sao chép các phần tử của tập hợp lần lượt từ đầu đến cây trong khi thực hiện chuyển ngang qua cây nhỏ hơn. Cần cẩn thận vì khi sao chép từng mục của tập hợp từ đầu, trước tiên chúng tôi sao chép nó vào cây trong khi thực hiện duyệt qua trình đơn vị, sau đó cũng xóa nó khỏi tập hợp.
-
Hiện tại, giải pháp được đề cập ở trên đơn giản và dễ thực hiện hơn so với việc chuyển đổi dựa trên mảng của cây nhị phân thành cây tìm kiếm nhị phân được giải thích tại đây.
Chương trình sau để chuyển đổi cây nhị phân sang cây tìm kiếm nhị phân (BST) bằng cách sử dụng set, được giải thích ở đây.
Ví dụ
/* 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;
} Đầu ra
Inorder traversal of BST is: 1 5 6 7 9 10 11
Độ phức tạp về thời gian được biểu thị là:O (n Log n)
Không gian Phụ trợ được ký hiệu là:(n)