java - 如何使用数组(在 Java 中)平衡现有的随机二叉搜索树 (BST)？

Question

我得到了以下任务 - 我有一个二叉搜索树的特定 Java 代码，我需要添加方法来用它做以下事情:

1. 将 BST 转换为按 BST 数据键排序的数组。
2. 从有序整数数组创建平衡 BST。
3. 使用 1. 和 2. 来平衡现有的 BST(随机生成并且可能有些不平衡)
4. 显示平衡前后的 BST。

请伙计们，如果你比我聪明并且知道如何实现，请帮助我!

这是我需要使用的代码:

import java.util.*;
class BtreeNode {

    int data;
    BtreeNode L,R;
    static int depth=0;

    public BtreeNode(){
         data = 0; L = null; R=null;
    }
    public BtreeNode(int key){
         this();data = key;
    }
    public String toString()    {
        return  "["+data+"]";
    }



    public static BtreeNode insOrd(BtreeNode roo, int key){
        if(roo==null)return new BtreeNode(key);
        //Не се допуска повторение на ключове
        if(key==roo.data)return roo;
        if(key<roo.data)roo.L=insOrd(roo.L,key);
        else roo.R=insOrd(roo.R,key);
        return roo;
    }

    public static BtreeNode generate(int length) {
        BtreeNode start = null;
        Random rn = new Random();
        for(int i = 0; i < length; i++){
            start = insOrd(start,rn.nextInt(10000));
        }
        return start;
    }

    public static void spc(int n){
        for(int i=0;i<n;i++)System.out.print(" ");
    }

    public static void print(BtreeNode roo){
        if(roo!=null){
            depth++;
            print(roo.R);
            spc(depth);System.out.println(roo);
            print(roo.L);
            depth--;
        }
    }

    public static BtreeNode find(BtreeNode roo, int key){
        BtreeNode r=null;
        if(roo==null)return r;
        if(roo.data==key)r= roo;
        if(key>roo.data)r= find(roo.R,key);
        if(key<roo.data)r= find(roo.L,key);
        return r;
    }
};

public class Main {

        public static void main(String[] args){
            int N;
            Scanner sc = new Scanner(System.in);
            System.out.print("Enter the number if tree items:");
            N=sc.nextInt();
            BtreeNode c = BtreeNode.generate(N);
            BtreeNode.print(c);
        /*
            System.out.println("This tree has "+
                    BtreeNode.weight(c)+" nodes and "+
                    BtreeNode.height(c)+" levels.");
        */
       }
}

更新:

非常感谢你们的大力帮助，你们无法想象我对你们的建议有多感激!!!

我的整个程序都在运行。我要发布它是因为有人有时可能需要这样的东西。

import java.util.*;
class BtreeNode {

    int data;
    BtreeNode L,R;
    static int depth=0; 

    public BtreeNode(){
         data = 0; L = null; R=null;
    }
    public BtreeNode(int key){
         this();data = key;
    }
    public String toString()    {
        return  "["+data+"]";
    }


    public static ArrayList<BtreeNode> asList(BtreeNode node) {
        ArrayList<BtreeNode> result = new ArrayList<BtreeNode>();
        traverse(node, result);
        Collections.sort(result, new Comparator<BtreeNode>() {
            @Override
            public int compare(BtreeNode arg0, BtreeNode arg1) {
                if (arg0.data < arg1.data)
                    return -1;
                else if (arg0.data > arg1.data)
                    return 1;
                return 0;
            }
        });
        return result;
    }

    private static void traverse(BtreeNode node, ArrayList<BtreeNode> result) {
        if (node.L != null) {
            traverse(node.L, result);
        }
        result.add(node);
        if (node.R != null) {
            traverse(node.R, result);
        }
    }

