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

Это не домашнее задание, и мне не нужно отвечать на него, но теперь я стал одержим:)

Проблема заключается в следующем:

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

Я нашел решение этой проблемы в Интернете около года назад, но теперь я забыл об этом, и я хочу знать:)

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

Каждый раз, когда я пытаюсь решить эту проблему, я теряю узлы (например, каждый раз, когда я связываю следующий node/add в очередь), мне требуется дополнительное хранилище, или я не могу определить запутанный метод, который мне нужен чтобы вернуться к node, у которого есть указатель, который мне нужен.

Даже ссылка на эту оригинальную статью/сообщение была бы полезной для меня:) Google не дает мне радости.

Edit:

Jérémie указала, что существует довольно простой (и хорошо известный ответ), если у вас есть родительский указатель. Хотя теперь я думаю, что он прав относительно исходного решения, содержащего родительский указатель, я действительно хотел решить проблему без него:)

Уточненные требования используют это определение для node:

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

Ответы

Ответ 1

Идея:

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

Алгоритм в псевдокоде:

(отредактируйте: переписано для ясности)

  • A node имеет три компонента: значение, ссылку на его левое дочернее устройство и ссылку на его правый дочерний элемент. Ссылки могут быть пустыми.
  • Функция преобразования двоичного дерева таких узлов в один связанный список
    • ссылается на корень node как параметр root,
    • с tail, начиная с левого дочернего элемента root:
      • замените левый дочерний элемент tail на правый дочерний элемент root,
      • цикл (O (n)), при bubble-to начиная с root и bubble-from всегда левого дочернего элемента bubble-to,
        • замените правый дочерний элемент bubble-to на правый дочерний элемент'bubble-from`,
        • вперед bubble-to и bubble-from к их левым дочерним элементам,
        • до bubble-from достигает tail,
      • перейти tail к его левому дочернему элементу,
      • while tail не является нулевым.
    • Наконец, верните head. Единый связанный список теперь выполняется вдоль левых детей.

Иллюстрация

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

              1
          /       \
      2               3
    /   \           /   \
  4       5       6       7
 / \     / \     / \     / \
8   9   A   B   C   D   E   F

Обратите внимание, что это не обязательно значения узлов, они просто нумеруются для целей показа.

Дерево после 1-й итерации (обратите внимание, что список формируется от 1 до 3 и очередь поддеревьев, корневых в 4 и 5):

                head
                  v
                  1
               /    \
    tail    2         4
      v  /    \      / \
      3         5   8   9
    /   \      / \
  6       7   A   B
 / \     / \
C   D   E   F

после 3 итераций (теперь список 1 - 5, а очередь содержит поддеревья, корневые в 6 - 9):

                   head
                     v
                     1
                  /     \
               2          6
             /   \       / \
           3       7    C   D
          / \     / \
         4   8   E   F
        / \
tail > 5   9
      / \
     A   B

и после 8 итераций (почти сделано):

                       head
                         v
                         1
                        / \
                       2   B
                      / \
                     3   C
                    / \
                   4   D
                  / \
                 5   E
                / \
               6   F
              /
             7
            /
           8
          /
         9
        /
tail > A

Реальный код (Lisp)

Это класс node:

(defclass node ()
  ((left :accessor left)
   (right :accessor right)
   (value :accessor value)))

Полезный помощник:

(defmacro swap (a b)
  `(psetf ,a ,b
          ,b ,a))

Функция преобразования (отредактируйте: переписано для ясности):

(defun flatten-complete-tree (root)
  (loop for tail = (and root (left root)) then (left tail)
        while tail
        do (swap (left tail) (right root))
           (loop for bubble-to = root then (left bubble-to)
                 for bubble-from = (left bubble-to)
                 until (eq bubble-from tail)
                 do (swap (right bubble-to) (right bubble-from))))
  root)

Необратимая операция для зубчатых деревьев:

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

(defun flatten-tree (root)

;; Внутренний цикл здесь держится head в корне все еще незакрепленного поддерева,
;; т.е. node первой ветки,
;; в то же время гладя все от корневых неразветвленных уровней влево.
;; Он заканчивается nil, когда дерево полностью сплющено.

  (loop for head = (loop for x = (or head root) then (left x)
                         do (when (and x (null (left x)))
                              (swap (left x) (right x)))
                         until (or (null x) (right x))
                         finally (return x))
        for tail = (and head (left head)) then (left tail)
        while head
        do (swap (left tail) (right head))

;; Этот внутренний цикл представляет собой установку очереди O (n)

           (loop for bubble-to = head then (left bubble-to)
                 for bubble-from = (left bubble-to)
                 until (eq bubble-from tail)
                 do (swap (right bubble-to) (right bubble-from))))

;; Наконец, верните исходный корень.

  root)

Ответ 2

Только для записи рекурсивная версия красива (это в С#):

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

[Редактировать: двойные крысы. Это не первый раз.]

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

Ответ 3

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

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

  • если вы спуститесь с родителя, то ясно, что вы впервые посещаете node, поэтому вы идете влево,
  • если вы выходите из левого дочернего элемента, то вы посетили все узлы, которые меньше текущего node, поэтому вы можете печатать (помните, что мы хотим напечатать узлы в порядке) текущего node и затем перейдите к RIGHT;
  • Наконец, если вы выйдете из правильного дочернего элемента, это означает, что вы посетили все поддеревья, внедренные в этот конкретный node, и поэтому вы можете вернуть UP к родительскому объекту.

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

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

РЕДАКТИРОВАТЬ 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);
    }
}

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

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

Ответ 4

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

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

Ответ 5

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

EDIT: код

#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");
}

Ответ 6

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

Для записи здесь приведен код С#:

// 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.
    }
}

Ответ 7

Ват об этом решении

temp=root;
struct node*getleftmost(struct node* somenode)
{
   while(somenode->left)
   somenode=somenode->left;
   return somenode;
}

 while(temp)
 {
 if(temp->right){
 (getletfmost(temp))->left=temp->right;
 temp->right=NULL;}
 temp=temp->left;
 }

Ответ 9

Вот мое приложение к проблеме;

struct TreeNode
{
    TreeNode(int in) : data(in)
    {
        left = nullptr;
        right = nullptr;
    }
    int data;
    TreeNode* left;
    TreeNode* right;
};


//Converts left pointer to prev , right pointer to next
// A tree which is like              5 
//                                 11  12

//will be converted to double linked list like 5 -> 12 -> 11 
void finalize(TreeNode* current, TreeNode* parent)
{
    if (parent == nullptr)
    {
        current->left = nullptr;
        return;
    }

    if (parent->left == current)
    {
        if (parent->right == nullptr)
        {
            parent->right = current;
            current->left = parent;
        }
        current->left = parent->right;
    }
    else
    {
        current->left = parent;
        parent->right = current;
        current->right = parent->left;
    }
}


void traverser(TreeNode* current, TreeNode* parent)
{
    if (current->left != nullptr)
        traverser(current->left, current);
    if (current->right != nullptr)
        traverser(current->right, current);

    finalize(current, parent);
}

void start(TreeNode* head)
{
    if (head == nullptr || (head->left == nullptr && head->right == nullptr))
        return;

    traverser(head, nullptr);
}


int main()
{
    TreeNode* n1 = new TreeNode(5);
    TreeNode* n2 = new TreeNode(11);
    TreeNode* n3 = new TreeNode(12);



    n1->left = n2;
    n1->right = n3;

    start(n1);
}