Lisp 递归搜索二叉树

博客数据库死而复生, 虚惊一场.

言归正传, 也许你早就知道LISP的精髓在于递归, 但是对于初学者来说, 往往仍然不知道递归要怎么实现, 或者干脆不知道递归有什么好处. 接下来的例子也许会使你重新面对递归这一问题.

Lisp recursion search tree

上面图片中演示了家谱式结构, 越上层的圆辈份越高, 圆有后代, 用线段标明血缘关系. 例如: 第二层的三个黄色圆为第一层白色圆的孩子.

为了记录这种血缘关系, 我们将第二层三个黄色圆的图元名记录成表, 放到白色圆的ldata中. 这一步可以通过以下语句实现:

1
2
3
4
5
6
7
8
9
;;; 选择集转化为表
(defun ent2list (ss / lst i ent)
  (setq i -1)
  (while (setq ent (ssname ss (setq i (1+ i))))
    (setq lst (cons ent lst))
  )
)
;;; 定义父子关系
(vlax-ldata-put (car (entsel "选择父圆:")) "son" (ent2list (ssget)))

好了, 我们得到了一个树状结构, 特点是, 辈份级数不定, 后代数量不定.

此时如果想要获得任意圆的所有后代, 该怎么做呢? 请看下面:

1
2
3
4
5
6
7
;;; 遍历家族树 仅输出
(defun tree (e)
  (foreach e (vlax-ldata-get e "son")
    (print e)
    (tree e)
  )
)

如果仅仅是显示, 或许用处不大, 那么我们再加上执行函数部分:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
;;; 遍历家族树 执行函数
(defun tree (e f / r)
  (foreach e (vlax-ldata-get e "son")
    (if (= (type f) \'list)
      (apply
        (car f)
        (if (cdr f)
          (cons e (cdr f))
          (list e)
        )
      )
    )
    (tree e f)
  )
)

测试一下, 我们先写个改变图元颜色的函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
;;; 设置颜色
(defun entSetColor (e c)
  (setq e (entget e))
  (if (assoc 62 e)
    (entmod (subst
      (cons 62 c)
      (assoc 62 e)
      e
      )
    )
    (entmod (append
      e
      (list (cons 62 c))
      )
    )
  )
)

OK, 让我们用以下语句对任意一个圆操作一下:

1
2
;;; 遍历 并改变后代的颜色
(tree (car (entsel "选择圆:")) (list \'entSetColor 1))