0

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

我在查找节点之间的路径方面看到了类似的问题，但还没有真正看到有关如何将最深节点实际打印到屏幕上的任何有用信息。

感谢您的关注。

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

4

2 回答 2

0

我只是想你必须打电话给tree-depthnot postorder。虽然答案基本保持不变：只要您使用跟踪获取调用树：

(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并且都是nil. 但是现在您的代码想要+对它们进行操作，这将导致失败，因为既不是类型nil也不nil是类型REAL（正如您的解释器已经告诉您的那样）。因此，如果您想继续使用当前的解决方案，您将必须修复您的递归逻辑以确保处理这种情况。

如果您查看树的绘图，该修复实际上看起来很直观

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

因此(null subtree)应该返回值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
于 2015-03-04T00:02:38.577 回答
0

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

(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
于 2015-03-04T13:25:44.227 回答