1

I am trying to write the algorithm for inorder traversal for a binary tree using RACKET/DR. RACKET

 (define (print-records node number)
      (cond
      [(not (empty? node-left))(print-records (node-left node) number )]
      *Do This before moving to next IF clause*
      [(not (empty? node-right))(print-records(node-right node) number)]

      ))

I am trying to follow the following algorithm

InOrder(node)
if node is null return
InOrder(node.left)
Print(node)
InOrder(node.Right)

My problem is that through COND I can execute one expression and it will skip the rest. I tried to add two expressions under one it did not work either e.g ((a)(b)). I also tried to make a helper procedure but that did not work either.

4

2 回答 2

2

走一棵二叉树是一个非常普遍的操作。您可以制作一个通用过程,然后使用适用于每个节点的功能对其进行专门化。

(define (walker node function)
  (unless (empty? node)
    (walker (node-left  node) function)
    (function node)
    (walker (node-right node) function)))

注意:最好empty?在函数开始时检查。

(define (print-records node number)
  (walker node (compose print node-value)))  ; ignore number, it seems.

你也可以这样工作:

(define (walking-with function)
  (letrec ((walker (lambda (node)
                     (unless (empty? node)
                       (walker (node-left  node))
                       (function node)
                       (walker (node-right node))))))
     walker))
(define print-records-for (walking-with (compose print node-value)))
(print-records-for node)
> ...
于 2013-05-16T23:14:53.547 回答
2

你用cond错了方法。请注意,您必须递归地遍历树的左侧部分,然后访问当前节点,然后递归地遍历树的右侧部分——它们不是互斥的替代方案,这三个步骤需要以精确的顺​​序执行。尝试这样的事情:

(define (print-records node number)
  (unless (empty? (node-left node))
    (print-records (node-left node) number))
  (print (node-value node)) ; replace this line with the actual printing code
  (unless (empty? (node-right node))
    (print-records (node-right node) number)))

一些解释:

  • (unless <condition> <body>)只是(cond ((not <condition>) <body>)).
  • 遍历的真正工作是在两个递归调用之间完成的,在这种情况下,我(print (node-value node))作为示例编写,将该行替换为当前节点值的实际打印代码。
  • 目前尚不清楚您打算如何处理该number参数,因为它只是被传递,未使用。
于 2013-05-16T22:03:18.113 回答