Как перенести узлы из двоичного дерева в массив?

Question

Я борюсь с переносом значений из дерева двоичного поиска в массив, но мне также нужно, чтобы они были отсортированы. Вот инструкции того, что нужно.

Метод toArray должен создать и вернуть массив, содержащий каждый элемент в дереве в отсортированном порядке («по порядку»). Емкость этого массива должна равняться количеству элементов, которые он содержит. Этот метод должен использовать рекурсивный закрытый вспомогательный метод toArray (BSTNode, List) для генерации массива. Этот массив необходимо будет создать как массив сопоставимых объектов и привести к массиву из E объектов. Вы можете использовать метод toArray (E []) Collection, чтобы помочь с генерацией массива.

Поэтому вот мой код, который у меня есть:

 public E[] toArray()
    {
        List<E> lista = new ArrayList<E>();
        toArray(root, lista);
        E[] good = (E[]) lista.toArray();
        return good;
    }
    private void toArray(BSTNode<E> node, List<E> aList)
    {
        if(node.left != null)
        {
            aList.add(node.left.data);
        }
    }

Вот остальная часть кода для ссылок, но я больше сосредоточен на методах toArray, чем на чем-либо еще. Я не могу понять, как отсортировать их в массив. Пожалуйста помоги.

public class BinarySearchTree<E extends Comparable<E>>
{
private BSTNode<E> root; // root of overall tree
private int numElements;

// post: constructs an empty search tree
public BinarySearchTree()
{
    root = null;
}

// post: value added to tree so as to preserve binary search tree
public void add(E value)
{
    root = add(root, value);
}
// post: value added to tree so as to preserve binary search tree
private BSTNode<E> add(BSTNode<E> node, E value)
{
    if (node == null)
    {
        node = new BSTNode<E>(value);
        numElements++;
    }
    else if (node.data.compareTo(value) > 0)
    {
        node.left = add(node.left, value);
    }
    else if (node.data.compareTo(value) < 0)
    {
        node.right = add(node.right, value);
    }
    return node;
}

// post: returns true if tree contains value, returns false otherwise
public boolean contains(E value)
{
    return contains(root, value);
}
// post: returns true if given tree contains value, returns false otherwise
private boolean contains(BSTNode<E> node, E value)
{
    if (node == null)
    {
        return false;
    }
    else
        {
        int compare = value.compareTo(node.data);
        if (compare == 0)
        {
            return true;
        }
        else if (compare < 0)
        {
            return contains(node.left, value);
        }
        else
            {   // compare > 0
            return contains(node.right, value);
        }
    }
}
    public void remove(E value)
    {
        root = remove(root, value);
    }
    private BSTNode<E> remove(BSTNode<E> node, E value)
    {
        if(node == null)
        {
            return null;
        }
        else if(node.data.compareTo(value) < 0)
        {
            node.right = remove(node.right, value);
        }
        else if(node.data.compareTo(value) > 0)
        {
            node.left = remove(node.left, value);
        }
        else
        {
            if(node.right == null)
            {
                numElements--;
                return node.left;// no R child; replace w/ L
            }
            else if(node.left == null)
            {
                numElements--;
                return node.right;   // no L child; replace w/ R
            }
            else
            {
                // both children; replace w/ max from L
                node.data = getMax(node.left);
                node.left = remove(node.left, node.data);
            }
        }
        return node;
    }
    private E getMax(BSTNode<E> node)
    {
        if(node.right == null)
        {
            return node.data;
        }
        else
        {
            return getMax(node.right);
        }
    }
    public void clear()
    {
        root = null;
        numElements--;
    }
    public boolean isEmpty()
    {
        if(numElements == 0)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    public int size()
    {
        return numElements;
    }
    //My toArray Methods will go here. 
    public Iterator<E> iterator()
    {
        return new Iterator<>(root);
    }
    public static class Iterator<E>
    {
        private Stack<BSTNode<E>> stack;

        public Iterator(BSTNode<E> node)
        {
            this.stack = new Stack<>();
            while (node != null)
            {
                stack.push(node);
                node = node.left;
            }
        }
        public boolean hasNext()
        {
            return !stack.isEmpty();
        }
        public E next()
        {
            BSTNode<E> goodDays = stack.pop();
            E result = goodDays.data;
            if (goodDays.right != null)
            {
                goodDays = goodDays.right;
                while (goodDays != null)
                {
                    stack.push(goodDays);
                    goodDays = goodDays.left;
                }
            }
            return result;
        }
    }
private static class BSTNode<E>
{
    public E data;
    public BSTNode<E> left;
    public BSTNode<E> right;

    public BSTNode(E data)
    {
        this(data, null, null);
    }
    public BSTNode(E data, BSTNode<E> left, BSTNode<E> right)
    {
        this.data = data;
        this.left = left;
        this.right = right;
    }
}
}

Answer 1

Подождите, это бинарное дерево поиска, поэтому оно уже отсортировано.

Тогда вам нужно пройтись по дереву.

Учитывая, что у вас есть что-то вроде:

