将二叉树转换为链表,广度优先,恒定存储/破坏性

Question

这不是功课,我不需要回答它,但现在我已经变得痴迷:)

问题是:

• 设计一种算法,将二叉树破坏性地展平为链表,广度优先.好的,够容易的.只需构建一个队列,并做你需要做的事情.
• 那是热身.现在,使用常量存储实现它(递归,如果你能用它来找出答案,那就是对数存储,而不是常数).

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

据我记忆,这个技巧涉及使用树来实现队列,利用算法的破坏性.链接列表时,您还将项目推入队列.

每次我尝试解决这个问题,我都会丢失节点(比如每次我链接下一个节点/添加到队列中),我需要额外的存储空间,或者我无法弄清楚我需要回到一个复杂的方法具有我需要的指针的节点.

即使链接到原始文章/帖子对我也很有用:)谷歌没有给我带来快乐.

编辑:

Jérémie指出,如果你有一个父指针,有一个相当简单(和众所周知的答案).虽然我现在认为他对包含父指针的原始解决方案是正确的,但我真的想在没有它的情况下解决问题:)

精炼的需求将此定义用于节点:

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

Answer 1

想法:

您可以沿树的左侧子项构建链接列表.同时,该列表的正确子节点用于保存下一个子树的队列以插入尾部.

伪代码中的算法:

(编辑:为清楚起见重写)

• 节点有三个组件:值,对其左子节点的引用以及对其右子节点的引用.引用可以为null.
• 将此类节点的二叉树转换为单个链接列表的功能
  • 将根节点的引用作为参数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其左子,
    • 虽然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)

Answer 2

只是为了记录,递归版本很漂亮(这是在C#中):

[编辑:正如st0le指出的那样,我的第一个版本包含'新的!请原谅我,过去二十年我一直在用声明性语言编写代码.这是更正后的版本.]

[编辑:双鼠.这不是第一个广度.]

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