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

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

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

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

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

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

Ответы

Ответ 1

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

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

EDIT: продумал. Здесь алгоритм, который печатает в порядке:

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;
    }
  }
}

Ответ 2

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

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

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

Ответ 3

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

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

Ответ 4

Вот более короткая версия iluxa оригинальный ответ. Он выполняет точно те же операции node манипуляции и печати в точно таком же порядке, но упрощенно [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] Кроме того, он работает даже тогда, когда корень дерева node не имеет левого дочернего элемента.

Ответ 5

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

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

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;
}

Ответ 6

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

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

  •   
  • SouthWest: вы находитесь на левой стороне края, перейдя от родителя к его левому ребенку.  
  • NorthEast: переход от левого ребенка обратно к родительскому  
  • SouthEast: переход от родителя к правильному ребенку  
  • 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;
        }
    }
}

Ответ 7

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

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

Ответ 8

второстепенный частный случай для ответа iluxa выше

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

Ответ 9

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