Обход бинарного дерева с константным количеством памяти.

Как-то раз, будучи на собеседование, меня гоняли по структурам данных, в частности по бинарным деревьям. Как любитель функциональщины, я всё рассказывал на рекурсивных алгоритмах, что, в конце концов, вызвало вопрос, как обойти дерево без рекурсии. После описания простейшего кода со стеком, спросили, а можно ли без стека, без динамической памяти, и я, после минуты раздумья, ответил нет. Точную реакцию интервьюера я не помню, но кажется он согласился. Спустя где-то пол года наткнулся где-то в жж на замечание о том, что это возможно, и как итог, придумал решение.

Задача:

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

Рассуждения:

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

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

• Создаём указатель на голову нашего импровизированного списка вершин в которых мы не были. 
• В случае, если мы попадаем на развилку, то добавляем в этот список ещё один элемент, в котором отмечаем текущую вершину. Память для нового элемента списка находим в правой ветке, а сами переходим в левую.
• В случае, если мы попадаем в листок, то смотрим не пуст ли наш список, если это так, то откусываем первый элемент (последняя развилка), и останавливаем нулевые указатели. Переходим конечно в правую ветку относительно последней развилки.

Вот два варианта реализации на языке salltalk и java (если кто-то может попинать меня за стиль кодирования, прошу это сделать, так как сейчас учу этот язык). Проверка корректности производится при помощи использования свёрток, в данном случае свёртка суммы.

Код на Java для узла:

public class Node<T extends Comparable<T>> {
    private T value;
    private Node<T> left, right;

    public Node(T value) {
        this.value = value;
    }

    public void add(T value) {
        if (left == null) {
            left = new Node<T>(value);
            return;
        }
        if (right == null) {
            right = new Node<T>(value);
            return;
        }
        if (left.getSize() < right.getSize()) {
            left.add(value);
        } else {
            right.add(value);
        }
    }

    public void addSort(T value) {
        if (this.value.compareTo(value) == -1) {
            if (left == null) {
                left = new Node<T>(value);
            } else {
                left.addSort(value);
            }
        } else {
            if (right == null) {
                right = new Node<T>(value);
            } else {
                right.addSort(value);
            }
        }
    }

    public int getSize() {
        return 1 + (left == null ? 0 : left.getSize())
                + (right == null ? 0 : right.getSize());
    }

    public Node<T> getNext() {
        if (!(right == null)) return right;
        if (!(left == null)) return left;
        return null;
    }

    public boolean isNormalBranch() {
        if (left == null && right != null) return true;
        if (left != null && right == null) return true;
        return false;
    }

    public boolean isLeaf(){
        return left == null && right == null;
    }

    public Node<T> getLeft() {
        return left;
    }

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

    public Node<T> getRight() {
        return right;
    }

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

    public T getValue() {
        return value;
    }

}

Код на Java для корня, в котором и реализован алгоритм:

import java.util.*;

interface Callable<T1, T2> {
        public T1 call(T1 acc, T2 e);
        }

public class Root<T extends Comparable<T>> {
    private Node<T> root;

    public Root() {
    }

    public int getSize() {
        return root.getSize();
    }

    public void add(T value) {
        if (root == null) {
            root = new Node<T>(value);
        } else {
            root.add(value);
        }
    }

    public void addSort(T value) {
        if (root == null) {
            root = new Node<T>(value);
        } else {
            root.addSort(value);
        }
    }

    public Node getRoot() {
        return root;
    }

    private Node<T> store(Node<T> branch, Node<T> edit) {
        Node<T> node = branch;
        while (!node.isLeaf()) {
            node = node.getNext();
        }
        node.setLeft(branch);
        node.setRight(edit);
        return node;
    }

    private Node<T> fetch(Node<T> node){
        Node<T> tmp = node.getRight();
        node.setLeft(null);
        node.setRight(null);
        return tmp;
    }

    public <TAcc> TAcc inject(TAcc state, Callable<TAcc, T> fun){
        if (root == null) return null;
        Node<T> current = root;
        Node<T> edit = null;
        while (!(edit == null && current.isLeaf())) {
            state = fun.call(state, current.getValue());
            if (current.isNormalBranch()) {
                current = current.getNext();
            } else {
                if (current.isLeaf()) {
                    current = edit.getLeft().getRight();
                    edit = fetch(edit);
                } else {
                    edit = store(current, edit);
                    current = current.getLeft();
                }
            }
        }
        state = fun.call(state, current.getValue());
        return state;
    }

