问：将二叉树转换为二叉搜索树的程序。

2025年3月17日 | 阅读 10 分钟

说明

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

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

Program to convert Binary Tree to Binary Search Tree

算法

定义 Node 类，该类包含三个属性：data、left 和 right。这里，left 表示节点的左子节点，right 表示节点的右子节点。
创建节点时，数据将传递到节点的 data 属性，left 和 right 都将设置为 null。
定义另一个具有两个属性 root 和 treeArray 的类。
1. Root 表示树的根节点，并将其初始化为 null。
2. treeArray 将存储二叉树的数组表示。
convertBTBST() 将把二叉树转换为相应的二叉搜索树
1. 它将通过调用 convertBTtoArray() 将二叉树转换为相应的数组。
2. 按升序对步骤 1 生成的数组进行排序。
3. 通过调用 createBST() 将数组转换为二叉搜索树。
calculateSize() 将计算树中的节点数。
convertBTtoArray() 将通过遍历树并将元素添加到 treeArray 中，将二叉树转换为其数组表示。
createBST() 将通过选择排序的 treeArray 的中间节点作为根节点来创建相应的二叉搜索树。treeArray 将被分成两部分，即 [0, mid-1] 和 [mid+1, end]。递归地从每个数组中查找中间节点，以分别创建左子树和右子树。
Inorder() 将以中序方式显示树的节点，即左子节点后跟根节点，然后是右子节点。

解决方案

Python

#Represent a node of binary tree
class Node:
    def __init__(self,data):
        #Assign data to the new node, set left and right children to None
        self.data = data;
        self.left = None;
        self.right = None;
 
class ConvertBTtoBST:
    def __init__(self):
        #Represent the root of binary tree
        self.root = None;
        self.treeArray = [];
        
    #convertBTBST() will convert a binary tree to the binary search tree
    def convertBTBST(self, node):
        
        #Converts binary tree to array
        self.convertBTtoArray(node);
        
        #Sort treeArray
        self.treeArray.sort();
        
        #Converts array to binary search tree
        d = self.createBST(0, len(self.treeArray) -1);
        return d;
        
    #convertBTtoArray() will convert the given binary tree to its corresponding array representation
    def convertBTtoArray(self, node):
        
        #Check whether tree is empty
        if(self.root == None):
            print("Tree is empty\n");
            return;
        else:
            if(node.left!= None):
                self.convertBTtoArray(node.left);
            #Adds nodes of binary tree to treeArray
            self.treeArray.append(node.data); 
 
            if(node.right!= None):
                self.convertBTtoArray(node.right);
                
    #createBST() will convert array to binary search tree
    def createBST(self, start, end):
        
        #It will avoid overflow
        if(start > end):
            return None;
            
        #Variable will store middle element of array and make it root of binary search tree
        mid = (start + end) // 2;
        node = Node(self.treeArray[mid]);
        
        #Construct left subtree
        node.left = self.createBST(start, mid - 1);
        
        #Construct right subtree
        node.right = self.createBST(mid + 1, end);
        
        return node;
        
    #inorder() will perform inorder traversal on binary search tree
    def inorderTraversal(self, node):
        
        #Check whether tree is empty
        if(self.root == None):
            print("Tree is empty\n");
            return;
        else:
            if(node.left != None):
                self.inorderTraversal(node.left);
            print(node.data),
            if(node.right!= None):
                self.inorderTraversal(node.right);
                
bt = ConvertBTtoBST();
#Add nodes to the binary tree
bt.root = Node(1);
bt.root.left = Node(2);
bt.root.right = Node(3);
bt.root.left.left = Node(4);
bt.root.left.right = Node(5);
bt.root.right.left = Node(6);
bt.root.right.right = Node(7);
 
#Display given binary tree
print("Inorder representation of binary tree: ");
bt.inorderTraversal(bt.root);
 
#Converts binary tree to corresponding binary search tree
bst = bt.convertBTBST(bt.root);
 
