假设我有以下树:
在我的程序中,这棵树使用列表表示:'(+ (* 5 6) (sqrt 3))
。
如何通过索引获取子树?
索引应该从0开始,深度优先。在上图中,我用索引标记了所有节点以显示这一点。
例如:
(define tree '(+ (* 5 6) (sqrt 3)))
(subtree tree 0) ; Returns: '(+ (* 5 6) (sqrt 3)))
(subtree tree 1) ; Returns: '(* 5 6)
(subtree tree 2) ; Returns: 5
(subtree tree 3) ; Returns: 6
(subtree tree 4) ; Returns: '(sqrt 3)
(subtree tree 5) ; Returns: 3
我试着像这样实现subtree
:
(define (subtree tree index)
(cond [(= index 0) tree]
[else
(subtree (cdr tree)
(- index 1))]))
但是,这不会遍历子列表。这是不正确的。
编辑:
我尝试使用连续传递样式实现子树
:
(define (subtree& exp index counter f)
(cond [(= counter index) exp]
[(null? exp) (f counter)]
[(list? exp)
(let ((children (cdr exp)))
(subtree& (car children)
index
(+ counter 1)
(lambda (counter2)
(if (null? (cdr children))
(f counter)
(subtree& (cadr children)
index
(+ counter2 1)
f)))))]
[else (f counter)]))
(define (subtree tree index)
(subtree& tree
index
0
(lambda (_)
(error "Index out of bounds" index))))
这适用于像这样的树:
'(+ 1 2)
'(+ (* 5 6) (sqrt 3))
但是,对于像这样的树,它会失败:
'(+ 1 2 3)
我的实现有什么问题?
最佳答案
在没有毛茸茸的控制结构的情况下做到这一点的方法是有一个议程。
但在此之前,定义抽象。每次我看到代码正在走它称为“树”的东西并且充满明确的 car
,cdr
&c 我必须阻止自己简单地冷启动希望我们能得到一个更好的宇宙。如果教你的人没有告诉你这个对他们说些强硬的话。
下面是树结构的一些抽象。这些特别重要,因为树结构确实是不规则的:我希望能够在任何节点上说“给我这个节点的 child ”:叶子只是没有 child 的节点,而不是某种特殊的东西。
(define (make-node value . children)
;; make a tree node with value and children
(if (null? children)
value
(cons value children)))
(define (node-value node)
;; the value of a node
(if (cons? node)
(car node)
node))
(define (node-children node)
;; the children of a node as a list.
(if (cons? node)
(cdr node)
'()))
现在是议程的一些抽象。议程以列表的形式表示,但当然没有其他人知道这一点,而且更具工业实力的实现可能不想那样表示它们。
(define empty-agenda
;; an empty agenda
'())
(define agenda-empty?
;; is an agenda empty?
empty?)
(define (agenda-next agenda)
;; return the next element of an agenda if it is not empty
;; error if it is
(if (not (null? agenda))
(car agenda)
(error 'agenda-next "empty agenda")))
(define (agenda-rest agenda)
;; Return an agenda without the next element, or error if the
;; agenda is empty
(if (not (null? agenda))
(cdr agenda)
(error 'agenda-rest "empty agenda")))
(define (agenda-prepend agenda things)
;; Prepend things to agenda: the first element of things will be
;; the next element of the new agenda
(append things agenda))
(define (agenda-append agenda things)
;; append things to agenda: the elements of things will be after
;; all elements of agenda in the new agenda
(append agenda things))
现在很容易编写函数的纯迭代版本(议程是维护堆栈),没有各种复杂的控制结构。
(define (node-indexed root index)
;; find the node with index index in root.
(let ni-loop ([idx 0]
[agenda (agenda-prepend empty-agenda (list root))])
(cond [(agenda-empty? agenda)
;; we're out of agenda: raise an exception
(error 'node-indexed "no node with index ~A" index)]
[(= idx index)
;; we've found it: it's whatever is next on the agenda
(agenda-next agenda)]
[else
;; carry on after adding all the children of this node
;; to the agenda
(ni-loop (+ idx 1)
(agenda-prepend (agenda-rest agenda)
(node-children
(agenda-next agenda))))])))
需要思考的一件事:如果将上述函数中的 agenda-prepend
替换为 agenda-append
会发生什么情况?
关于tree - 如何通过索引获取子树?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/65000785/