使用搜索找到树中最深的节点，然后移动它
Using search to find the deepest node in a tree and then moving it
我有一棵树，我想找到到最深节点的最长路径，然后我想以某种方式更改它以使其更加平衡。在这个非常简单的示例中，我想移动 4，因为它是最深的路径，而不是将它放在 1 中，这样高度差异就不会那么大。我想在 lisp 中执行此操作，但我不太确定如何，我知道我想使用搜索但它有它，所以它实际上确实找到了最长的。我知道如何获得从根到给定节点的路径，但我不确定如何真正获得最深的节点。我想我有一个关于如何将最深的节点放在更好的部分上的想法，但任何建议都会很棒。
到目前为止，我只有一些代码可以 return 树的深度，但是我可以通过任何方式得到它 return 最深的节点是什么)?
(defun maxdepth (l)
(cond ((null l) 0)
((atom l) 0)
(t (+ 1 (max (maxdepth (cadr l)) (maxdepth (caddr l)))))))
您可以使用深度优先搜索，每次（每个节点）扩展一个节点时增加一个计数器，保留所有已探索节点的列表，然后解析它以找到最高的计数器，这应该是最深的路径.
根据您对 maxdepth 的实施，我假设如果节点有分支，则树的格式为 (value left-branch &optional right-branch)，如果是叶节点，则为 value。
因为不这样做会导致每次迭代都必须重建整个树的病态情况，所以 (value) 也是叶节点，(value nil) 和 (value nil nil) 也是.
我还假设您想移动现有树中的分支，而不是在不同的地方创建一个分支的新树。
如果是这样，您的目标是保留在计算树的 maxdepth 时遇到的最后一个非叶节点。
新函数的工作方式与 maxdepth 完全相同，只是它将 return 三个值而不是一个。对于您的图表，表示为 (1 (2 (3 4)))，它将 return:
3
(3 4)
LEFT
...其中3是深度，(3 4)是最深的非叶节点，LEFT
意味着 4 在该节点的左分支 (CADR) 而不是
右 (CADDR) 分支。
这意味着每次它使用自己的 return 值时，它必须捕获所有三个 return 值以便它可以重新 return 它们，并且需要特殊处理
确保我们不会将“4”作为 return 值，您不会
能够移动。
因为我们要折腾 3 个值，所以我们必须将我们自己的 max 和 1+ 版本定义为宏（l 和 betterp 是自由变量下面。它们的值分别是 maxdepth 的 l 参数和要使用的比较运算符：
(defmacro my-max (value-form1 value-form2)
(let ((n1 (gensym))
(v1 (gensym))
(n2 (gensym))
(v2 (gensym))
(pos1 (gensym))
(pos2 (gensym)))
`(multiple-value-bind (,n1 ,v1 ,pos1) ,value-form1
(multiple-value-bind (,n2 ,v2 ,pos2) ,value-form2
(if (funcall betterp ,n1 ,n2)
(apply #'values (cons ,n1 (if (consp ,v1)
(list ,v1 ,pos1)
(list l 'left))))
(apply #'values (cons ,n2 (if (consp ,v2)
(list ,v2 ,pos2)
(list l 'right)))))))))
(defmacro my-1+ (value-form)
(let ((number (gensym))
(value (gensym))
(position (gensym)))
`(multiple-value-bind (,number ,value ,position) ,value-form
(values (1+ ,number) ,value ,position))))
因为叶节点可以是一个裸值，也可以是一个列表
非空成员，我们需要一些函数来帮助消除这些差异
出去。第一个函数识别叶子，第二个函数将任何叶子转换为裸值：
(defun leafp (val)
(or (not (listp val))
(= (length (remove nil val)) 1)))
(defun leaf-value (leaf)
(if (listp leaf)
(car leaf)
leaf))
然后是 maxdepth 函数本身，我只对它做了一些小改动：
(defun maxdepth (l &optional (betterp #'>=))
(cond ((null l) (values -1 l nil))
((leafp l) (values 0 (leaf-value l) nil))
(t (my-1+ (my-max (maxdepth (cadr l) betterp) (maxdepth (caddr l) betterp))))))
最大的变化是，通过将 #'<= 作为 betterp 参数传递，可以将 maxdepth 变成 mindepth。这是因为我们必须在树上找到我们找到的深度值要去的地方。
此外，l = NIL 被视为具有 -1 的深度。这样一来，如果您有分支 (8 NIL 10)，最深的值将是 RIGHT 上的 10 而不是 `NIL，它可能根本不是一个节点，只是一个存根节点已删除或尚未添加。
移动节点，一旦找到，可以使用(setf (cdr x))或(setf (cddr x))来完成。但首先，您需要编写一个 mindepth 函数：
(defun mindepth (tree)
(maxdepth tree #'<=))
我想出了这个函数来实际将值从最深的节点移动到最浅的节点：
(defun balance-tree (l)
(multiple-value-bind (deepest-depth deepest-node deepest-side)
(maxdepth l)
(multiple-value-bind (shallowest-depth shallowest-node shallowest-side)
(mindepth l)
(let ((max-value (case deepest-side
((left) (prog1
(cadr deepest-node)
(setf (cadr deepest-node) nil)))
((right) (prog1
(caddr deepest-node)
(setf (cddr deepest-node) nil))))))
(case shallowest-side
((left) (cond ((= (length shallowest-node) 1)
(setf (cdr shallowest-node) (list max-value)))
((leafp (cadr shallowest-node))
(setf (cadr shallowest-node)
(list (leaf-value (cadr shallowest-node)) max-value)))
(t (setf (cadr shallowest-node) max-value))))
((right) (case (length shallowest-node)
((1) (setf (cdr shallowest-node)
(list nil max-value)))
((2) (setf (cddr shallowest-node)
(list max-value)))
((3) (cond ((null (caddr shallowest-node))
(setf (caddr shallowest-node)
max-value))
((leafp (caddr shallowest-node))
(setf (caddr shallowest-node)
(list (leaf-value (caddr shallowest-node))
max-value)))
(t (error "Didn't think this was reachable!"))))))))))
;; Return value: the modified tree.
l)
如果在我测试用的树(1 (2 (3 4)) (5 (6 (7 (8 nil 10)))))上反复调用这个函数，最终
树在以下两种状态之间交替：
(1 (2 (3 4) 10) (5 (6 (7 NIL)) (8 NIL)))
(1 (2 (3 NIL 4) 10) (5 (6 (7 NIL)) (8 NIL)))
...两者的 maxdepth 均为 3.
在您的原始示例中使用时，它会产生正确的结果：
CL-USER> (balance-tree '(1 (2 (3 4))))
(1 (2 (3 NIL)) 4)
...相当于：
(1 (2 3) 4)
如果你想将 (3 NIL) 之类的实例转换为普通的 3，有一个
功能，但它会遍历整棵树并重建它，所以请谨慎使用：
(defun clean-tree (tree)
(cond
((null tree) nil)
((atom tree) tree)
((= (length (remove nil tree)) 1)
(car tree))
((and (= (length tree) 3)
(null (caddr tree)))
(setf (cddr tree) nil)
(clean-tree tree))
(t
(unless (null (cadr tree))
(setf (cadr tree)
(clean-tree (cadr tree))))
(unless (null (caddr tree))
(setf (caddr tree)
(clean-tree (caddr tree))))
tree)))
由于这两种情况，它只是 return 其参数或其参数的函数，clean-tree 应始终以 setf 形式使用：
(setf tree (clean-tree tree))
这是上面示例输出之一的 clean-tree 的输出：
CL-USER> (clean-tree '(1 (2 (3 4) 10) (5 (6 (7 NIL)) (8 NIL))))
(1 (2 (3 4) 10) (5 (6 7) 8))
我有一棵树，我想找到到最深节点的最长路径，然后我想以某种方式更改它以使其更加平衡。在这个非常简单的示例中，我想移动 4，因为它是最深的路径，而不是将它放在 1 中，这样高度差异就不会那么大。我想在 lisp 中执行此操作，但我不太确定如何，我知道我想使用搜索但它有它，所以它实际上确实找到了最长的。我知道如何获得从根到给定节点的路径，但我不确定如何真正获得最深的节点。我想我有一个关于如何将最深的节点放在更好的部分上的想法，但任何建议都会很棒。
到目前为止，我只有一些代码可以 return 树的深度，但是我可以通过任何方式得到它 return 最深的节点是什么)?
(defun maxdepth (l)
(cond ((null l) 0)
((atom l) 0)
(t (+ 1 (max (maxdepth (cadr l)) (maxdepth (caddr l)))))))
您可以使用深度优先搜索，每次（每个节点）扩展一个节点时增加一个计数器，保留所有已探索节点的列表，然后解析它以找到最高的计数器，这应该是最深的路径.
根据您对 maxdepth 的实施，我假设如果节点有分支，则树的格式为 (value left-branch &optional right-branch)，如果是叶节点，则为 value。
因为不这样做会导致每次迭代都必须重建整个树的病态情况，所以 (value) 也是叶节点，(value nil) 和 (value nil nil) 也是.
我还假设您想移动现有树中的分支，而不是在不同的地方创建一个分支的新树。
如果是这样，您的目标是保留在计算树的 maxdepth 时遇到的最后一个非叶节点。
新函数的工作方式与 maxdepth 完全相同，只是它将 return 三个值而不是一个。对于您的图表，表示为 (1 (2 (3 4)))，它将 return:
3
(3 4)
LEFT
...其中3是深度，(3 4)是最深的非叶节点，LEFT
意味着 4 在该节点的左分支 (CADR) 而不是
右 (CADDR) 分支。
这意味着每次它使用自己的 return 值时，它必须捕获所有三个 return 值以便它可以重新 return 它们，并且需要特殊处理 确保我们不会将“4”作为 return 值，您不会 能够移动。
因为我们要折腾 3 个值，所以我们必须将我们自己的 max 和 1+ 版本定义为宏（l 和 betterp 是自由变量下面。它们的值分别是 maxdepth 的 l 参数和要使用的比较运算符：
(defmacro my-max (value-form1 value-form2)
(let ((n1 (gensym))
(v1 (gensym))
(n2 (gensym))
(v2 (gensym))
(pos1 (gensym))
(pos2 (gensym)))
`(multiple-value-bind (,n1 ,v1 ,pos1) ,value-form1
(multiple-value-bind (,n2 ,v2 ,pos2) ,value-form2
(if (funcall betterp ,n1 ,n2)
(apply #'values (cons ,n1 (if (consp ,v1)
(list ,v1 ,pos1)
(list l 'left))))
(apply #'values (cons ,n2 (if (consp ,v2)
(list ,v2 ,pos2)
(list l 'right)))))))))
(defmacro my-1+ (value-form)
(let ((number (gensym))
(value (gensym))
(position (gensym)))
`(multiple-value-bind (,number ,value ,position) ,value-form
(values (1+ ,number) ,value ,position))))
因为叶节点可以是一个裸值，也可以是一个列表 非空成员，我们需要一些函数来帮助消除这些差异 出去。第一个函数识别叶子，第二个函数将任何叶子转换为裸值：
(defun leafp (val)
(or (not (listp val))
(= (length (remove nil val)) 1)))
(defun leaf-value (leaf)
(if (listp leaf)
(car leaf)
leaf))
然后是 maxdepth 函数本身，我只对它做了一些小改动：
(defun maxdepth (l &optional (betterp #'>=))
(cond ((null l) (values -1 l nil))
((leafp l) (values 0 (leaf-value l) nil))
(t (my-1+ (my-max (maxdepth (cadr l) betterp) (maxdepth (caddr l) betterp))))))
最大的变化是，通过将 #'<= 作为 betterp 参数传递，可以将 maxdepth 变成 mindepth。这是因为我们必须在树上找到我们找到的深度值要去的地方。
此外，l = NIL 被视为具有 -1 的深度。这样一来，如果您有分支 (8 NIL 10)，最深的值将是 RIGHT 上的 10 而不是 `NIL，它可能根本不是一个节点，只是一个存根节点已删除或尚未添加。
移动节点，一旦找到，可以使用(setf (cdr x))或(setf (cddr x))来完成。但首先，您需要编写一个 mindepth 函数：
(defun mindepth (tree)
(maxdepth tree #'<=))
我想出了这个函数来实际将值从最深的节点移动到最浅的节点：
(defun balance-tree (l)
(multiple-value-bind (deepest-depth deepest-node deepest-side)
(maxdepth l)
(multiple-value-bind (shallowest-depth shallowest-node shallowest-side)
(mindepth l)
(let ((max-value (case deepest-side
((left) (prog1
(cadr deepest-node)
(setf (cadr deepest-node) nil)))
((right) (prog1
(caddr deepest-node)
(setf (cddr deepest-node) nil))))))
(case shallowest-side
((left) (cond ((= (length shallowest-node) 1)
(setf (cdr shallowest-node) (list max-value)))
((leafp (cadr shallowest-node))
(setf (cadr shallowest-node)
(list (leaf-value (cadr shallowest-node)) max-value)))
(t (setf (cadr shallowest-node) max-value))))
((right) (case (length shallowest-node)
((1) (setf (cdr shallowest-node)
(list nil max-value)))
((2) (setf (cddr shallowest-node)
(list max-value)))
((3) (cond ((null (caddr shallowest-node))
(setf (caddr shallowest-node)
max-value))
((leafp (caddr shallowest-node))
(setf (caddr shallowest-node)
(list (leaf-value (caddr shallowest-node))
max-value)))
(t (error "Didn't think this was reachable!"))))))))))
;; Return value: the modified tree.
l)
如果在我测试用的树(1 (2 (3 4)) (5 (6 (7 (8 nil 10)))))上反复调用这个函数，最终
树在以下两种状态之间交替：
(1 (2 (3 4) 10) (5 (6 (7 NIL)) (8 NIL)))
(1 (2 (3 NIL 4) 10) (5 (6 (7 NIL)) (8 NIL)))
...两者的 maxdepth 均为 3.
在您的原始示例中使用时，它会产生正确的结果：
CL-USER> (balance-tree '(1 (2 (3 4))))
(1 (2 (3 NIL)) 4)
...相当于：
(1 (2 3) 4)
如果你想将 (3 NIL) 之类的实例转换为普通的 3，有一个
功能，但它会遍历整棵树并重建它，所以请谨慎使用：
(defun clean-tree (tree)
(cond
((null tree) nil)
((atom tree) tree)
((= (length (remove nil tree)) 1)
(car tree))
((and (= (length tree) 3)
(null (caddr tree)))
(setf (cddr tree) nil)
(clean-tree tree))
(t
(unless (null (cadr tree))
(setf (cadr tree)
(clean-tree (cadr tree))))
(unless (null (caddr tree))
(setf (caddr tree)
(clean-tree (caddr tree))))
tree)))
由于这两种情况，它只是 return 其参数或其参数的函数，clean-tree 应始终以 setf 形式使用：
(setf tree (clean-tree tree))
这是上面示例输出之一的 clean-tree 的输出：
CL-USER> (clean-tree '(1 (2 (3 4) 10) (5 (6 (7 NIL)) (8 NIL))))
(1 (2 (3 4) 10) (5 (6 7) 8))