Переход по дереву в массив

Я должен пройти по дереву двоичного поиска в качестве предварительного, последующего и последующего порядка и вставить значения в объект [] в Java. Честно говоря, я понятия не имею, как это сделать, и мне нужен совет.

Моя функция:

public Object[] traversePreOrder()

Все, что мне нужно, это в основном идеи или подсказки, как выполнить эту задачу. Если я прохожу по дереву в качестве предзаказа, объект [0], очевидно, является значением корня. Затем я продолжаю в левом дереве и вставляю самые левые значения в свой массив. Затем я вставляю правый дочерний элемент самого левого узла и продолжаю с родительским элементом обоих узлов, если у правого узла нет дочерних узлов.

Но мой метод не может запомнить, какие значения уже были проверены и вставлены. Я также думал об обходе в postorder, помещении каждого элемента в стек и помещении каждого элемента в свой массив, но у меня есть ограничения в моих знаниях о том, как это реализовать.

Помощь!

Вот что, на мой взгляд, уже правильно:

@Override
public Object[] traversePreOrder() {
    Object[] preOrderArray = new Object[elements];
    if (elements == 0) {
        return preOrderArray;
    }



    return preOrderArray;

}

Очевидно, что этот пробел необходимо восполнить.

Дополнительно у меня есть в качестве основных методов и конструкторов:

BinarySearchTreeNode(T value, BinarySearchTreeNode<T> left,
        BinarySearchTreeNode<T> right) {
    this.value = value;
    this.left = left;
    this.right = right;
}

BinarySearchTreeNode(T value) {
    this(value, null, null);
}

BinarySearchTreeNode<T> getLeft() {
    return left;
}

void setLeft(BinarySearchTreeNode<T> left) {
    this.left = left;
}

BinarySearchTreeNode<T> getRight() {
    return right;
}

void setRight(BinarySearchTreeNode<T> right) {
    this.right = right;
}

T getValue() {
    return value;
}

void setValue(T value) {
    this.value = value;
}

java tree traversal preorder
person Granolaboy    schedule 29.05.2013    source источник
comment
Используйте очередь, а затем преобразуйте ее в массив.   -  person Sotirios Delimanolis    schedule 29.05.2013
comment
Это домашнее задание? meta.stackexchange.com/questions/10811/   -  person crush    schedule 29.05.2013
comment
Это необязательное задание. Я делаю это, чтобы подготовиться к экзаменам.   -  person Granolaboy    schedule 29.05.2013
comment
en.wikipedia.org/wiki/Tree_traversal#Implementations   -  person arynaq    schedule 29.05.2013
comment
Можем ли мы хотя бы увидеть ваш метод?   -  person crush    schedule 29.05.2013
comment
Покажите нам код, пожалуйста.   -  person Adam Arold    schedule 29.05.2013

Ответы (2)


arrow_upward
1
arrow_downward

Идеальный случай для использования рекурсии. Создать метод

List<BinarySearchTreeNode> traverse(BinarySearchTreeNode n) {
    // traversal code
}

где код обхода пересекает левый дочерний элемент и правый дочерний элемент, если он есть, и

  • для обхода предварительного порядка объединяет значение, результат левого дочернего элемента и результат правого дочернего элемента;
  • для обхода по порядку объединяет результат левого дочернего элемента, значение и результат правого дочернего элемента;
  • для последующего обхода объединяет результат левого дочернего элемента, результат правого дочернего элемента и значение.

Вызов traverse для корня и преобразование результата в Object[].

person Arend    schedule 29.05.2013
comment
Большое Вам спасибо. Я попробую. - person Granolaboy; 29.05.2013
comment
Можете ли вы сделать так, чтобы возвращаемый тип для этого рекурсивного метода был списком? Кажется, каждый раз, когда его вызывают, он пытается вернуть отдельный список? Может, я неправильно смотрю ... - person sage88; 29.05.2013
comment
Конечно, он будет возвращать каждый раз отдельный список - просто объедините их в свой собственный. Ваше решение также будет работать и будет быстрее регистрироваться в n-множителе, потому что вы не копируете списки, а полагаетесь на побочный эффект рекурсивной функции, который гораздо менее очевиден для рассуждений. - person Arend; 29.05.2013
comment
@Pulz, если вам это нравится, рассмотрите возможность голосования за - person Arend; 30.05.2013

arrow_upward
0
arrow_downward

Как упоминала Аренд выше, это общая идея. Я не уверен, что вы сможете получить список каждый раз, но, возможно, сможете. Однако, если эта реализация не работает, вы можете попробовать что-то вроде этого, чтобы проверить, работает ли все остальное:

private List nodeValues = new ArrayList();

public void traversePreRecursive(BinarySearchTreeNode node) 
{
    if (node != null)
    {
        nodeValues.add(node.getValue());
        traversePreRecursive(node.getLeft());
        traversePreRecursive(node.getRight());
    }
}
person sage88    schedule 29.05.2013