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

Question

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

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

Проблема в:

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

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

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

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

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

Редактировать:

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

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

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

18

algorithm tree binary-tree

Источник

user232593 05 авг '10 в 04:40

9 ответов

Решение

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

[Отредактировано: как указывает 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;
}

5

Источник

user398575 06 авг '10 в 03:50

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

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

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

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

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

РЕДАКТИРОВАТЬ 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--- вместо мест переключения. Имея в своем распоряжении "вращение_право", алгоритм конвертации довольно прост:

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

2

Источник

user408734 05 авг '10 в 05:18

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

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

1

Источник

user329855 05 авг '10 в 05:48

Я не думаю, что нам нужны родительские указатели. Предположим индуктивно, что уровни от 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");
}

0

Источник

user382751 05 авг '10 в 05:54

Существует простая реализация Java с первым описанным методом.

http://www.dsalgo.com/BinaryTreeToLinkedList.php

0

Источник

user2025494 30 янв '13 в 13:23

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

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

0

Источник

user1268779 24 авг '12 в 17:05

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

Для записи вот код 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.
    }
}

0

Источник

user398575 08 авг '10 в 00:41

Вот мой подход к проблеме;

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

0

Источник

user1745372 30 ноя '14 в 11:54

Другие вопросы по тегам algorithm tree binary-tree

user31615 05 авг '10 в 12:13 2010-08-05 12:13 · Accepted Answer · 2010-08-05 12:13

Идея:

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

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

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

Узел имеет три компонента: значение, ссылку на его левый дочерний элемент и ссылку на его правый дочерний элемент. Ссылки могут быть нулевыми.
Функция для преобразования двоичного дерева таких узлов в единый связанный список
- принимает ссылку на корневой узел в качестве параметра root,
- петли, с tail начиная с левого ребенка root:
  - поменять местами левого ребенка tail с правильным ребенком root,
  - цикл (O(n) вставка очереди), с bubble-to начиная с root а также bubble-from всегда левый ребенок bubble-to,
    - поменять правильное дитя bubble-to с правильным ребенком "пузырёк",
    - продвижение bubble-to а также bubble-from своим оставленным детям,
    - до тех пор bubble-from достигает tail,
  - продвижение tail своему левому ребенку,
  - в то время как 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 итераций (почти сделано):

Реальный код (Лисп)

Это класс узла:

(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 в корне еще не раскрытого поддерева,
;; то есть узел первой ветви,
;; в то же время гладя все от корневых неразветвленных уровней влево.
;; Это заканчивается 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)