将二叉树转换为链表,宽度优先,常量存储/破坏性

想法:

可以沿着树的左子级构建链接列表。同时,该列表的右子级用于保存要在尾部插入的下一个子树的队列。

伪码算法:

( 编辑:为了清晰起见而重写 )

• 节点有三个组件:一个值、对其左子节点的引用和对其右子节点的引用。引用可以为空。
• 将此类节点的二叉树转换为单个链表的函数。
  • 将对根节点的引用作为参数 root ,
  • 循环,与 tail 从的左子级开始 根 :
    • 交换的左子级 尾 有一个正确的孩子 根 ,
    • 回路 o(n) 队列插入),使用 bubble-to 从开始 根 和 bubble-from 永远是的左撇子 气泡到 ,
      • 交换的右子项 气泡到 和``泡泡的右孩子在一起,
      • 提前 气泡到 和 气泡从 留给他们的孩子们,
      • 直到 气泡从 到达 尾 ,
    • 提前 尾 它左边的孩子,
    • 虽然 尾 不是空的。
  • 最后,返回 head . 现在,单个链接列表沿左子项运行。

插图

开始树(我认为它应该是一个完整的树;如果缺少节点,它们应该从最后开始。你可以试着给其他情况赋予意义,但有几种不同的可能性,而且这涉及到很多麻烦):

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

请注意,这些值不一定是节点的值,它们只是为了显示而编号。

一次迭代后的树(注意列表的形成 1 到 3 子树的队列 4 和 5 ):

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

经过3次迭代(列表现在 一 到 五 ,并且队列包含根目录树 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)

这是节点类:

(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)

这里的内环 头 在尚未形成的子树根部,
;;即第一个分支的节点,
同时从根部向左侧熨烫。
它结束了 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)

就记录而言,递归版本很漂亮(这是C):

[编辑:正如st0le指出的,我的第一个版本包含“新的”!原谅我,过去20年我一直用声明性语言编写代码。这是正确的版本。]

[编辑:两只老鼠。这不是宽度优先。]

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

首先,我假设您的节点有一个指向其父节点的“父”字段。或者您需要一个堆栈才能在树中向后移动(因此无法实现O(1)辅助内存需求)。

在O(1)空间中有一个众所周知的有序迭代。例如,假设您希望按顺序打印项目。基本上,当您遍历一个二叉树时,您必须在任何给定的时刻,在任何给定的节点中,决定是否要向上(向父节点)、向左(向左子节点)或向右移动。这个算法的想法是基于你来自哪里:

1. 如果您是从父节点下来的,那么很明显您是第一次访问节点,所以您向左走;
2. 如果您是从左边的子节点上来的,那么您已经访问了所有小于当前节点的节点,所以您可以打印(记住,我们要在这里按顺序打印节点)当前节点,然后向右;
3. 最后,如果您来自正确的子节点,这意味着您已经访问了这个特定节点上的整个子树,因此您可以备份到父节点。

好的:所以这是你拿它作为基础的算法。现在,很明显,如果您正在将其破坏性地修改为一个链接列表,那么您应该只在不再访问节点时修改它。那是你从右边上来的时候。此时,您必须决定该节点的后续节点将是什么…?

嗯,您需要随时跟踪两个指针:一个指向您访问过的最小节点,另一个指向您在当前根子树中访问过的最大节点。当您从正确的子节点访问时,您使用最小的节点作为上一次访问的节点的后续节点,并使用最大的节点作为上一次访问从其他位置访问的节点的后续节点,因为它们恰好没有正确的子节点!

编辑1 :我忘了说,我隐式地认为二进制树中的“parent”字段成为链接列表中的“next”字段——这是我在最后一步中修改的内容。

编辑3 :我的答案的以下部分并没有完全回答最初的问题(但前面的内容仍然相关)。

编辑2 :遵循Svante的可理解的愿望,我明确了将左旋转用于某些代码的建议:

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

旋转函数并不优雅,但由于很容易混淆,我尝试使用与中使用的完全相同的命名。 Wikipedia's article on rotations . 在我的代码中,节点a、b、c是这样命名的;节点p和q不是,因为我选择不使用指针指针,所以我使用了转换p和q值的技巧--in 代替 转换位置。使用“旋转权”,转换算法非常简单:

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

好吧,我现在还不太清楚这在这种情况下有什么帮助,但它可能会给你一个线索。有一种称为“指针反转”的技术用于迭代遍历树,而无需使用堆栈/队列来存储指针——它主要用于低内存开销的垃圾收集器。其背后的想法是,当您遍历到节点的子节点时,您将指向该子节点的指针链接回父节点,这样,当您完成该节点时,您就知道返回到何处。这样,通常保存在堆栈/队列中的回溯信息现在嵌入到树本身中。

我发现了以下内容 slideshow 举个例子(不幸的是,谷歌没有更好的东西)。这里的例子展示了如何在没有额外存储的情况下遍历二叉树。

我认为我们不需要父母指点。假设0到k-1级加上一个sentinel节点被转换为左子指针上的单个链接列表,右子指针指向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代码:

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

关于这个解决方案

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

有一个简单的Java实现与所描述的第一种方法。

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

这是我对这个问题的看法;

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