Построение двоичного дерева из списка (preorder)

Question

Интересный вопрос, который я натолкнул на несколько дней назад: есть ли элегантное функциональное программирующее решение для сборки двоичного дерева с меткой узла из списка?

Полученное дерево должно быть сбалансированным слева, то есть каждый уровень узлов в дереве должен быть заполнен полностью или, в случае наименьшего, заполнен слева направо. Кроме того, обход уровня на дереве (то есть сверху вниз, слева направо) должен содержать исходный список.

Пример: список 1,2,3,4,5 должно привести к

  1 
    2   3 
4 5 

Очевидное решение заключается в преобразовании списка в массив, присвоить значение нулевое к корню, а затем, рекурсивно , для узла n, дайте детям значения 2n+1 и 2n+2.

Но мне было интересно: есть ли более «функциональный» способ, который не требует вспомогательного массива?

Answer 1

Мысли выражаются в схеме rsr5

Мои первые мысли предполагает бесконечное дерево, узлы которого являются функции, которые принимают значение и дерево и вставить это значение в этом дереве в том же месте, функция найдена. Затем вы можете сделать fold2 как рекурсию над списком и поперечную трансляцию уровня дерева функций, применяя последовательную функцию к последующим элементам списка, чтобы накапливать двоичное дерево. (Только работает с ленивой оценкой, хотя)

Казалось немного громоздким, хотя я пересмотрел эту мысль до дерева данных, которое можно было подавать на функцию типа ('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 является главой дерева. В противном случае, если это нечетно, это правильная ветвь узла. Если это даже левая ветка. Индекс его родителя всегда представляет собой пол ребенка, разделенный на два. Из этого знания вы можете создать вставку или аксессуар с просто индексом.

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

Конечно, самый простой способ, если вы можете принять минимальную глубину бинарного дерево. Дерево глубины отображает минимальную глубину в дополнение к своим узлам и ветвям. Вставка затем будет вставляться в левое поддерево, если минимальная глубина правого поддерева меньше, чем у левой.

(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; используйте минимальное дерево глубины и вставьте самую левую минимальную глубину.