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

一尘不染

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

algorithm

这不是家庭作业，我不需要回答，但是现在我变得迷恋了:)

问题是：

设计一种算法，以破坏性的方式将二叉树展平为广度优先的链表。好吧，很简单。只需建立一个队列，然后执行您必须要做的。
那是热身。现在，用常量存储实现它（递归，如果您能找到一个答案，它是对数存储，而不是常量）。

大约一年前，我在互联网上找到了解决此问题的方法，但现在我已经忘记了，我想知道:)

据我所记得，这个技巧涉及利用树来实现队列，同时利用算法的破坏性。链接列表时，您还将项目推入队列。

每次尝试解决此问题时，我都会丢失节点（例如，每次将下一个节点链接/添加到队列时），我需要额外的存储空间，或者我无法弄清楚我需要回到的复杂方法具有我需要的指针的节点。

即使是原始文章/帖子的链接对我也将是有用的:) Google并没有给我带来欢乐。

编辑：

Jérémie指出，如果您有一个父指针，则有一个相当简单的答案（众所周知的答案）。虽然我现在认为他对包含父指针的原始解决方案是正确的，但我真的很想解决没有它的问题:)

完善的需求将以下定义用于节点：

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

阅读 261

2020-07-28

共1个答案

一尘不染

想法：

您可以沿着树的左子级建立链接列表。同时，该列表的右子元素用于保留要插入尾部的下一个子树的队列。

伪代码中的算法：

（ 编辑：为清楚起见重写 ）

节点具有三个组成部分：值，对其左子级的引用和对其右子级的引用。引用可以为空。
将此类节点的二叉树转换为单个链表的功能
- 以对根节点的引用作为参数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次迭代（几乎完成）：

实码（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)

;; 这里的内部循环保持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)

2020-07-28