查找树中最深的节点 (Lisp)

Question

我想在 lisp 中遍历一棵树，并通过使用列表形式的树找到最深（或离根节点最远）的树。到目前为止，我的想法一直是继续将树切割成左子树和右子树（假设父节点只会有两个儿子，就像在二叉树中一样）我将 post 下面的代码，因为虽然它编译它给我一个 nil 不是真实类型的错误。任何建议都会很棒，甚至可以改进代码！

我在 find the path between nodes 上看到过类似的问题，但还没有真正看到任何关于如何实际将最深的节点打印到屏幕上的有用信息。

感谢观看。

(defun postorder(tree)
 (cond ((null tree) 0)
    ((< (list-length tree) 3) 0)
    (t 
     (append (postorder (left-subtree tree))
        (postorder (right-subtree tree))
        (list (car tree))))))

(defun tree-depth (sub-tree)
 (cond ((null sub-tree) nil)
    ((atom sub-tree) nil)
    (t (+ 1 (max (tree-depth (cadr sub-tree)) (tree-depth (caddr sub-tree)))))))

(defun left-subtree(tree)
 (cond ((null tree) nil)
    ((not (listp tree)) nil)
 (t (car (cdr tree)))))

(defun right-subtree(tree)
 (cond ((null tree) nil)
    ((not (listp tree)) nil)
    (t (car (cdr (cdr tree))))))

(defun split-tree (tree)
 (cond ((null tree) 
    tree)
    ((> (tree-depth (left-subtree tree)) (tree-depth (right-subtree tree)))
       (split-tree (left-subtree tree)))
    ((< (tree-depth (left-subtree tree)) (tree-depth (right-subtree tree)))
       (split-tree (right-subtree tree)))
    ((= (tree-depth (left-subtree tree)) (tree-depth (right-subtree tree)))
       (first (postorder tree)))))

输入将类似于'(1 (2 (4) (6)) (5 (7) (8))))

Answer 1

我只是认为您必须调用 tree-depth 而不是 postorder。虽然答案基本上保持不变：一旦您使用 trace 获取调用树：

(trace tree-depth)

(tree-depth '(1 (2 (4) (6)) (5 (7) (8))))

0: (TREE-DEPTH (1 (2 (4) (6)) (5 (7) (8))))
1: (TREE-DEPTH (2 (4) (6)))
  2: (TREE-DEPTH (4))
    3: (TREE-DEPTH NIL)
    3: TREE-DEPTH returned NIL
    3: (TREE-DEPTH NIL)
    3: TREE-DEPTH returned NIL

因此，您现在得到了两个 tree-depth 递归调用的 return 值，并且都是 nil。但是现在你的代码想要对它们做一个 + 这将导致失败，因为 nil 和 nil 都不是 REAL 类型（正如你的解释器已经告诉你的那样）。因此，如果您想继续使用当前的解决方案，则必须修复递归逻辑以确保处理这种情况。

如果你看一下树的图画，这个修复实际上看起来很直观

lvl             tree
3                1
2       2               5
1    4     6        7       8
0

因此(null subtree)应该return值0。只要您坚持使用所选的树表示，这种情况 (atom subtree) 就永远不会发生。

(defun tree-depth (sub-tree)
 (cond ((null sub-tree) 0)
    (t (+ 1 (max (tree-depth (cadr sub-tree)) (tree-depth (caddr sub-tree)))))))

我认为替代解决方案可能如下所示（短一点）：

(defun find-deepest (tree)
  (reduce #'(lambda(l c)
          (if (> (car c)
                 (car l))
          c
          l))
      (mapcar #'(lambda (node)
              (if (listp node)
              (let ((found (find-deepest node)))
                (cons (+ (car found) 1) (cdr found)))
              (cons 1 node)))
          tree)))

  > (find-deepest '(1 (2 (4) (6)) (5 (7) (8))))
  (3 . 4)

或者如果您只关心值

  > (cdr (find-deepest '(1 (2 (4) (6)) (5 (7) (8)))))
  4

或者如果你只关心深度

  > (car (find-deepest '(1 (2 (4) (6)) (5 (7) (8)))))
  3

Answer 2

这个怎么样？编辑：抱歉，没有看到上面的简短答案。无论如何我都会把它留在这里

(defun tag-and-flatten (tree &optional (depth 0))
  (cond ((null tree) nil)
        ((atom tree) (list (list tree depth)))
        (t (apply #'append (mapcar (lambda (x) (tag-and-flatten x (1+ depth))) tree)))))

(defun find-deepest (tree)
  (caar (sort (tag-and-flatten tree) #'> :key #'second)))

测试

> (find-deepest '(1 (2 (4) (6)) (5 (7) (8))))
4

> (find-deepest '(:a :b ((((:c))) :d)))
:c

查找树中最深的节点 (Lisp)

Finding deepest node in a tree (Lisp)

lisp

tree

common-lisp

tree-traversal

postorder