Преобразование двоичного дерева в связанный список, сначала широта, постоянное хранение / деструктивное

Прежде всего, я предполагаю, что у ваших узлов есть «родительское» поле, которое указывает на их родительский элемент.Либо так, либо вам нужен стек, чтобы иметь возможность перемещаться вверх по дереву (и, таким образом, не удается достичь этого требования к вспомогательной памяти O (1)).

Существует хорошо известная итерация по порядку, которая является итеративной и находится в пространстве O (1). Предположим, например, что вы хотите распечатать элементы по порядку. По сути, когда вы проходите по бинарному дереву, вы должны решить в любой момент в любом заданном узле, хотите ли вы переместиться ВВЕРХ (к родительскому элементу), ВЛЕВО (к левому дочернему элементу) или ВПРАВО. Идея этого алгоритма состоит в том, чтобы основывать это решение на том, откуда вы пришли:

1. если вы спускаетесь от родителя, то очевидно, что вы посещаете узел впервые, поэтому вы идете ВЛЕВО;
2. если вы приходите вверх от левого дочернего элемента, то вы посетили все узлы, которые меньше текущего узла, так что вы можете распечатать (помните, мы хотим распечатать узлы по порядку здесь) текущий узел, а затем перейти ВПРАВО;
3. наконец, если вы переходите от правильного дочернего элемента, это означает, что вы посетили все поддерево, имеющее корень в этом конкретном узле, и поэтому вы можете вернуться к родительскому элементу UP.

Хорошо: это алгоритм, который вы берете за основу. Теперь ясно, что если вы деструктивно модифицируете его в связанный список, вам следует изменять узел только тогда, когда вы больше не собираетесь его посещать. Это когда вы подходите справа. В этот момент вы должны решить, каким будет преемник этого узла ...?

Ну, вам нужно постоянно отслеживать два указателя: один на наименьший узел, который вы посетили, и один для самого большого узла, который вы посетили в текущем корневом поддереве.Вы используете наименьший в качестве преемника для узлов, которые вы в последний раз посещали, когда вы переходите от правильного дочернего элемента, и используете наибольший в качестве преемника для узлов, которые вы в последний раз посещали, пришедших откуда-то еще, потому что у них нет правильного дочернего элемента!

РЕДАКТИРОВАТЬ 1 : Я забыл сказать, что я неявно считаю, что «родительское» поле в двоичном дереве становится «следующим» полем в связанном списке - это то, что я изменяю на последнем шаге.

РЕДАКТИРОВАТЬ 3 : Оказалось, что следующая часть моего ответа не совсем отвечает на исходный вопрос (но то, что было сказано выше, все еще актуально).

РЕДАКТИРОВАТЬ 2 : Следуя понятному желанию Сванте, я выразил свое предложение об использовании левого поворота в некотором коде:

#include <stdlib.h>
#include <stdio.h>

typedef struct node *node;

struct node
{
  int value;
  node left;
  node right;
};

node new_node(int value, node left, node right)
{
    node n = (node) malloc(sizeof(struct node));
    n->value = value; n->left = left; n->right = right;
    return n;
}

int rotate_right(node tree)
{
    if(tree != NULL && tree->left != NULL)
    {
        node
            a = tree->left->left,
            b = tree->left->right,
            c = tree->right;
        int tmp = tree->value;
        tree->value = tree->left->value;
        tree->left->value = tmp;

        tree->left->left = b;
        tree->left->right = c;
        tree->right = tree->left;

        tree->left = a;
        return 1;
    }
    return 0;
}

Функция вращения не изящна, но, поскольку ее легко запутать, я попытался следовать точно такое же название, как в статье Википедии о вращениях . Узлы A, B, C названы так в моем коде; узлы P и Q не являются, и поскольку я решил не использовать указатели указателей, я вместо этого прибег к уловке переключения значений P и Q --- в вместо переключения мест. При наличии в нашем распоряжении «rotation_right» алгоритм преобразования довольно прост:

void convert_to_list(node tree)
{
    if(tree != NULL) {
        while(rotate_right(tree) != 0);
        convert_to_list(tree->right);
    }
}

Результирующее дерево представляет собой отсортированный связанный список, где указатель next списка - это то, что раньше было правый указатель в дереве. Наконец, вот тестовая программа:

int main()
{
    node t =
        new_node(4,
              new_node(2, NULL, new_node(3, NULL, NULL)),
              new_node(8, new_node(5, NULL, NULL), NULL));
    convert_to_list(t);
    for(; t != NULL; t = t->right)
        printf("%d, ", t->value);
    return 0;
}

