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

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

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

---

伪代码中的算法：

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

• 节点具有三个组成部分：值，对其左子级的引用和对其右子级的引用。引用可以为空。
• 将此类节点的二叉树转换为单个链表的功能
  • 以对根节点的引用作为参数

    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）

这是节点类：

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