tree - 如何在球拍中折叠树状结构?
问题描述
我有一个可以创建树结构的结构:
(struct node (value left middle right))
和另一个定义叶节点的结构:
(struct emptyNode ())
如何通过将值相加来创建一个函数,将树折叠成一个值,从左子树开始,然后是中间,然后是右子树?
我正在考虑将树转换为列表,首先是左子树,然后是中间,然后是右子树,然后在列表上进行 foldl,但不确定如何完成它,或者这是否正确方法:
(define (treeToList tree)
(cond
[(node? tree) (append (node-left tree)) (treeToList (node-left tree))
(append (node-middle tree)) (treeToList (node-middle tree))
(append (node-right tree)) (treeToList (node-right tree))]
[else ] ;do nothing, leaf node
))
解决方案
所以,一个很好的方法是使用 Racket 的模式匹配。除此之外,使用基于议程的搜索也很好,这样整个过程是迭代的。所以进行求和的函数将有三个参数:
- 当前节点;
- 它需要查看的当前节点议程;
- 运行总和;
然后它根据与这些参数匹配的模式决定要做什么,遍历节点并从议程中推送和弹出内容。
因此,给定 和 的定义,node
以及empty-node
由它们组成的示例树如下:
(struct node (value left middle right))
(struct empty-node ())
(define sample-tree
(node 1
(node 2
(empty-node)
(node 3 (empty-node) (empty-node) (empty-node))
(node -1
(node 1 (empty-node) (empty-node) (empty-node))
(empty-node)
(empty-node)))
(node 10 (empty-node) (empty-node) (empty-node))
(empty-node)))
我们可以编写一个函数来对树求和,如下所示:
(define (sum-node-tree node-tree)
(define/match (snt-loop thing agenda sum)
[((empty-node) '() s)
;; an empty node, nothing on the agenda: we're done
s]
[((empty-node) (cons next more) s)
;; an empty node, but there is an agenda, so start on the next agenda
;; item
(snt-loop next more s)]
[((node (? number? v) l m r) a s)
;; a node with a value: sum the value into the total, push the middle
;; and right children onto the agenda, and start on the left child.
(snt-loop l (list* m r a) (+ s v))]
[(_ _ _)
;; something bad in the tree
(error 'sum-node-tree "bogus tree")])
(snt-loop node-tree '() 0))
然后
> (sum-node-tree sample-tree)
16
推荐阅读
- html - 谷歌地图api计费
- python - python:更新mysql表
- mpi - 如何使用 MPI_Scatter/MPI_Gather 将 MPI 中的两个矩阵相乘
- javascript - Jest Mock react组件的实现
- c# - 在c#中显示json结果的json字符串名称
- java - org.hibernate.hql.internal.ast.QuerySyntaxException:期待关闭,发现'('
- react-native - 在旧的 react-native 0.38.1 中禁用 http/2 请求
- angular - 用后端服务替换内存服务时的状态 404
- yii2 - 使用不同的连接向下迁移 Yii2 控制台失败
- android - 处理空服务器响应案例