球拍树遍历

Question

我在使用 Racket 时遇到以下问题。

我正在尝试为通用树实现树预序、post-序遍历。

结构定义为：

(define-struct eempty [])
(define-struct branch [left value right])

我不能使用 unless/when 运算符，只能使用 if 和 cond。我真的想不出解决办法。我看过维基百科伪代码，但由于球拍编程范式，它并没有真正帮助。

(define (inorder tree x)
  (cond [(and (branch? tree) (branch? (branch-left tree))) (inorder (branch-left tree) x)]
        [(and (branch? tree) (branch? (branch-right tree))) (inorder (branch-right tree) x)]

这是我到目前为止所做的，但是在匹配 empty 结构时出现问题。

更新：

我想做的是按 or/and post 顺序显示/打印节点值。

我知道我必须（以某种方式）实施另外 2 个条件：

(and (branch? tree) (empty? (branch-left tree))) do-something x)
(and (branch? tree) (empty? (branch-right tree))) do-something x)

在 do-something 中我必须做什么？我想我错过了这一点。

有什么帮助吗？

Answer 1

您似乎缺少 'empty' 结构的 'cond' 分支。您可以参考 How To Design Programs 教科书以获得这方面的帮助，特别是与混合自引用数据相关的 "template" 步骤。

Answer 2

我们从我们拥有的开始：

#lang racket
(define-struct empty [])                     ; no fields
(define-struct branch [left value right])    ; three fields

我们可以试着做一些树：

(define t1 (empty))
(define t2 (branch t1 7 t1))

现在我们可以尝试一下：

> t2
#<branch>
> (branch-left t2)
#<empty>
> (branch-left t1)
branch-left: contract violation
  expected: branch?
  given: #<empty>
> (branch? t2)
#t
> (branch? t1)
#f
> (empty? t2)
#f
> (empty? t1)
#t
>

所以那是我们的保留节目。 Racket 的 struct 宏定义了各种函数供我们使用——构造函数、访问器、谓词、...。

如何打印一个值？说，

(define (display-value v)
  (display #\ )
  (display v))

现在我们可以

> (display-value (branch-value t2))
 7

empty 没有 value 字段，只有 branch 有：

(define (display-tree-inorder t)
    (cond
        ((empty? t)
           (display-empty) )                       ; define it later
        ((branch? t)
           (display-branch-inorder                 ; define it later
                           (branch-left t)
                           (branch-value t)
                           (branch-right t)))))

在定义这个时，我们遵循了类型：我们的树要么是empty，要么是branch。是我们如何使用这两个结构定义来定义它们。

剩下的就是完成 display-empty 和 display-branch-inorder 的缺失定义。

但在我们这样做之前，我们还可以

(define (display-tree-preorder t)
    (cond
        ((empty? t)
           (display-empty) )
        ((branch? t)
           (display-branch-preorder
                           (branch-left t)
                           (branch-value t)
                           (branch-right t)))))

(define (display-tree-postorder t)
    (cond
        ((empty? t)
           (display-empty) )
        ((branch? t)
           (display-branch-postorder
                           (branch-left t)
                           (branch-value t)
                           (branch-right t)))))

那么display-empty在做什么呢？它什么都不做：

(define (display-empty)
    #f)

那么 display-branch-inorder 呢？

(define (display-branch-inorder lt val rt)

根据维基百科，我敢肯定，它首先显示其 left sub-tree,

    (display-tree-inorder .... )

然后它开始显示它的值

    (display-value .... )

最后显示正确的子树：

    .... )

其他两个变体也一样。

完成所有这些操作后，您会产生遵循关注点分离原则进行抽象和概括的冲动。好的。我们的 display-tree-inorder 将几件事混为一谈：它根据这样或那样的顺序概念遍历一棵树，并对每个节点的值执行某些操作。所有这些都可以抽象出来并成为一个通用过程的参数，比如 traverse-tree.

所以你看，这很简单：遵循类型！一切都会适合你。

球拍树遍历

Racket Tree Travesal

tree

recursion

traversal

racket