# 使用STL集将二叉树转换为二叉搜索树

## 代码

### C ++代码使用Set将二进制树转换为BST

```#include <bits/stdc++.h>
using namespace std;

// defines the structure of a tree node
struct node{
int data;
node* left;
node* right;
};

// inserts the given tree elements into the set
void insertIntoSet(node* root, set<int> &treeSet){
if(root){
insertIntoSet(root->left, treeSet);
treeSet.insert(root->data);
insertIntoSet(root->right, treeSet);
}
}

// replace the elements of the initial tree
// with elements in treeSet in in-order fashion
void modifyBinaryTreeIntoBST(node* root, set<int> &treeSet)
{
if(root){
modifyBinaryTreeIntoBST(root->left, treeSet);
root->data = *(treeSet.begin());
treeSet.erase(treeSet.begin());
modifyBinaryTreeIntoBST(root->right, treeSet);
}
}

// Converts Binary tree to BST
void binaryTreeToBST(node* root)
{
set<int> treeSet;
// first fill the set
insertIntoSet(root, treeSet);
// then replace the elements in initial tree
modifyBinaryTreeIntoBST(root, treeSet);
}

// creates and returns a new node with supplied node value
node* create(int data){
node *tmp = new node();
tmp->data = data;
tmp->left = tmp->right = NULL;
return tmp;
}

// simple in-order traversal
void inorder(node *root){
if(root){
inorder(root->left);
cout<<root->data;
inorder(root->right);
}
}

int main()
{
// constructing a binary tree
// same as shown above
node *root = create(1);
root->right = create(2);
root->right->left = create(4);
root->right->left->left = create(5);
root->right->left->right = create(3);

cout<<"Inorder Traversal of given binary tree"<<endl;
inorder(root);cout<<endl;
binaryTreeToBST(root);
cout<<"Inorder Traversal of modified tree\n";
inorder(root);
}
```
```Inorder Traversal of given binary tree
15432
Inorder Traversal of modified tree
12345```

### Java代码使用Set将二进制树转换为BST

```import java.util.*;
import java.lang.*;
import java.io.*;

class node{
int data;
node left;
node right;
}

class Tree{
// creates and returns a new node with supplied node value
static node create(int data){
node tmp = new node();
tmp.data = data;
tmp.left = null;
tmp.right = null;
return tmp;
}

// inserts the given tree elements into the set
static void insertIntoSet(node root, TreeSet<Integer> treeSet){
if(root != null){
insertIntoSet(root.left, treeSet);
insertIntoSet(root.right, treeSet);
}
}

// replace the elements of the initial tree
// with elements in treeSet in in-order fashion
static void modifyBinaryTreeIntoBST(node root, TreeSet<Integer> treeSet)
{
if(root != null){
modifyBinaryTreeIntoBST(root.left, treeSet);
root.data = treeSet.pollFirst();
modifyBinaryTreeIntoBST(root.right, treeSet);
}
}

// Converts Binary tree to BST
static void binaryTreeToBST(node root)
{
TreeSet<Integer> treeSet = new TreeSet<>();
// first fill the set
insertIntoSet(root, treeSet);
// then replace the elements in initial tree
modifyBinaryTreeIntoBST(root, treeSet);
}

// simple in-order traversal
static void inorder(node root){
if(root != null){
inorder(root.left);
System.out.print(root.data);
inorder(root.right);
}
}

public static void main(String[] args)
{
// constructing a binary tree
// same as shown above
node root = create(1);
root.right = create(2);
root.right.left = create(4);
root.right.left.left = create(5);
root.right.left.right = create(3);

System.out.println("Inorder Traversal of given binary tree");
inorder(root);
System.out.println();
binaryTreeToBST(root);
System.out.println("Inorder Traversal of modified tree");
inorder(root);
}
}```
```Inorder Traversal of given binary tree
15432
Inorder Traversal of modified tree
12345```

## 复杂度分析

### 时间复杂度

O（N log N），  其中N是树中元素的数量。 在这里，对数因子是由于集合而产生的。 设置数据结构需要N倍的时间才能插入，搜索和删除元素。