資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用 STL set 在 C++ 中將二叉樹轉換為二叉搜尋樹？
對於給定的二叉樹，將其轉換為二叉搜尋樹，同時保持二叉樹的原始結構不變。
此解決方案將使用 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)
輔助空間表示為：(n)
更新於： 2020 年 1 月 29 日
586 次瀏覽
廣告