Напишите нерекурсивный обход дерева двоичного поиска, используя постоянное пространство и O (n) время выполнения

Question

Это не домашняя работа, это вопрос интервью.

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

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

Любая помощь будет оценена.

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

Answer 1

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

Каждый узел имеет 2 указателя, поэтому его можно использовать для представления двусвязного списка. Предположим, вы переходите от Root к Root.Left = Current. Теперь указатель Root.Left бесполезен, поэтому присвойте ему значение Current.Right и перейдите к Current.Left. Когда вы дойдете до самого левого дочернего элемента, у вас будет связанный список с деревьями, свисающими с некоторых узлов. Теперь повторяем это, повторяя процесс для каждого дерева, с которым вы сталкиваетесь, когда вы идете

РЕДАКТИРОВАТЬ: продумано до конца. Вот алгоритм, который печатает по порядку:

void traverse (Node root) {
  traverse (root.left, root);
}

void traverse (Node current, Node parent) {
  while (current != null) {
    if (parent != null) {
      parent.left = current.right;
      current.right = parent;
    }

    if (current.left != null) {
      parent = current;
      current = current.left;
    } else {
      print(current);
      current = current.right;
      parent = null;
    }
  }
}

Answer 2

Как насчет обхода дерева Morris Inorder?Он основан на понятии потоковых деревьев и изменяет дерево, но возвращает его обратно, когда все готово.

Linkie: http://geeksforgeeks.org/?p=6358

Не использует дополнительное пространство.

Answer 3

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

Это возможно, если ваше двоичное дерево находится в массиве вместо структуры объекта на основе указателя. Но тогда вы можете получить доступ к любому узлу напрямую. Какой вид обмана; -)

Answer 4

Вот более короткая версия оригинального ответа iluxa .Он выполняет точно такие же шаги манипуляции и печати узла, в точно таком же порядке - но в упрощенном виде [1]:

void traverse (Node n) {
  while (n) {
    Node next = n.left;
    if (next) {
      n.left = next.right;
      next.right = n;
      n = next;
    } else {
      print(n);
      n = n.right;
    }
  }
}

[1] Плюс, он работает даже тогда, когда корневой узел дерева не имеетоставленный ребенок.

Answer 5

незначительный особый случай для ответа iluxa выше

if(current== null)
        {
            current = root;
            parent = current.Right;
            if(parent != null)
            {
                current.Right = parent.Left;
                parent.Left = current;
            }
        }

Answer 6

Принятый ответ нуждается в следующем изменении, иначе он не будет печатать дерево, где BST имеет только один узел

if (current == NULL && root != NULL)
   print(root);

Answer 7

Мы можем пройти через двоичное дерево без изменения самого дерева (при условии, что узлы имеют родительский указатель).И это можно сделать в постоянном пространстве.Я нашел эту полезную ссылку для того же http://tech.technoflirt.com/2011/03/04/non-recursive-tree-traversal-in-on-using-constant-space/

Answer 8

В заголовке вопроса не упоминается отсутствие «родительского» указателя в узле.Хотя это не обязательно требуется для BST, многие реализации двоичного дерева имеют родительский указатель.class Node {Node * left;Узел * правый;Узел * родительский;Данные данных;};

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

1. SouthWest: вы находитесь на левой стороне ребра, переходя от родителя к его левому потомку
2. NorthEast: переход от левого потомка к его родителю
3. SouthEast: переход от родителя к правому ребенку
4. NorthWest: переход от правого ребенка к его родителю

Traverse( Node* node )
{
    enum DIRECTION {SW, NE, SE, NW};
    DIRECTION direction=SW;

    while( node )
    {
        // first, output the node data, if I'm on my way down:
        if( direction==SE or direction==SW ) {
            out_stream << node->data;
        }

        switch( direction ) {
        case SW:                
            if( node->left ) {
                // if we have a left child, keep going down left
                node = node->left;
            }
            else if( node->right ) {
                // we don't have a left child, go right
                node = node->right;
                DIRECTION = SE;
            }
            else {
                // no children, go up.
                DIRECTION = NE;
            }
            break;
        case SE:
            if( node->left ) {
                DIRECTION = SW;
                node = node->left;
            }
            else if( node->right ) {
                node = node->right;
            }
            else {
                DIRECTION = NW;
            }
            break;
        case NE:
            if( node->right ) {
                // take a u-turn back to the right node
                node = node->right;
                DIRECTION = SE;
            }
            else {
                node = node->parent;
            }
            break;
        case NW:
            node = node->parent;
            break;
        }
    }
}

Answer 9

Это дерево поиска, так что вы всегда можете получить следующий ключ / запись

Вам нужно что-то вроде (я не тестировал код, но он так прост, как кажется)

java.util.NavigableMap<K, V> map=...
for (Entry<K, V> e = map.firstEntry(); e!=null; e = map.higherEntry(e.getKey())) {
  process(e)
}

для ясности это higherEntry, так что это не рекурсивно.Вот оно:)

final Entry<K,V> getHigherEntry(K key) {
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = compare(key, p.key);
        if (cmp < 0) {
            if (p.left != null)
                p = p.left;
            else
                return p;
        } else {
            if (p.right != null) {
                p = p.right;
            } else {
                Entry<K,V> parent = p.parent;
                Entry<K,V> ch = p;
                while (parent != null && ch == parent.right) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        }
    }
    return null;
}

Answer 10

Это двоичное дерево поиска, поэтому каждый узел может быть достигнут серией правых / левых решений. Опишите эту серию как 0/1, от наименее значимого бита к наиболее значимому. Таким образом, функция f (0) означает «узел, найденный путем выбора правой ветви, пока вы не найдете лист; f (1) означает, что вы берете один левый, а остальные правый; f (2) - то есть двоичный код 010 - - означает повернуть направо, затем налево, затем направо, пока вы не найдете лист. Повторяйте f (n), начиная с n = 0, пока не дойдете до каждого листа. Неэффективно (так как вы должны начинать с вершины дерева каждый время), но постоянная память и линейное время.