球拍树遍历

Question

我对Racket有以下问题。

我正在尝试为通用树实现树预订，后序遍历。

结构定义是：

(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结构时遇到了问题。

更新：

我要做的是按顺序显示/打印节点值或/和后期顺序。

我知道我必须实现（不知何故）另外2个条件：

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

做什么我必须做什么？我想我错过了这一点。

有帮助吗？

Answer 1

我们从拥有的东西开始：

#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)

根据维基百科，我敢肯定，它首先显示其左子树，

    (display-tree-inorder .... ) 

然后它会显示它的价值

    (display-value .... )

它通过显示正确的子树完成：

    .... )

其他两个变体也是如此。

在完成所有这些之后，您将感受到通过遵循关注点分离原则来抽象和概括的冲动。好。我们的display-tree-inorder将几个东西混为一谈：它根据这个或那个有序的概念遍历一棵树，并且它对每个节点的价值做了一些事情。所有这些都可以被抽象出来并作为一个广义程序的参数，比如traverse-tree。

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

Answer 2

看起来你错过了'空'结构的'cond'分支。您可以参考How To Design Programs教科书获取相关帮助，特别是与混合自参考数据相关的“模板”步骤。