Как стать автором
Обновить

Обход бинарных деревьев: рекурсия, итерации и указатель на родителя

Время на прочтение 5 мин
Количество просмотров 183K
Основы о бинарных деревьях представлены, в том числе, здесь . Добавлю свои «5 копеек» и данным постом систематизирую материалы, связанные с обходом бинарных деревьев, а именно сравнений возможностей рекурсии и итераций, а также обсуждение возможностей использования указателя на родительский узел.

Итак… язык Java, класс узла имеет следующий вид:
public class Node {
	Node left;
    Node right;
    Node parent;
    String value;
    public Node(Node p, String v){
        parent=p;
        value=v;
    }
    …
}

Примечание: Указатель на родителя parent – как правило не имеет большого смысла, однако, как следует из заголовка и будет показано, может быть полезен в ряде случаев.

Обход деревьев – последовательная обработка (просмотр, изменение и т.п.) всех узлов дерева, при котором каждый узел обрабатывается строго один раз. При этом получается линейная расстановка узлов дерева.

В зависимости от траекторий выделяют два типа обхода:
— горизонтальный (в ширину); и
— вертикальный (в глубину).

Горизонтальный обход подразумевает обход дерева по уровням (level-ordered) – вначале обрабатываются все узлы текущего уровня, после чего осуществляется переход на нижний уровень.
level

При вертикальном обходе порядок обработки текущего узла и узлов его правого и левого поддеревьев варьирует и по этому признаку выделяют три варианта вертикального обхода:
— прямой (префиксный, pre-ordered): вершина – левое поддерево – правое поддерево;
— обратный (инфиксный, in-ordered): левое поддерево – вершина – правое поддерево; и
— концевой (постфиксный, post-ordered): левое поддерево – правое поддерево – вершина.
хостинг картинок
Сам обход во всех случаях в принципе один и тот же, различается порядок обработки. Для представления в каком порядке будет проходить обработка узлов дерева удобно следовать по «контуру обхода». При прямом обходе узел будет обработан в точке слева от узла, при обратном снизу от узла и при концевом, соответственно, справа от узла.
Другими словами «находясь» в некотором узле, нам нужно знать, нужно ли его обрабатывать и куда двигаться дальше.

Рекурсия


Все три варианта вертикального обхода элементарно реализуются рекурсивными функциями.

    void recPreOrder(){
        treatment();
        if (left!=null) left.recPreOrder();
        if (right!=null) right.recPreOrder();
    }
    void recInOrder(){
        if (left!=null) left.recInOrder();
        treatment();
        if (right!=null) right.recInOrder();
    }
    void recPostOrder(){
        if (left!=null) left.recPostOrder();
        if (right!=null) right.recPostOrder();
        treatment();
    }


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

Контейнеры


В случае использования итераций необходимо хранить сведенья о посещенных, но не обработанных узлах. Используются контейнеры типа стек (для вертикального обхода) и очередь (для горизонтального обхода).

Горизонтальный обход:
обрабатываем первый в очереди узел, при наличии дочерних узлов заносим их в конец очереди. Переходим к следующей итерации.
    static void contLevelOrder(Node top){
        Queue<Node> queue=new LinkedList<> ();
        do{
            top.treatment();
            if (top.left!=null) queue.add(top.left);
            if (top.right!=null) queue.add(top.right);
            if (!queue.isEmpty()) top=queue.poll();
        }while (!queue.isEmpty());
    }


Вертикальный прямой обход:
обрабатываем текущий узел, при наличии правого поддерева добавляем его в стек для последующей обработки. Переходим к узлу левого поддерева. Если левого узла нет, переходим к верхнему узлу из стека.
    static void contPreOrder(Node top){
         Stack<Node> stack = new Stack<> (); 
         while (top!=null || !stack.empty()){
             if (!stack.empty()){
                 top=stack.pop();
             }
             while (top!=null){
                 top.treatment();
                 if (top.right!=null) stack.push(top.right);
                 top=top.left;
             }
         }
    }


