2

想象一个算术表达式，例如 (+ 1 (* 2 (- 3 5))) 被认为是一个树状结构，其叶子为数字，内部节点为运算符符号，如下所示：

     +
   /   \
  1     *
       /  \
      2    -
          /  \
         3    5

我已经定义了这些函数来访问树的某些部分：

;; returns tree node
(define (operator lst)
  (cadr lst))

;; returns left tree
(define (left-op lst)
  (car lst))

;; returns right tree
(define (right-op lst)
  (cddr lst))

我正在尝试编写 3 个函数preorder, inorder, 并postorder返回按遇到的顺序遍历的树的列表

我从以前的 java 编程中知道树遍历是如何工作的，但是在编码时遇到了麻烦

上面的前： (preorder '(+ 1 (* 2 (- 3 5))))=>(+ 1 * 2 - 3 5)

4

1 回答 1

2

您对树的实现并不完全正确，您需要将叶子（示例中的数字）表示为另一棵具有空左子树和右子树的树。make-tree此外，拥有“构造函数”也很有用。让我们一步一步来 - 首先，表示树的正确抽象：

(define (make-tree value left right)
  (list left value right))

(define (operator tree)
  (cadr tree))

(define (left-op tree)
  (car tree))

(define (right-op tree)
  (caddr tree))

现在进行遍历。我会帮你做第一个，preorder：

(define (preorder tree)
  (if (null? tree)
      '()
      (append (list (operator tree))
              (preorder (left-op tree))
              (preorder (right-op tree)))))

问题中的树如下所示：

(define tree
  (make-tree '+
             (make-tree 1 '() '())
             (make-tree '*
                        (make-tree 2 '() '())
                        (make-tree '-
                                   (make-tree 3 '() '())
                                   (make-tree 5 '() '())))))

像这样使用它：

(preorder tree)
> '(+ 1 * 2 - 3 5)

其他两个遍历非常相似，只需append为每种情况以正确的顺序重新排列三个参数 - 我将把它作为读者的练习。

于 2012-10-12T01:18:26.727 回答