# 二叉树到二叉搜索树的转换

## 算法

1. 创建一个名为inOrder的数组。
2. 以顺序形式遍历给定的二叉树，并将节点的值存储在数组“ inOrder”中。
3. 对数组进行排序。
4. 同时遍历数组和二叉树，并用inOrder数组中的值替换二叉树中相应节点的值。
5. 二叉树被转换为二叉搜索树。

## 说明

inOrder [] = {47，51，25，6，13，8}

inOrder = {6，8，13，25，47，51}

## 二叉树到二叉搜索树转换的JAVA代码

```import java.util.ArrayList;
import java.util.Collections;

public class BinaryTreeToBinarySearchTreeConversion {
// class representing Node of a Binary Tree
static class Node {
int data;
Node left, right;

public Node(int data) {
this.data = data;
}
}

// class to provide a wrapper around index
// so that we can pass it by reference
static class Index {
int index;

public Index(int index) {
this.index = index;
}
}

// function to print pre order traversal of a binary tree
private static void preOrder(Node root) {
if (root != null) {
System.out.print(root.data + " ");
preOrder(root.left);
preOrder(root.right);
}
}

// function to traverse in binary tree in in-order form and store the elements
// in a list
private static void inOrderAndFormList(Node root, ArrayList<Integer> inorder) {
if (root != null) {
inOrderAndFormList(root.left, inorder);
// store the current value in the list
inOrderAndFormList(root.right, inorder);
}
}

// function to traverse in binary tree in in-order form and
// change the value of elements accordingly
private static void inOrderAndChange(Node root, ArrayList<Integer> inOrder, Index index) {
if (root != null) {
inOrderAndChange(root.left, inOrder, index);
// change the current element of Tree with current element of list
root.data = inOrder.get(index.index);
// increment index by 1
index.index++;
inOrderAndChange(root.right, inOrder, index);
}
}

private static void convertToBST(Node root) {
// create a list and store the inorder of the given Binary Tree
ArrayList<Integer> inOrder = new ArrayList<>();
inOrderAndFormList(root, inOrder);

// Sort the list
Collections.sort(inOrder);

// traverse in binary tree and list simultaneously and change the required values
inOrderAndChange(root, inOrder, new Index(0));
}

public static void main(String[] args) {
// Example Tree
Node root = new Node(25);
root.left = new Node(51);
root.right = new Node(13);
root.left.left = new Node(47);
root.right.left = new Node(6);
root.right.right = new Node(8);

convertToBST(root);

preOrder(root);
System.out.println();
}
}```
`13 8 6 47 25 51`

## 二叉树到二叉搜索树转换的C ++代码

```#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// class representing Node of a Binary Tree
class Node {
public:
int data;
Node *left;
Node *right;

Node(int d) {
data = d;
}
};

// global variable index
int index = 0;

void preOrder(Node *root) {
if (root != NULL) {
cout<<root->data<<" ";
preOrder(root->left);
preOrder(root->right);
}
}

// function to traverse in binary tree in in-order form and store the elements
// in a list
void inOrderAndFormList(Node *root, vector<int> &inOrder) {
if (root != NULL) {
inOrderAndFormList(root->left, inOrder);
// store the current value in the list
inOrder.push_back(root->data);
inOrderAndFormList(root->right, inOrder);
}
}

// function to traverse in binary tree in in-order form and
// change the value of elements accordingly
void inOrderAndChange(Node *root, vector<int>& inOrder) {
if (root != NULL) {
inOrderAndChange(root->left, inOrder);

// change the current element of Tree with current element of list
root->data = inOrder[index];
index++;

inOrderAndChange(root->right, inOrder);
}
}

void convertToBST(Node *root) {
// create a list and store the inorder of the given Binary Tree
vector<int> inOrder;
inOrderAndFormList(root, inOrder);

// Sort the list
sort(inOrder.begin(), inOrder.end());

// traverse in binary tree and list simultaneously and change the required values
index = 0;
inOrderAndChange(root, inOrder);
}

int main() {
// Example Tree
Node *root = new Node(25);
root->left = new Node(51);
root->right = new Node(13);
root->left->left = new Node(47);
root->right->left = new Node(6);
root->right->right = new Node(8);

convertToBST(root);

preOrder(root);
cout<<endl;

return 0;
}```
`13 8 6 47 25 51`