将二进制树转换为二进制搜索树的Java程序

1 简介

在此程序中，我们需要将给定的二叉树转换为相应的二叉树。如果每个节点最多具有两个子节点，则将一棵树称为二叉树。而二叉搜索树是二叉树的一种特殊情况，其中根节点左侧的所有节点都应小于根节点，而右侧节点则应大于根节点。

通过将给定的二叉树转换为其对应的数组表示形式，可以解决此问题。对数组进行排序。根据数组元素计算中间节点，因为它将成为相应的二进制搜索树的根节点。

2 算法思路

• 定义具有三个属性的Node类，即：左和右数据。在此，左代表节点的左子节点，右代表节点的右子节点。
• 创建节点时，数据将传递到该节点的data属性，并且左右都将设置为null。
• 定义另一个具有两个属性root和treeArray的类。
  • 根表示树的根节点，并将其初始化为null。
  • treeArray将存储二叉树的数组表示形式。
• 它将通过调用convertBTtoArray（）将二叉树转换为相应的数组。
• 从第1步开始对生成的数组进行升序排序。
• 通过调用createBST（）将数组转换为二进制搜索树。
• computeSize（）将计算树中存在的节点数。
• convertBTtoArray（）将通过遍历二叉树并将元素添加到treeArray来将二叉树转换为其数组表示形式。
• createBST（）将通过选择排序的treeArray的中间节点作为其根节点来创建相应的二进制搜索树。treeArray将分为两部分，即[0，mid-1]和[mid + 1，end]。从每个数组中递归地找到中间节点，分别创建左子树和右子树。
• Inorder（）将以有序方式显示树的节点，即左子节点，后跟根节点，右子节点。

3 程序实现

import java.util.Arrays;  
/**
 * 一点教程网： http://www.yiidian.com
 */
public class ConvertBTtoBST {  
  
    //Represent a node of binary tree  
    public static class Node{  
        int data;  
        Node left;  
        Node right;  
  
        public Node(int data){  
            //Assign data to the new node, set left and right children to null  
            this.data = data;  
            this.left = null;  
            this.right = null;  
            }  
        }  
  
    //Represent the root of binary tree  
    public Node root;  
  
    int[] treeArray;  
    int index = 0;  
  
    public ConvertBTtoBST(){  
        root = null;  
    }  
  
    //convertBTBST() will convert a binary tree to binary search tree  
    public Node convertBTBST(Node node) {  
  
        //Variable treeSize will hold size of tree  
        int treeSize = calculateSize(node);  
        treeArray = new int[treeSize];  
  
        //Converts binary tree to array  
        convertBTtoArray(node);  
  
          //Sort treeArray  
        Arrays.sort(treeArray);  
  
        //Converts array to binary search tree  
        Node d = createBST(0, treeArray.length -1);  
        return d;  
    }  
  
    //calculateSize() will calculate size of tree  
    public int calculateSize(Node node)  
    {  
        int size = 0;  
        if (node == null)  
         return 0;  
        else {  
            size = calculateSize (node.left) + calculateSize (node.right) + 1;  
            return size;  
        }  
    }  
  
    //convertBTtoArray() will convert the given binary tree to its corresponding array representation  
    public void convertBTtoArray(Node node) {  
        //Check whether tree is empty  
        if(root == null){  
            System.out.println("Tree is empty");  
            return;  
        }  
        else {  
            if(node.left != null)  
                convertBTtoArray(node.left);  
            //Adds nodes of binary tree to treeArray  
            treeArray[index] = node.data;  
            index++;  
            if(node.right != null)  
                convertBTtoArray(node.right);  
            }  
        }  
  
    //createBST() will convert array to binary search tree  
    public Node createBST(int start, int end) {  
  
        //It will avoid overflow  
        if (start > end) {  
            return null;  
        }  
  
        //Variable will store middle element of array and make it root of binary search tree  
        int mid = (start + end) / 2;  
        Node node = new Node(treeArray[mid]);  
  
        //Construct left subtree  
        node.left = createBST(start, mid - 1);  
  
        //Construct right subtree  
        node.right = createBST(mid + 1, end);  
  
        return node;  
    }  
  
    //inorder() will perform inorder traversal on binary search tree  
    public void inorderTraversal(Node node) {  
  
        //Check whether tree is empty  
        if(root == null){  
            System.out.println("Tree is empty");  
            return;  
           }  
        else {  
  
            if(node.left!= null)  
                inorderTraversal(node.left);  
            System.out.print(node.data + " ");  
            if(node.right!= null)  
                inorderTraversal(node.right);  
  
          }  
      }  
  
    public static void main(String[] args) {  
  
        ConvertBTtoBST bt = new ConvertBTtoBST();  
        //Add nodes to the binary tree  
        bt.root = new Node(1);  
        bt.root.left = new Node(2);  
        bt.root.right = new Node(3);  
        bt.root.left.left = new Node(4);  
        bt.root.left.right = new Node(5);  
        bt.root.right.left = new Node(6);  
        bt.root.right.right = new Node(7);  
  
        //Display given binary tree  
        System.out.println("Inorder representation of binary tree: ");  
        bt.inorderTraversal(bt.root);  
  
        //Converts binary tree to corresponding binary search tree  
        Node bst = bt.convertBTBST(bt.root);  
  
        //Display corresponding binary search tree  
        System.out.println("\nInorder representation of resulting binary search tree: ");  
        bt.inorderTraversal(bst);  
      }  
}  

输出结果为：

Inorder representation of binary tree: 
4 2 5 1 6 3 7 
Inorder representation of resulting binary search tree: 
1	2 3 4 5 6 7