gpt4 book ai didi

tree - 如何在 Racket 中折叠树形结构?

转载 作者:行者123 更新时间:2023-12-02 02:52:45 25 4
gpt4 key购买 nike

我有一个可以创建树结构的结构:

(结构节点(值左中右))

以及另一个定义叶节点的结构:

(structemptyNode())

如何创建一个函数,通过将值相加在一起,将树折叠成一个值,从左子树开始,然后是中间子树,然后是右子树?

我正在考虑将树转换为列表,首先是左子树,然后是中间子树,然后是右子树,然后在列表上执行折叠,但不确定如何完成它,或者如果这正确的做法是:

(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 的模式匹配。除此之外,使用基于议程的搜索也很好,这样整个过程是迭代的。因此,进行求和的函数将具有三个参数:

  • 当前节点;
  • 当前需要关注的节点议程;
  • 运行总计;

然后它根据匹配这些参数的模式来决定要做什么,循环遍历节点并从议程中推送和弹出内容。

因此给出了nodeempty-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

关于tree - 如何在 Racket 中折叠树形结构?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/61691151/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com