Обход дерева по уровням (сначала ширина) в Лиспе

Question

Я пытаюсь распечатать в порядке уровня дерево с общим Lisp.

Список равен (1 (2 4 (5 (8 11)) 6) (3 (7 9 10))), что означает, что дерево упорядочено:

1. 1
2. 2 3
3. 4 5 6 7
4. 8 9 10
5. 11

Здесьэто быстрый макет дерева:

Я пытаюсь напечатать это дерево в этом порядке, выполнив поиск в ширину.

То, о чем я здесь думал, это то, что я просто должен был бы car и cdr пройти через это дерево, но у меня были огромные проблемы, чтобы понять, как именно.Вот именно то, что я пробовал в полупсевдокоде.

(defun traverse (*cur-level*)
  (print (car *cur-level*)) ; print out the first element of the current level
    (if (cdr *cur-level*) ; if cdr of next level is not nil
      (setq *next-level* (cdr *cur-level*) ;set that to be the next level
      (traverse *next-level*)) ; recursively call until all levels traversed. 
                               ; else, simply do not do anything and terminate
                               ; the function.

Проходя по дереву самостоятельно, я обнаружил, что во втором цикле этот алгоритм ломается, потому что

;first loop
(car *cur-level) = 1
(cdr *cur-level*)=((2 4 (5 (8 11)) 6) (3 (7 9 10)), 

, поэтому в следующем цикле

;second loop
(car *cur-level*) = (2 4 (5 (8 11)) 6)
(cdr *cur-level*) = (3 (7 9 10))

Это означает, что дерево по существу разделяется, и (2 4 (5 (8 11)) 6) игнорируется.

Кроме того, в том же цикле(car cur-level) - это не отдельный элемент, а список.Это значит, что мне нужно сделать:

;still second loop
(car (car *cur-level*) = 2
(cdr (car *cur-level*) = (4 (5 (8 11)) 6)

Поэтому я попытался включить условие, которое проверяет размер уровня:

(if (> (list-length (car *cur-level*)) 1)
  (print (car (car *cur-level*))
  (setq *next-level* (cdr (car *cur-level*))

Но это не исправляет тот факт, что (3 (7 9 10)отделен от дерева, что означает, что порядок печатается неправильно, и у меня возникает ощущение, что я исправляю проблему, относящуюся только к этому дереву, вместо того, чтобы иметь правильный алгоритм.

Примечание: эта проблема возникает дважды, один раз во втором цикле и еще раз в четвертом цикле левой стороны дерева (где (car cur-level) = (5 (8 11))).

Как я могу это сделатьправильно?Я действительно застрял здесь и понятия не имею, как продолжить.

Answer 1

Это почти копия этого вопроса : для любого вида обхода дерева в ширину, с которым вы работаете, используя повестку дня . мой ответ на предыдущий вопрос дает череду все более изощренных подходов к этой проблеме, начиная с простодушной листовой повестки дня и заканчивая тем, что показывая, что если вы поменяетесь в различных структурах повестки дня, вы можете сделатьразличные виды поиска, в том числе по ширине и глубине, с одним и тем же кодом.

Прежде всего абстрактная древовидная структура : это уже 1970-е годы, и нам не нужен код, которыйполна car & cdr, когда это означает что-то еще.Ваше дерево на самом деле имеет несколько нерегулярную структуру, поскольку узлы могут быть константами (value. Children) или просто необработанными значениями:

(defun tree-node-value (node)
  ;; a node is either (value . children) or value
  (typecase node
    (cons
     (car node))
    (t node)))

(defun tree-node-children (node)
  ;; a node only has children if it is a cons
  (typecase node
    (cons
     (cdr node))
    (t '())))

(defun make-tree-node (value children)
  ;; only make consy nodes
  (cons value children))

Я не удосужился создать компоновщик, но я просто определюваше примерное дерево:

(defparameter *sample-tree* '(1 (2 4 (5 (8 11)) 6) (3 (7 9 10))))

А теперь вот реализация функции, которая будет проходить посетителя по деревьям в порядке ширины, используя простую повестку дня со списком:

(defun walk-tree/breadth-first (tree visitor)
  ;; walk over a tree breadth-first, calling visitor on each node's
  ;; value, using an agenda represented explicitly as a list.
  (labels ((walk (agenda)
             (when (not (null agenda))
               ;; there is more to do
               (destructuring-bind (this . next) agenda
                 ;; call the visitor
                 (funcall visitor (tree-node-value this))
                 ;; and continue with the extended agenda
                 (walk (append next (tree-node-children this)))))))
    (walk (list tree))
    (values)))

И мы можем вызвать это в вашем дереве, используя print в качестве посетителя:

> (walk-tree/breadth-first *sample-tree* #'print)

1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 

Я бы посоветовал вам взглянуть на другие реализации в более старом ответе, в частности явно итеративные..

Answer 2

Я думаю, что в вашем исходном коде вы пытаетесь сделать это:

(defun traverse (cur-level)
  (print (car cur-level)) ;print out the first element of the current level
  (when (cdr cur-level) ;if cdr of next level is not nil
    (setq next-level (cdr cur-level)) ;set that to be the next level
    (traverse next-level)))

Я думаю, что ваше представление дерева можно улучшить, убедившись, что все дочерние узлы являются списками,

, какИтак: (1 (2 (4) (5 (8 (11))) (6)) (3 (7 (9) (10)))))

(defun traverse2 (children)
  (when children
    (print (mapcar 'car children)) 
    (traverse2 (apply 'append (mapcar 'cdr children)))))

(defun traverse (tree)
  (print (car tree))
  (traverse2 (cdr tree)))

Попробуйте запустить этот код здесь .

Я не могу обобщить это так много, потому что я незнаком с Common Lisp, но надеюсьэто помогает.

Редактировать : дальнейшее объяснение

Помните, что входная информация для traverse2 всегда будет списком дочерних узлов(которые сами по себе являются списками)

С этого момента я буду ссылаться на этот входной список дочерних узлов, поскольку input

1. mapcar 'car получает первый элемент каждого дочернего узла в input
2. mapcar 'cdr получает все остальные элементы, кроме первого элемента каждого дочернего узла в input

Теперь проблема с шагом 2 заключается в том, что в отличие от car, который появляетсяхороший элемент, не являющийся списком (в данном случае), cdr дает мне список

Итак, список лиsts (или список дочерних узлов) теперь преобразуется в список списков списков (или список списков дочерних узлов)

apply 'append объединяет этот список списков в один список (или список списков дочерних узлов в список дочерних узлов)

отложеновывод 2 (список списков || список дочерних узлов) в traverse2