   4
 /   \
2      6
 \    /  \
  3  5    9

Чтобы вставить его, вам необходимо:

Учитывая корень дерева

• A. Если дерево пустое, вставлять нечего.
• B. Если не ноль:
  • B.1 Вставить все слева
  • B.2 Вставить корень дерева
  • B.3 Вставить все справа

Что бы выглядело так:

void walkAndInsert(tree, array) {
    if (tree == null) {//A
        return
    } else { //B
      walkAndInsert(tree.left) //B.1
      array.add(tree.root) //B.2
      walkAndInsert(tree.right) //B.3
    }
}    

Таким образом, применяя эти шаги к массиву:

Является ли дерево нулевым? Нет, затем выполните шаг #B (вставьте все слева, root и все справа)

//B
tree = 
   4
 /   \
2      6
 \    /  \
  3  5    9

array =[]

Берём левую ветвь и повторяем процесс (шаг # B.1, вставляем все левые):

Является ли дерево нулевым? Нет, затем выполните # B

//B.1
tree = 
2      
 \      
  3     

array =[]

Поскольку левая ветвь равна нулю, следующее выполнение будет выглядеть так:

Является ли дерево нулевым? да, тогда верните

//A
tree = 

array = []

Это завершит шаг B.1, теперь мы можем перейти к шагу B.2, вставить root

//B.2
tree = 
2      
 \      
  3     

array =[2]

После шага B.3 вставить все справа

Является ли дерево нулевым? Нет (там 3),

//B.3
tree =      
  3     

array =[2]

Затем выполните # B.1 для этого дерева

Дерево пусто? Да, это завершает это B.1

//A
tree =      

array =[2]

Теперь в B.2 мы вставляем этот корень

Является ли дерево нулевым? Нет (там 3),

//B.2
tree =      
  3     

array =[2,3]

И, наконец, мы идем к B.3 и вставляем все справа

Но там ничего нет, поэтому мы просто возвращаем

 //A
tree =      

array =[2,3]

Это завершает левую ветвь нашего самого начального дерева.

Итак, после завершения B.1 в нашем исходном дереве мы выполняем B.2, и наши данные выглядят следующим образом:

// B.2 on the initial tree
tree = 
   4
 /   \
2      6
 \    /  \
  3  5    9

array =[2,3,4]

И мы повторяем с правой стороны

Нуль? нет, тогда B на ветке с 5, вставьте 6 и шаг B на ветке с 9

//B.3
tree = 
    6
   /  \
  5    9

array =[2,3,4]

// B.1
tree = 
    5

array =[2,3,4]

// A
tree = 


array =[2,3,4]

// B.2
tree = 
    5

array =[2,3,4,5]

// B.2
tree = 
    6
   /  \
  5    9

array =[2,3,4,5,6]

// B.3
tree = 
    9

array =[2,3,4,5,6]

// A
tree = 


array =[2,3,4,5,6]

// B.2
tree = 
    9

array =[2,3,4,5,6,9]

Answer 2

Рабочий пример описанных шагов здесь

import java.util.*;
import java.lang.reflect.Array;
import static java.lang.System.out;

class Tree<E extends Comparable<E>> {

    E root;
    Tree<E> left;
    Tree<E> right;

    void insert(E element) {
        if (this.root == null) {
            this.root = element;
            this.left = new Tree<E>();
            this.right = new Tree<E>();
        } else if (element.compareTo(this.root) < 0 ) {
            left.insert(element);
        } else {
            right.insert(element);
        }
    }

    E[] toArray() {
      List<E> a = new ArrayList<>();
      toArray(this, a);
      @SuppressWarnings("unchecked")
      final E[] r = a.toArray((E[]) Array.newInstance(a.get(0).getClass(), a.size()));
      return r;
    }

    // instance method just to retain the generic type E
    private void toArray(Tree<E> t, List<E> list) {
        if (t == null || t.root == null) {
            return;
        } else {
            toArray(t.left, list);
            list.add(t.root);
            toArray(t.right, list);
        }
    }

    public static void main(String ... args) {
        Tree<String> t = new Tree<>();
        t.insert("hola");
        t.insert("adios");
        t.insert("fuimonos");

        System.out.println(Arrays.toString(t.toArray()));
    }
}

Answer 3

Я понял это. Я раскрою код и объясню, что происходит.

В общественных местах я делаю Список, который скоро станет списком массивов. Затем я вызываю вспомогательный метод toArray (private) для установки значений. Корень для верхнего и список для списка, в который это войдет. После сделайте массив и установите размер с помощью numElements. Сравнимо там, потому что в самом верху моего кода это то, что он расширяет. Затем поместите этот массив в список. Наконец верните это.

 public E[] toArray()
    {
        List<E> lista = new ArrayList<E>();
        toArray(root, lista);
        E[] arr = (E[]) new Comparable[numElements];
        lista.toArray(arr);
        return arr;
    }

В частном порядке я делаю рекурсию. Пока узел не пустой (нулевой), массив будет непрерывно искать левые узлы, пока не останется левый (левый), поэтому добавьте это в массив. Затем добавляет правильные.

 private void toArray(BSTNode<E> node, List<E> aList)
    {
        if(node != null)
        {
            toArray(node.left, aList);
            aList.add(node.data);
            toArray(node.right, aList);
        }
    }

Извините, если это было трудно понять, я не лучший в объяснении вещей, однако это сработало для меня.