Что ж, сейчас я не могу понять, как это помогает в этой ситуации, но это может дать вы ведущий. Существует метод, называемый «обращением указателя», используемый для итеративного обхода дерева без необходимости использования стека / очереди для хранения указателей - он в основном использовался для сборщиков мусора с малыми накладными расходами памяти. Идея, лежащая в основе этого, заключается в том, что, когда вы переходите к дочернему узлу, вы связываете этот указатель на дочерний элемент обратно с родительским, чтобы вы знали, куда вернуться, когда вы закончите с этим узлом. Таким образом, информация трассировки, которую вы обычно храните в стеке / очереди, теперь встроена в само дерево.

Я нашел следующее слайд-шоу с примером (к сожалению, в Google нет ничего лучше). В приведенном здесь примере показано, как пройти по двоичному дереву без дополнительной памяти.

Я не думаю, что нам нужны родительские указатели.Предположим индуктивно, что уровни от 0 до k-1 плюс контрольный узел были преобразованы в односвязный список на левых дочерних указателях, правые потомки которых указывают на узлы уровня k. Пройдитесь по списку, по очереди захватывая каждый «правый дочерний элемент» (узел уровня k) и вставляя его в конец списка, перезаписывая правый указатель, из которого он пришел, своим левым дочерним элементом, который скоро будет перезаписан. Когда мы достигли начального конца списка, мы расширили индуктивную гипотезу до k + 1.

РЕДАКТИРОВАТЬ: код

#include <cstdio>

struct TreeNode {
  int value;
  TreeNode *left;
  TreeNode *right;
};

// for simplicity, complete binary trees with 2^k - 1 nodes only
void Flatten(TreeNode *root) {
  TreeNode sentinel;
  sentinel.right = root;
  TreeNode *tail = &sentinel;
  while (true) {
    TreeNode *p = &sentinel;
    TreeNode *old_tail = tail;
    while (true) {
      if ((tail->left = p->right) == NULL) {
        return;
      }
      tail = p->right;
      p->right = p->right->left;
      if (p == old_tail) {
        break;
      }
      p = p->left;
    }
  }
}

int main() {
  const int n = 31;
  static TreeNode node[1 + n];
  for (int i = 1; i <= n; ++i) {
    node[i].value = i;
    if (i % 2 == 0) {
      node[i / 2].left = &node[i];
    } else {
      node[i / 2].right = &node[i];
    }
  }
  Flatten(&node[1]);
  for (TreeNode *p = &node[1]; p != NULL; p = p->left) {
    printf("%3d", p->value);
  }
  printf("\n");
}

Для записи, рекурсивная версия прекрасна (это на C #):

[Отредактировано: как указывает st0le, моя первая версия содержит новые! Простите меня, последние двадцать лет я кодил на декларативных языках. Вот исправленная версия.]

[Edit: двойные крысы. Это не в первую очередь.]

public static Tree<T> Flatten(Tree<T> t, Tree<T> u = null)
{
    if (t == null) return u;
    t.R = Flatten(t.L, Flatten(t.R, u));
    t.L = null;
    return t;
}

Это мой ответ, который работает. Теперь я понимаю, что это тот же подход, что и решение Сванте(!), хотя я строю дерево справа.

Для протокола, вот код на C#:

// Flatten a tree into place in BFS order using O(1) space and O(n) time.
// Here is an example of the transformation (the top-row indicates the
// flattened parts of the tree.
//  
//  a
//  |---.
//  b   c
//  |-. |-.
//  d e f g
//  
//  becomes
//  
//  a-b-c
//  | | |-.
//  d e f g
//  
//  becomes
//  
//  a-b-c-d-e-f-g
//  
public static void FlattenBFS(Tree<T> t)
{
    var a = t; // We "append" newly flattened vertices after 'a'.
    var done = (t == null);
    while (!done)
    {
        done = true;
        var z = a; // This is the last vertex in the flattened part of the tree.
        var i = t;
        while (true)
        {
            if (i.L != null)
            {
                var iL = i.L;
                var iLL = iL.L;
                var iLR = iL.R;
                var aR = a.R;
                i.L = iLL;
                a.R = iL;
                iL.L = iLR;
                iL.R = aR;
                a = iL;
                done &= (iLL == null) & (iLR == null);
            }
            if (i == z)
            {
                break; // We've flattened this level of the tree.
            }
            i = i.R;
        }
        a = (a.R ?? a); // The a.R item should also be considered flattened.
    }
}