Verwendung des Schemas zum Aufbau eines Baums und zum Drucken der Knoten des in_order-Traversals

Question

Ich verstehe den Algorithmus, kann aber den Code nicht mit dem Schema zum Laufen bringen. Ich baue einen binären Suchbaum auf. Ein Knoten ist ein Paar von (Schlüsselwert). in Java, der Code funktioniert gut:

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

im Schema, mein Ausgangscode wie folgt:

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

Wenn wir jedoch die 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)

sollte es gedruckt werden:

1 10
2 20
3 30

aber es funktioniert nicht, es wird nichts ausgedruckt.

Kann jemand in dieser Angelegenheit helfen? Danke!

Answer 1

Der Code, den Sie geschrieben haben, ist ungefähr gleichwertig mit:

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

(... mit der Ausnahme, dass Java wahrscheinlich die nackten n.Wert als Syntaxfehler, da es für nichts Interessantes verwendet wird).

Ausdrücke geben ihre Werte nicht automatisch aus, es sei denn, ihre Werte erreichen die oberste Ebene. Andernfalls müssen Sie die Werte explizit ausgeben. Sie können verwenden Anzeige y Zeilenumbruch um die Wirkung von System.out.println . Wenn Sie Racket verwenden, haben Sie auch printf mit denen man arbeiten kann.

Answer 2

Alan, für einen Java-Programmierer überladen Sie Ihre Top-Level-Umgebung mit vielen Funktionen. Betrachten Sie ein Node-Objekt wie dieses:

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

Um einen vollwertigen Baum zu erstellen, bräuchte man natürlich etwas mehr als das; man bräuchte ein Listenobjekt mit mindestens einer Einfügemethode (wenn man es manuell macht, wie Sie es gerade tun, könnte man versehentlich den falschen Knoten in "links" oder "rechts" an einem beliebigen Punkt im Baum einfügen). Ich würde auch eine List-in-order-Methode zum Tree-Objekt hinzufügen, die eine Liste von Key->Value-Paaren zurückgibt, und dann könnte man alles mit der Liste machen (einschließlich sie anzeigen).

Ich behaupte nicht, dass dies der beste Weg ist, den Baum zu bauen, aber er ist sauberer.