从列表构建二叉树（预排序）

Question

我几天前遇到的一个有趣的问题：是否有一种优雅的函数式编程解决方案可以从列表构建（节点标记的）二叉树？

生成的树应该是左平衡的，即树中的每一级节点都应该完全填充，或者在最低的节点的情况下，从左到右填充。此外，树的级别顺序遍历（即从上到下，从左到右）应该给出原始列表。

示例：列表 1,2,3,4,5 应导致

          1
    2         3
 4    5

显而易见的解决方案是将列表转换为数组，将第零个值分配给根，然后递归地，对于节点 n，为子节点提供值 2n+1 和 2n+2.

但是我想知道：有没有更多的"functional"不需要辅助数组的方式？

Answer 1

用rsr5方案表达的想法

我最初的想法涉及一棵无限树，它的节点是接受一个值的函数和一棵树，并将该值插入到该树中找到该函数的同一位置。然后，您可以对列表执行类似于 fold2 的递归，并对函数树进行 level-oder 遍历，将连续函数应用于连续列表元素以累积二叉树。（虽然只适用于惰性评估）

虽然看起来有点笨拙，但我将想法修改为数据树，可以将其馈送到函数（'l'r'l）或可以告诉在哪里插入和索引的东西。

(define (insert-new ls-and-rs tree)
  (cond ((or (empty-tree?) (null? ls-and-rs))
         (if (and (empty-tree?) (null? ls-and-rs))
             (make-tree x emptyTree emptyTree)
             (error "insert-new can only insert at emptyree")))
        ((sybol=? (car ls-and-rs) 'l)
         (make-tree (node tree) 
                    (insert-new (cdr ls-and-rs) 
                                (left-tree tree)) 
                    (right-tree tree)))
        ((sybol=? (car ls-and-rs) 'r)
         (make-tree (node tree) 
                    (left-tree tree) 
                    (insert-new (cdr ls-and-rs) 
                                (right-tree tree))))
        (else (error "insert-new expected 'l or 'r, recieved " 
                     (car ls-and-rs))))))

然后我看到您可以从索引本身构建它。如果 1 是树的头部，则为索引。否则，如果它是奇数，则它是节点的右分支。如果它甚至是左分支。它的 parent 的索引总是 child 的底数除以二。根据这些知识，您可以构建仅具有索引的插入器或访问器。

(define (branch-order i)
  (let loop ((i i) (accum '()))
    (cond ((i = 1) accum)
          ((odd? i) (loop (quotient i 2) (cons 'r accum)))
          (else     (loop (quotient i 2) (cons 'l accum))))))

从那里是一个简单的递归

 (define (list->tree list)
   (let loop ((list list) (i 1) (tree emptyTree))
     (cond ((null? list) tree)
           (else (loop (cdr list)
                       (+ i 1)
                       (insert-new (branch-order i) tree))))))

当然最简单的方法是如果你能接受一个minimum-depth二叉树。除了节点和分支之外，深度树还列出了它的最小深度。然后插入将插入左侧 sub-tree 除非右侧的最小深度 sub-tree 小于左侧的最小深度。

(define (list->d-tree list)
  (fold-left (flip balanced-insert) emptyTree list))

(define (balanced-insert x d-tree)
  (cond ((= 0 (d-d-tree d-tree)) 
        (mk-d-tree x emptyTree emptyTree)
       ((= 1 (- (d-d-tree d-tree) (d-d-tree (l-d-tree d-tree))))
        (mk-d-tree (n-d-tree d-tree)
                   (balanced-insert x (l-d-tree d-tree))
                   (r-d-tree d-dtree)))
      (else 
       (mk-d-tree (n-d-tree d-tree)
                  (l-d-tree d-tree)
                  (balanced-insert x (r-d-tree d-dtree))))))

(define (mk-d-tree n l r)
 (let ((d-l (d-d-tree l))
       (d-r (d-d-tree r)))
 (list n l r (+ 1 (min d-l d-r)))))
(define (n-d-tree d-tree)
 (car d-tree))
(define (l-d-tree d-tree)
 (cadr d-tree))
(define (r-d-tree d-tree)
 (caddr d-tree))
(define (d-d-tree d-tree)
 (if emptyTree? d-tree)
     0
     (cadddr d-tree)))
(define (emptyTree? tree)
       (null? tree))
(define emptyTree '())

(define (flip f)
 (lambda (a b)
   (f b a)))

TLdr；使用最小深度树并插入到最左边的最小深度。

从列表构建二叉树（预排序）

Building a binary tree from a list (preorder)

tree

functional-programming

preorder