    public static BtreeNode sortedArrayToBST (ArrayList<BtreeNode> result, int start, int end) {
        if (start > end) return null;
          // same as (start+end)/2, avoids overflow.
          int mid = start + (end - start) / 2;
          BtreeNode node = new BtreeNode(result.get(mid).data);
          node.L = sortedArrayToBST(result, start, mid-1);
          node.R = sortedArrayToBST(result, mid+1, end);

          return node;
        }


    public static BtreeNode insOrd(BtreeNode roo, int key){
        if(roo==null)return new BtreeNode(key);

        if(key==roo.data)return roo;
        if(key<roo.data)roo.L=insOrd(roo.L,key);
        else roo.R=insOrd(roo.R,key);
        return roo;
    }

    public static BtreeNode generate(int length) {
        BtreeNode start = null;
        Random rn = new Random();
        for(int i = 0; i < length; i++){
            start = insOrd(start,rn.nextInt(10000));
        }
        return start;
    }

   public static void spc(int n){
    for(int i=0;i<n;i++)System.out.print(" ");
   }

    public static void print(BtreeNode roo){
        if(roo!=null){
            depth++;
            print(roo.R);
            System.out.print("Level "+depth);
            spc(depth);
            System.out.println(roo);
            print(roo.L);
            depth--;
        }
    }

    public static BtreeNode find(BtreeNode roo, int key){
        BtreeNode r=null;
        if(roo==null)return r;
        if(roo.data==key)r= roo;
        if(key>roo.data)r= find(roo.R,key);
        if(key<roo.data)r= find(roo.L,key);
        return r;
    }
}; 

public class Main {

        public static void main(String[] args){
            int N;
            Scanner sc = new Scanner(System.in);
            System.out.print("Enter the number if tree items:");
            N=sc.nextInt();
            BtreeNode c = BtreeNode.generate(N);
            BtreeNode.print(c);
            System.out.println("********************");
        /*
            System.out.println("This tree has "+
                    BtreeNode.weight(c)+" nodes and "+
                    BtreeNode.height(c)+" levels.");
        */
            ArrayList<BtreeNode> result = BtreeNode.asList(c);
            for (BtreeNode btreeNode : result) {
                System.out.println(btreeNode.data);
            }

        // insert in sorted order
            c = result.get(0);
            for (int i = 1; i < result.size(); i++) {
                BtreeNode.insOrd(c, result.get(i).data);
            }
            BtreeNode.print(c);

            System.out.println("********************");

            BtreeNode d = BtreeNode.generate(N); 
            BtreeNode.print(d);

            System.out.println("********************");

            ArrayList<BtreeNode> result2 = BtreeNode.asList(d);

            for (BtreeNode btreeNode : result2) {
                System.out.println(btreeNode.data);
            }

            System.out.println("********************");

            BtreeNode.print(BtreeNode.sortedArrayToBST(result2, 0, result2.size()-1));
        }
}

Answer 1

首先，您必须拥有一个全局数组和一个遍历方法。 遍历方法应该像这样工作:

在main方法最后添加:

ArrayList<BtreeNode> result = BtreeNode.asList(c);
    for (BtreeNode btreeNode : result) {
        System.out.println(btreeNode.data);
    }

// insert in sorted order
    c = result.get(0);
    for (int i = 1; i < result.size(); i++) {
        c.insOrd(c, result.get(i).data);
    }
    BtreeNode.print(c);

将此方法添加到 BtreeNode 类:

public static ArrayList<BtreeNode> asList(BtreeNode node) {
    ArrayList<BtreeNode> result = new ArrayList<BtreeNode>();
    traverse(node, result);
    Collections.sort(result, new Comparator<BtreeNode>() {
        @Override
        public int compare(BtreeNode arg0, BtreeNode arg1) {
            if (arg0.data < arg1.data)
                return -1;
            else if (arg0.data > arg1.data)
                return 1;
            return 0;
        }
    });
    return result;
}

private static void traverse(BtreeNode node, ArrayList<BtreeNode> result) {
    if (node.L != null) {
        traverse(node.L, result);
    }
    result.add(node);
    if (node.R != null) {
        traverse(node.R, result);
    }
}