Вертикальный обратный обход:
из текущего узла «спускаемся» до самого нижнего левого узла, добавляя в стек все посещенные узлы. Обрабатываем верхний узел из стека. Если в текущем узле имеется правое поддерево, начинаем следующую итерацию с правого узла. Если правого узла нет, пропускаем шаг со спуском и переходим к обработке следующего узла из стека.
    static void contInOrder(Node top){
         Stack<Node> stack = new Stack<> (); 
         while (top!=null || !stack.empty()){
             if (!stack.empty()){
                 top=stack.pop();
                 top.treatment();
                 if (top.right!=null) top=top.right;
                 else top=null;
             }
             while (top!=null){
                 stack.push(top);
                 top=top.left;
             }
         }
    }


Вертикальный концевой обход:
Здесь ситуация усложняется – в отличие от обратного обхода, помимо порядка спуска нужно знать обработано ли уже правое поддерево. Одним из вариантов решения является внесение в каждый экземпляр узла флага, который бы хранил соответствующую информацию (не рассматривается). Другим подходом является «кодирование» непосредственно в очередности стека — при спуске, если у очередного узла позже нужно будет обработать еще правое поддерево, в стек вносится последовательность «родитель, правый узел, родитель». Таким образом, при обработке узлов из стека мы сможем определить, нужно ли нам обрабатывать правое поддерево.
    static void contPostOrder(Node top){
         Stack<Node> stack = new Stack<> (); 
         while (top!=null || !stack.empty()){
             if (!stack.empty()){
                 top=stack.pop();
                 if (!stack.empty() && top.right==stack.lastElement()){
                     top=stack.pop();
                 }else{
                     top.treatment();
                     top=null;
                 }
             }
             while (top!=null){
                 stack.push(top);
                 if (top.right!=null){
                     stack.push(top.right);
                     stack.push(top);
                 }
                 top=top.left;
             }
         }
    }

Об указателе на родителя


Наличие в экземпляре класса указателя на родителя приносит определенные хлопоты при построении и балансировки деревьев. Однако, возможность из произвольного узла дерева «дойти» до любого из его узлов может придтись весьма кстати. Все, за чем нужно следить при «подъеме» на верхний уровень – пришли ли от правого потомка или от левого.
Так, с использованием родительских указателей будет выглядеть код вертикального концевого обхода.
    static void parentPostOrder(Node top){
        boolean fromright=false;
        Node shuttle=top, holder;
        while(true){
            while (fromright){
                shuttle.treatment();
                if (shuttle==top) return;
                holder=shuttle;
                shuttle=shuttle.parent;
                fromright=shuttle.right==holder;
                if (!fromright && shuttle.right!=null) shuttle=shuttle.right;
                else fromright=true;
            }
            while (shuttle.left!=null) shuttle=shuttle.left;
            if (shuttle.right!=null) shuttle=shuttle.right;
            else fromright=true;
        }
    }

Другой класс задач, которые позволяет решить родительский указатель, как уже было упомянуто — перемещение внутри дерева.
Так, что бы перейти на n-ый по счету узел от текущего узла, без «ориентации в дереве» пришлось бы обходить дерево с самого начала, до известного узла, а потом еще n-узлов. С использованием же родительского указателя при обратном обходе дерева перемещение на steps узлов от текущего узла (start) будет иметь следующий вид.
    public static Node walkTheTree(Node start, int steps){
        boolean fromright=true;
        Node shuttle=start, holder;
        if (shuttle.right!=null){
            shuttle=shuttle.right;
            while (shuttle.left!=null) shuttle=shuttle.left;
            fromright=false;
        }
        int counter=0;
        do{
            while (true){
                if (!fromright && ++counter==steps) return shuttle;
                if (!fromright && shuttle.right!=null){
                        shuttle=shuttle.right;
                        break;
                    }
                holder=shuttle;
                shuttle=shuttle.parent;
                fromright=(holder==shuttle.right);
            }
            while (shuttle.left!=null) shuttle=shuttle.left;
        }while (true);
    }

Примечание: В общем случае также требуется предотвратить возможность попытки выхода за пределы дерева (подняться выше корневого узла).
Теги:
Хабы:
-5
Комментарии 4
Комментарии Комментарии 4

Публикации

Истории

Работа

Java разработчик
356 вакансий

Ближайшие события

Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн
Геймтон «DatsEdenSpace» от DatsTeam
Дата 5 – 6 апреля
Время 17:00 – 20:00
Место
Онлайн