通用树查找算法

        想要一个树形控件来显示数据，却发现Racket的GUI库竟然没有提供这个控件。既然没有，那就自己手搓一个吧。没想到，在做这个控件中竟然有了新发现！

        树形控件有一个功能是查找树中指定的节点。这就是接下来的故事的起点。

1 找外援

        不想动脑筋，就找网络，网上一般都是二叉树、红黑树啥的，不是我需要的；找AI帮我写一个，如下：

问：用Racket写一个通用的树查找算法。

AI答：

以下是使用Racket编写的通用树查找算法：

#lang racket

(define (tree? x)

(and (pair? x) (not (null? x))))

(define (search-tree t target)

(cond ((null? t) #f)

((equal? (car t) target) t)

(else (+ 1 (search-tree (cdr t) target)))))

(define tree

'(("A" "B" "C") ("D" "E" "F") ("G" "H" "I")))

(displayln "Tree:")

(tree-walk tree tree-root tree)

(displayln "Search for 'D':")

(search-tree tree 'D)

        这个程序定义了一个辅助函数 ‘tree?‘,用于检查一个值是否为树。然后，它定义了 ‘search-tree‘ 函数，该函数接受一个树和目标值作为参数，并返回找到的目标节点或 "#f"(表示未找到)。最后，它创建了一个名为“tree”的示例树，并使用“tree-walk”函数遍历它。然后，它在树中搜索目标值“D”，并将结果打印到控制台上。

显然，AI也不是救世主！还是开动自己的思想解决问题吧。

2 我的思考

         树的根节点、子节点、叶子节点的处理属于基本操作，不用过多考虑。重点是不确定的子节点数量，如何处理？

        以下是一个通用树节点的结构：

;树节点结构：

(struct node

(id ;这里设定id值为数字。

value ;节点值。

children ;子节点，考虑用列表来存放。

))

        我实际要使用的树节点比这个要复杂一些，这里我就把这个结构来凑合作为例子样本吧。

        如上面所说，重点就是children这个列表了。一般会考虑采用"for-each"遍历列表元素，然后用递归方式对每个元素的children继续以上过程，直到找到需要的值或遍历整个树为止。

        但这样有一个严重的问题，这样的每次递归都会出现等待下一级递归结束后才能继续列表元素处理的问题，就会出现著名的低效递归的问题——因为这样递归在执行时需要系统提供隐式栈来实现递归，造成效率低效，甚至填满内存的严重问题（当然现在内存一般足够大，还不至于因内存溢出造成崩溃）。

        解决办法是采用尾递归。难点还是在children列表上。

        我找到一个办法——将列表与树结合起来进行尾递归，算法原理如下。

3 算法原理

        假设我们有一个查找函数"find-node"，其参数有两个——"tree"为要查找的树；"id"为查找的关键值。

        在"find-node"中定义一个闭包"find-node/in"，它来实现树的遍历查找，这也是常规操作。

        为了实现尾递归，为"find-node/in"设定一个参数nodes作为存放树节点的子节点的列表（根节点是这个列表参数的初始值）。然后挨个搜索树的各个节点，如果遇到节点有子节点时，就把这个节点的children添加到nodes的后面。这样就把对树的搜索和对子节点列表的遍历转换为对列表nodes的遍历，处理起来就异常简单了。关键是，复杂度也很理想，这个最后分析。

具体算    法描述如下：

1. 首先，nodes为包含节点的列表。

2. 初始时nodes里仅包含根节点。

3. 如果nodes列表为空，返回#f；

4. 如果nodes列表不为空，取列表首值（节点）：

5. 如果该值是指定节点，返回该节点；

6. 如果该值不是指定节点，检查其子节点：

7. 如果有子节点，将子节点加入到nodes列表里，并重复3-6对nodes向后搜索；

8. 如果没有子节点，重复3-6对nodes向后搜索。

        注意，以上算法描述中还需要考虑一个特例，就是根节点不存在（一般设置为"#f"）时的情况。为了处理这个特例，我们在取出列表首值后首先对其做一个判断——是否为未设置节点值的根节点。

4 实现树查找

        根据上边的算法原理，我们把代码写出来，如下：

;定义取得节点值函数：

;tree为需要搜索的树，id为节点标识。

(define (find-node-version-1 tree id)

(define (find-node/in nodes)

(cond

;nodes列表为空，返回#f：

[(empty? nodes) #f]

;值（节点）#f，即树根未初始化，树不存在：

[(not (car nodes)) #f]

;nodes列表首值（节点）即为指定节点，返回节点：

[(= (node-id (car nodes)) id)

;(display-node-value (car nodes))

(car nodes)]

;如果nodes首值不是指定节点，且其子列表为空：

[(empty? (node-children (car nodes)))

;(display-node-value (car nodes))

(find-node/in (cdr nodes))]

[else

;(display-node-value (car nodes))

(find-node/in

(append (cdr nodes)

(node-children (car nodes))))]))

(find-node/in (list tree)))

5 测试

        现在手搓一棵树并放到测试模块中来做测试。如下：

(module+ test

;测试空树：

(define tree/empty #f)

(find-node tree/empty 3)

;测试自定义树：

(define tree/user

(node 0 "t-0" (list (node 1 "t-1" '())

(node 2 "t-2" (list (node 3 "t-3" (list (node 4 "t-4" '())))

(node 5 "t-5" '())

(node 6 "t-6" (list (node 7 "t-7" '())

(node 8 "t-8" '())))))

(node 9 "t-9" (list (node 10 "t-10" (list (node 11 "t-11" '())))

(node 12 "t-12" '())))

(node 13 "t-13" (list (node 14 "t-14" (list (node 15 "t-15" (list (node 16 "t-16" '()))))))))))

(let* ([id 13]

[n (find-node-version-1 tree/user id)])

(display (format "查找结果为：id=~a，value=”~a“\n" id (node-value n))))

)

这棵树如果在手机这种移动设备上看可能有点乱。如果用图片显示应该是这样的：

        运行程序，得到的结果是：

        查找结果为：id=13，value=”t-13“

6 检查搜索路径

        我们来看看程序的搜索路径。

        为了实现这个功能，我再定义一个显示函数，以便显示出程序搜索的每一个节点情况。如下：

;显示节点值（用于测试）：

(define (display-node-value node)

(display

(format "id=~a，value=”~a“\n"

(node-id node)

(node-value node))))

        也就是上边程序中被注释掉的函数。现在我们把它的注释去掉。再运行程序，得到以下结果：

        id=0，value=”t-0“

        id=1，value=”t-1“

        id=2，value=”t-2“

        id=9，value=”t-9“

        id=13，value=”t-13“

        哦，这不是遍历树的广度优先算法吗！这的确是遍历树的广度优先算法。

        我们可以把这个算法独立出来用单独函数表示。如下：

;广度优先搜索：

(define (find-node/width nodes id)

(cond

;nodes列表为空，返回#f：

[(empty? nodes) #f]

;值（节点）#f，即树根未初始化，树不存在：

[(not (car nodes)) #f]

;nodes列表首值（节点）即为指定节点，返回节点：

[(= (node-id (car nodes)) id)

;(display-node-value (car nodes))

(car nodes)]

;如果nodes首值不是指定节点，且其子列表为空：

[(empty? (node-children (car nodes)))

;(display-node-value (car nodes))

(find-node/width (cdr nodes) id)]

[else

;(display-node-value (car nodes))

(find-node/width

(append (cdr nodes)

(node-children (car nodes)))

id)]))

相应地，查找函数就表示为：

;定义取得节点值函数：

;tree为需要搜索的树，id为节点标识。

(define (find-node tree id)

;广度优先搜索指定节点：

(display (format "广度优先搜索指定节点：\n"))

(find-node/width (list tree) id))

        在测试模块中添加如下测试代码：

(let* ([id 13]

[n (find-node tree/user id)])

(display (format "查找结果为：id=~a，value=”~a“\n" id (node-value n))))

        运行程序，结果如下：

        广度优先搜索指定节点：

        id=0，value=”t-0“

        id=1，value=”t-1“

        id=2，value=”t-2“

        id=9，value=”t-9“

        id=13，value=”t-13“

        与上边一样的结果。

        那么问题来了，如果要实现深度优先算法，怎么做呢？

7 深度优先算法

        从上边的算法原理来理解，如果在将子节点与现有nodes列表合并时，不是将子节点放到nodes列表之后，而是放到nodes列表之前——也就是说优先搜索子节点内容——就可以实现深度优先算法了。实现如下：

;深度优先搜索：

(define (find-node/depth nodes id)

(cond

;nodes列表为空，返回#f：

[(empty? nodes) #f]

;值（节点）#f，即树根未初始化，树不存在：

[(not (car nodes)) #f]

;nodes列表首值（节点）即为指定节点，返回节点：

[(= (node-id (car nodes)) id)

;(display-node-value (car nodes))

(car nodes)]

;如果nodes首值不是指定节点，且其子列表为空：

[(empty? (node-children (car nodes)))

;(display-node-value (car nodes))

(find-node/depth (cdr nodes) id)]

[else

;(display-node-value (car nodes))

(find-node/depth

(append (node-children (car nodes))

(cdr nodes))

id)]))

        把深度优先算法添加到"find-node"函数中，如下：

;定义取得节点值函数：

;tree为需要搜索的树，id为节点标识。

(define (find-node tree id)

;广度优先搜索指定节点：

(display (format "广度优先搜索指定节点：\n"))

(find-node/width (list tree) id)

;深度优先搜索指定节点：

(display (format "深度优先搜索指定节点：\n"))

(find-node/depth (list tree) id))

        运行程序，得到如下结果：

广度优先搜索指定节点：

id=0，value=”t-0“

id=1，value=”t-1“

id=2，value=”t-2“

id=9，value=”t-9“

id=13，value=”t-13“

深度优先搜索指定节点：

id=0，value=”t-0“

id=1，value=”t-1“

id=2，value=”t-2“

id=3，value=”t-3“

id=4，value=”t-4“

id=5，value=”t-5“

id=6，value=”t-6“

id=7，value=”t-7“

id=8，value=”t-8“

id=9，value=”t-9“

id=10，value=”t-10“

id=11，value=”t-11“

id=12，value=”t-12“

id=13，value=”t-13“

        从上边的运行结果来看，广度优先算法比深度优先算法更快找到了指定的节点。当然，仅是对于这里给的数据样本及指定的id来说的。比如，如果id=8，运行结果就会出现深度优先算法更快找到结果的情况。

8 时间复杂度与空间复杂度

        从以上分析和运行情况可以直观看出，本查找算法的时间复杂度与空间复杂度均为O(n)，而且是稳定算法。

           注：以上内容采用Racket语言的Scribble编辑并编译生成。