    public static void main(String[] args) {
        Root<Integer> root = new Root<Integer>();
        Random rand = new Random();
        long state = 0;
        int tmp;
        for (int i = 0; i < 10000; i++){
            tmp = rand.nextInt(100000);
            root.add(tmp);
            root.addSort(tmp + 1);
            state += 2*tmp + 1;
        }
        System.out.println(state ==
                root.inject(0, new Callable<Integer, Integer>(){
                    public Integer call(Integer a, Integer b){
                        return a + b;
                    }
                }));
    }
}

Код на Smalltalk, реализован в Pharo, почти стандартный экспорт в файл.

Object subclass: #Node
 instanceVariableNames: 'left rigth value'
 classVariableNames: ''
 poolDictionaries: ''
 category: 'my'!

add: v
 left ifNil: [ ^ left := Node new value: v ].
 rigth ifNil: [ ^ rigth := Node new value: v ].
 ^ (left size) < (rigth size) ifTrue: [ left add: v ] ifFalse: [ rigth add: v ]

addSort: v
 ^ v < value
  ifTrue: [ left isNil ifTrue: [ left := Node new value: v ] ifFalse: [ left addSort: v ] ] 
  ifFalse: [ rigth isNil ifTrue: [ rigth := Node new value: v ] ifFalse: [ rigth addSort: v ] ] .

fetch
 | tmp |
 tmp := rigth.
 left := nil.
 rigth := nil.
 ^ tmp

isBranch
 (left isNil) & (rigth isNil not) ifTrue: [ ^ true ].
 (left isNil not) & (rigth isNil) ifTrue: [ ^ true ].
 ^ false


isLeaf
 ^ left isNil & rigth isNil

left
 ^ left

left: anObject
 left := anObject

next 
 rigth isNil not ifTrue: [ ^ rigth ].
 left isNil not ifTrue: [ ^ left ].
 ^ nil

printOn: aStream
 aStream nextPutAll: 'aNode: '.
 aStream print: value.

rigth
 ^ rigth

rigth: anObject
 rigth := anObject

size
 | lsize rsize |
 lsize := left isNil ifTrue: [ 0 ] ifFalse: [ left size ].
 rsize := rigth isNil ifTrue: [ 0 ] ifFalse: [ rigth size ].
 ^ lsize + rsize + 1

store: branch lastEdit: edit
 ^ self isLeaf 
  ifTrue: [ 
   left := branch.
   rigth := edit.
   self ]
  ifFalse: [ self next store: branch lastEdit: edit ].

value
 ^ value

value: anObject
 value := anObject


Object subclass: #Root
 instanceVariableNames: 'root'
 classVariableNames: ''
 poolDictionaries: ''
 category: 'my'!

add: value
 ^ root isNil ifTrue: [ root := Node new value: value ] ifFalse: [ root add: value ]

addSort: v
 ^ root isNil ifTrue: [ root := Node new value: v ] ifFalse: [ root addSort: v ]

inject: init into: aBlock
 | cur edit state |
 cur := root.
 state := init.
 edit := nil.

 [ edit isNil & cur isLeaf ] whileFalse: [
  state := aBlock value: state value: cur value.
  cur isBranch
   ifTrue: [ cur := cur next ]
   ifFalse: [ cur isLeaf
    ifTrue: [ 
     cur := edit left rigth. 
     edit := edit fetch ]
    ifFalse: [
     edit := cur store: cur lastEdit: edit.
     cur := cur left ] ] ].
 ^ aBlock value: state value: cur value.

root
 ^ root

size
 ^ root size

Тестовый workspace:

root := Root new.
rand := Random new.
state := 0.

1000 timesRepeat: [ | t | 
 t := rand nextInt: 1000000.
 state := state + 1 + (t * 2). 
 root addSort: t.
 root add: (t + 1) ].

(root inject: 0 into: [ :a :b | a + b ]) = state. 

Файлы с исходниками
smalltalk: http://dl.dropbox.com/u/1619524/src/binary_tree.st
java node class: http://dl.dropbox.com/u/1619524/src/Node.java
java root class: http://dl.dropbox.com/u/1619524/src/Root.java

PS Буду рад любым замечаниям.