Как сбалансировать существующее дерево случайного двоичного поиска (BST), используя массив (в Java)? - PullRequest
Новая
       5

Как сбалансировать существующее дерево случайного двоичного поиска (BST), используя массив (в Java)?

1 голос
/ 21 марта 2012

Я получил следующее назначение - у меня есть определенный код 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.");
        */
       }
}

UPDATE:

Большое спасибо, ребята, за вашу большую помощь, вы не представляете, как я благодарен за ваш совет !!!

У меня вся программа работает. Я собираюсь опубликовать это, потому что кому-то когда-нибудь может понадобиться нечто подобное 

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));
        }
}

Ответы [ 3 ]

2 голосов
/ 21 марта 2012

Ну, для первой точки у вас должен быть глобальный массив и метод обхода.Метод traverse должен работать примерно так:

в конце метода 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);
    }
}
2 голосов
/ 21 марта 2012

1) Создание отсортированного массива можно выполнить с помощью "обхода дерева порядков" - его довольно легко реализовать в виде рекурсивной функции, которую вы запускаете на корневом узле. Это будет выглядеть примерно так: 

void addToListInOrder(List<BtreeNode> l) {
    if(L != null) {
        L.addToListInOrder(l);
    }
    list.add(this);
    if(R != null) {
        R.addToListInOrder(l);
    }
}

2) Рекурсивный алгоритм также будет хорошо работать и здесь: выберите точку посередине (при необходимости округлите вверх или вниз) и выберите ее в качестве корневого узла. Затем разделите оставшиеся точки в двух списках, те, которые находятся до и после выбранного узла, и затем рекурсивно вызовите алгоритм для них. Затем установите результаты как левый и правый дочерний элемент текущего узла. и, наконец, вернуть узел, который был выбран. Обязательно правильно обрабатывать списки только с одним или несколькими узлами

3) Сделайте 1, а затем 2 на BST, чтобы получить сбалансированный отдых.

4) В прошлом я использовал graphviz для некоторых приятных визуализаций, но это, вероятно, выходит за рамки вашего задания. В нем я использовал обход графа по порядку для создания исходного файла для graphviz

0 голосов
/ 21 марта 2012

Просто отметьте http://www.roseindia.net/java/java-get-example/java-binary-tree-code.shtml Для всех этих операций вы должны использовать рекурсию с проверкой конца для текущего узла, если у него нет дочерних элементов.

...