Получить все элементы из двоичного дерева в список - JAVA

#java #list #binary-tree

#java #Список #двоичное дерево

Вопрос:

Допустим, у нас есть двоичное дерево, и мы хотим выполнить итерацию по нему, получить все элементы (Node.value) и создать список с ними. Я думал, что решение проблемы таким образом :

   public List<T> fromTreeToList(){
   // use elementsToList to create the list
    }
public (what is the optional) elementsToList(Node node){
   // use this method to recursion
        List<T> example = new ArrayList<>();
        if (node != null){
            example.add(node.val) ;
            example.add(elementsToList(node.left));
            example.add(elementsToList(node.right)) ;
       }else System.out.println("Empty Tree");
}

1. Как вы хотите выполнить итерацию по нему, то есть в каком порядке? Это может помочь вам datastructuresnotes. blogspot.com/2009/02 /…

2. Порядок не важен

3. Хорошо, не могли бы вы опубликовать свой Node код, пожалуйста?

4. Мой узел — это класс Node<>{ T val; Узел <> слева; Узел <> справа; Узел (T v) { val = v; слева = null; справа = null; }

Ответ №1:

Мы можем использовать рекурсивную функцию для обхода дерева и продолжать добавлять элементы в список. Предполагая, что Node.val имеет тип int

 public static void main(String[] args) {
        //assuming that we already have tree with root treeRoot
        List<Integer> list = new ArrayList<>();
        treeItemsToList(treeRoot, list); 
        //print the list
    }


public void treeItemsToList(Node node, List<Integer> list ){
        if(node == null){
            return;
        }
        treeItemsToList(node.left, list);
        list.add(node.val);
        treeItemsToList(node.right, list);
    }

Ответ №2:

Если бы вы предоставили свой код, мой ответ был бы более точным, но это моя реализация вашего метода Preorder Traversal , в основном вы добавляете Node , если вы идете вниз Tree , иначе вы каждый раз переходите к самому левому, а затем проверяете правую часть subtree .

 public List<Node> fromTreeToList(){
    return elementsToList(root);
}

public List<Node> elementsToList(Node node) {
    List<Node> nodes = new ArrayList<>();
    Node current = node;
    Node rootParent = node.getParent();
    Node previous = null;
    while (current != rootParent) {
        if (previous == current.getParent()) { // going down the tree
            nodes.add(current);
            previous = current;
            if (current.getLeft() != null) {
                current = current.getLeft();
            } else {
                if (current.getRight() != null) {
                    current = current.getRight();
                } else {
                    current = current.getParent();
                }
            }
        } else if (previous.equals(current.getLeft())) { // going up the left subtree
            previous = current;
            if (current.getRight() != null) {
                current = current.getRight();
            } else {
                current = current.getParent();
            }
        } else { // going up the right subtree
            previous = current;
            current = current.getParent();
        }
    }
    return nodes;
}