2

我了解算法，但无法使用方案使代码工作。我正在构建一个二叉搜索树。一个节点是一对（键值）。在java中，代码工作正常：

public void inOrder(BinaryNode n) {
    if (n != null) {
        inOrder(n.left);
        System.out.println(n.value);
        inOrder(n.right);
    }
}

在方案中，我的起始代码如下：

(define empty ())

(define empty? null?)

(define (node_key tn) (list-ref tn 0))

(define (node_val tn) (list-ref tn 1))

(define (node_left tn) (list-ref tn 2))

(define (node_right tn) (list-ref tn 3))

(define (tree-node key value left right) (list key value left right))

(define (get-key tn) (node_key tn))

(define (get-val tn) (node_val tn))

(define (get-left tn) (node_left tn))

(define (get-right tn) (node_right tn))

(define (get-pair tn) (list (get-key tn) (get-val tn)))

(define (atom? tn) (and (empty? (get-left tn)) (empty? (get-right tn))))

(define (printInOrder  t)
  (if (not (empty? t))       
      (begin
        (printInOrder (get-left t))
        (get-pair t)
        (printInOrder (get-right t))
        )
      )
  )

但是，如果我们测试 printInOrder：

(define a (tree-node 3 30 empty empty))

(define b (tree-node 1 10 empty empty))

(define c (tree-node 2 20 b a))

(printInOrder  c)

它应该打印：

1 10
2 20
3 30

但它不起作用，什么也不打印。

有人可以帮忙解决这个问题吗？谢谢。

4

2 回答 2

1

您编写的代码大致相当于：

public void inOrder(BinaryNode n) {
    if (n != null) {
        preOrder(n.left);
        n.value;
        preOrder(n.left);
    }
}

（...除了 Java 可能会将裸n.value视为语法错误，因为它没有被用于任何有趣的事情。）

除非它们的值达到顶层，否则表达式不会自动打印出它们的值。否则，您必须明确打印这些值。您可以使用display和newline来获得System.out.println的效果。如果您使用的是 Racket，您还可以使用printf。

于 2012-10-02T15:31:47.920 回答
0

Alan，对于一个 java 编码器，你在你的顶级环境中乱扔了许多功能。考虑这样的节点对象：

    (define make-node
      (lambda (key value)
        (let ((left '()) (right '()))
          (lambda (m)
            (cond
              ((eq? m 'key) key)
              ((eq? m 'value) value)
              ((eq? m 'left) left)
              ((eq? m 'right) right)
              ((eq? m 'set-left) (lambda (x) (set! left x)))
              ((eq? m 'set-right) (lambda (x) (set! right x)))
              (else (error "Error (make-node): unknown op " m)) )))))

当然，你需要比这更多的东西来制作一棵成熟的树。你想要一个至少有一个插入方法的列表对象（手动执行它，就像你正在做的那样，意味着你可能会不小心将错误的节点放入树中任何点的“左”或“右”）。我还将向树对象添加一个按顺序列出的方法，返回一个键-> 值对列表，然后您可以对列表执行任何操作（包括显示它）。

我并不是说这是构建树的最佳方法，但它更清洁。

于 2012-10-02T22:08:55.807 回答