#Display corresponding binary search tree
print("\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

C

#include <stdio.h>
#include <stdlib.h>
 
//Represent a node of binary tree
struct node{
    int data;
    struct node *left;
    struct node *right;
};
 
//Represent the root of binary tree
struct node *root = NULL;
 
int treeArray[100];
int ind = 0;
    
//createNode() will create a new node
struct node* createNode(int data){
    //Create a new node
    struct node *newNode = (struct node*)malloc(sizeof(struct node));
    //Assign data to newNode, set left and right children to NULL
    newNode->data= data;
    newNode->left = NULL;
    newNode->right = NULL;
    
    return newNode;
}
 
//calculateSize() will calculate size of tree
int calculateSize(struct 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
void convertBTtoArray(struct node *node) {
    //Check whether tree is empty
    if(root == NULL){
        printf("Tree is empty\n");
        return;
    }
    else {
        if(node->left != NULL)
            convertBTtoArray(node->left);
        //Adds nodes of binary tree to treeArray
        treeArray[ind] = node->data; 
        ind++;
        if(node->right!= NULL)
            convertBTtoArray(node->right);  
        }      
}
 
//createBST() will convert array to binary search tree
struct 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;
    struct node *temp = createNode(treeArray[mid]);
 
    //Construct left subtree
    temp->left = createBST(start, mid - 1);
 
    //Construct right subtree
    temp->right = createBST(mid + 1, end);
 
    return temp;
}
 
//convertBTBST() will convert a binary tree to binary search tree
struct node* convertBTBST(struct node *node) {
    
    //Variable treeSize will hold size of tree
    int treeSize = calculateSize(node);
    
    //Converts binary tree to array
    convertBTtoArray(node);
    
    //Sort treeArray
    int compare (const void * a, const void * b) {
        return ( *(int*)a - *(int*)b );
    }
    qsort(treeArray, treeSize, sizeof(int), compare);
    
    //Converts array to binary search tree
    struct node *d = createBST(0, treeSize - 1);
    return d;
}
 
//inorder() will perform inorder traversal on binary search tree
void inorderTraversal(struct node *node) {
    
    //Check whether tree is empty
    if(root == NULL){
        printf("Tree is empty\n");
        return;
       }
    else {
        
        if(node->left!= NULL)
            inorderTraversal(node->left);
        printf("%d ", node->data);
        if(node->right!= NULL)
            inorderTraversal(node->right);
    }      
}
      
int main()
{
    //Add nodes to the binary tree
    root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);
    root->right->right = createNode(7);
    
    //Display given binary tree
    printf("Inorder representation of binary tree: \n");
    inorderTraversal(root);
    
    //Converts binary tree to corresponding binary search tree
    struct node *bst = convertBTBST(root);
    
    //Display corresponding binary search tree
    printf("\nInorder representation of resulting binary search tree: \n");
    inorderTraversal(bst);
 
    return 0;
}

输出

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

JAVA

import java.util.Arrays;
 
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

C#

using System;
namespace Tree 
{                     
    public class Program
    {
        //Represent a node of binary tree
        public class Node<T>{
            public T data;
            public Node<T> left;
            public Node<T> right;
            
            public Node(T data) {
                //Assign data to the new node, set left and right children to null
                this.data = data;
                this.left = null;
                this.right = null;
            }
        }
        
        public class ConvertBTtoBST<T>{
            //Represent the root of binary tree
            public Node<T> root;
            
            T[] treeArray;
            int index = 0;
            
            public ConvertBTtoBST(){
                root = null;
            }
        
            //convertBTBST() will convert a binary tree to binary search tree
            public Node<T> convertBTBST(Node<T> node) {
 
                //Variable treeSize will hold size of tree
                int treeSize = calculateSize(node);
                treeArray = new T[treeSize];
 
                //Converts binary tree to array
                convertBTtoArray(node);
 
                //Sort treeArray
                Array.Sort(treeArray);
 
                //Converts array to binary search tree
                Node<T> d = createBST(0, treeArray.Length -1);
                return d;
            }
    
