自己做网站可以上传软件,学校官网主页网页设计,高端网站制作 专业制作平台,浙江网商银行股份有限公司想要一个树形控件来显示数据#xff0c;却发现Racket的GUI库竟然没有提供这个控件。既然没有#xff0c;那就自己手搓一个吧。没想到#xff0c;在做这个控件中竟然有了新发现#xff01; 树形控件有一个功能是查找树中指定的节点。这就是接下来的故事的起点。
1 找外援 不… 想要一个树形控件来显示数据却发现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的遍历处理起来就异常简单了。关键是复杂度也很理想这个最后分析。
具体算 法描述如下 首先nodes为包含节点的列表。 初始时nodes里仅包含根节点。 如果nodes列表为空返回#f 如果nodes列表不为空取列表首值节点 如果该值是指定节点返回该节点 如果该值不是指定节点检查其子节点 如果有子节点将子节点加入到nodes列表里并重复3-6对nodes向后搜索 如果没有子节点重复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~avalue”~a“\n id (node-value n)))) ) 这棵树如果在手机这种移动设备上看可能有点乱。如果用图片显示应该是这样的 运行程序得到的结果是 查找结果为id13value”t-13“
6 检查搜索路径 我们来看看程序的搜索路径。 为了实现这个功能我再定义一个显示函数以便显示出程序搜索的每一个节点情况。如下 ;显示节点值用于测试(define (display-node-value node) (display (format id~avalue”~a“\n (node-id node) (node-value node)))) 也就是上边程序中被注释掉的函数。现在我们把它的注释去掉。再运行程序得到以下结果 id0value”t-0“ id1value”t-1“ id2value”t-2“ id9value”t-9“ id13value”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~avalue”~a“\n id (node-value n)))) 运行程序结果如下 广度优先搜索指定节点 id0value”t-0“ id1value”t-1“ id2value”t-2“ id9value”t-9“ id13value”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)) 运行程序得到如下结果
广度优先搜索指定节点
id0value”t-0“
id1value”t-1“
id2value”t-2“
id9value”t-9“
id13value”t-13“
深度优先搜索指定节点
id0value”t-0“
id1value”t-1“
id2value”t-2“
id3value”t-3“
id4value”t-4“
id5value”t-5“
id6value”t-6“
id7value”t-7“
id8value”t-8“
id9value”t-9“
id10value”t-10“
id11value”t-11“
id12value”t-12“
id13value”t-13“ 从上边的运行结果来看广度优先算法比深度优先算法更快找到了指定的节点。当然仅是对于这里给的数据样本及指定的id来说的。比如如果id8运行结果就会出现深度优先算法更快找到结果的情况。
8 时间复杂度与空间复杂度 从以上分析和运行情况可以直观看出本查找算法的时间复杂度与空间复杂度均为O(n)而且是稳定算法。 注以上内容采用Racket语言的Scribble编辑并编译生成。