            //calculateSize() will calculate size of tree
            int calculateSize(Node<T> 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<T> node) {
                //Check whether tree is empty
                if(root == null){
                    Console.WriteLine("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<T> 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<T> node = new Node<T>(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<T> node) {
 
                    //Check whether tree is empty
                    if(root == null){
                        Console.WriteLine("Tree is empty");
                        return;
                       }
                    else {
 
                        if(node.left!= null)
                            inorderTraversal(node.left);
                        Console.Write(node.data + " ");
                        if(node.right!= null)
                            inorderTraversal(node.right);
 
                      }      
                  }
        }
        
        public static void Main()
        {
            ConvertBTtoBST<int> bt = new ConvertBTtoBST<int>();
        
            //Add nodes to the binary tree
            bt.root = new Node<int>(1);
            bt.root.left = new Node<int>(2);
            bt.root.right = new Node<int>(3);
            bt.root.left.left = new Node<int>(4);
            bt.root.left.right = new Node<int>(5);
            bt.root.right.left = new Node<int>(6);
            bt.root.right.right = new Node<int>(7);
 
            //Display given binary tree
            Console.WriteLine("Inorder representation of binary tree: ");
            bt.inorderTraversal(bt.root);
 
            //Converts binary tree to corresponding binary search tree
            Node<int> bst = bt.convertBTBST(bt.root);
 
            //Display corresponding binary search tree
            Console.WriteLine("\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

PHP

<!DOCTYPE html>
<html>
<body>
<?php
//Represent a node of binary tree
class Node{
    public $data;
    public $left;
    public $right;
    
    function __construct($data){
        //Assign data to the new node, set left and right children to NULL
        $this->data = $data;
        $this->left = NULL;
        $this->right = NULL;
    }
}
class ConvertBTtoBST{
    //Represent the root of binary tree
    public $root;
    public $treeArray;
    public $index;
    function __construct(){
        $this->root = NULL;
        $this->treeArray = array();
        $this->index = 0;
    }
    
    //convertBTBST() will convert a binary tree to binary search tree
    function convertBTBST($node) {
        
        //Converts binary tree to array
        $this->convertBTtoArray($node);
        
          //Sort treeArray
        sort($this->treeArray);
      
        //Converts array to binary search tree
        $d = $this->createBST(0, count($this->treeArray) -1);
        return $d;
    }
    
    //convertBTtoArray() will convert the given binary tree to its corresponding array representation
    function convertBTtoArray($node) {
        //Check whether tree is empty
        if($this->root == null){
            print("Tree is empty <br>");
            return;
        }
        else {
            if($node->left != NULL)
                $this->convertBTtoArray($node->left);
            //Adds nodes of binary tree to treeArray
            $this->treeArray[$this->index] = $node->data; 
            $this->index++;
            if($node->right != NULL)
                $this->convertBTtoArray($node->right);  
            }      
        }
    
    //createBST() will convert array to binary search tree
    function createBST($start, $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
        $mid = ($start + $end) / 2;
        $node = new Node($this->treeArray[$mid]);
 
        //Construct left subtree
        $node->left = $this->createBST($start, $mid - 1);
 
        //Construct right subtree
        $node->right = $this->createBST($mid + 1, $end);
 
        return $node;
    }
    
    //inorder() will perform inorder traversal on binary search tree
    function inorderTraversal($node) {
        
        //Check whether tree is empty
        if($this->root == NULL){
            print("Tree is empty <br>");
            return;
           }
        else {
            
            if($node->left!= NULL)
                $this->inorderTraversal($node->left);
            print("$node->data ");
            if($node->right!= NULL)
                $this->inorderTraversal($node->right);
              
          }      
      }
}
$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
print("Inorder representation of binary tree: <br>");
$bt->inorderTraversal($bt->root);
 
//Converts binary tree to corresponding binary search tree
$bst = $bt->convertBTBST($bt->root);
 
//Display corresponding binary search tree
print("<br> Inorder representation of resulting binary search tree: <br>");
$bt->inorderTraversal($bst);      
?>
</body>
</html>

输出

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

下一个主题程序列表

问：将二叉树转换为二叉搜索树的程序。

说明

算法

解决方案

Python

C

JAVA

C#

PHP

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

程序

问：将二叉树转换为二叉搜索树的程序。

说明

算法

解决方案

Python

C

JAVA

C#

PHP

相关帖子

打印数字图案 6 的程序

将英尺转换为厘米的程序

打印图案 7 的程序

打印数组中重复元素的程序

查找半圆面积和周长的程序

查找字符串的所有可能子集的程序

计算两个矩阵乘积的程序

检查哈沙德数（Harshad number）的程序

打印数字图案 8 的程序

计算字符串中所有标点符号字符数量的程序

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器