Príklad - vkladanie uzlov do binárneho stromu

Reprezentácia

• prázdny strom - NIL
• strom skoreňom K, ľavým podstromom L a pravým podstromom P - (L K P)

Selektory

(DEFUN ROOT (S) (SECOND S))
(DEFUN LEFT (S) (FIRST S))
(DEFUN RIGHT (S) (THIRD S))

Napriek tomu, že ide iba o premenovanie existujúcich funkcií, je vhodné konštruktory zadefinovať. Môže to mať vplyv na čitateľnosť programu.

Konštruktor

(DEFUN CREATE-TREE (ROOT LEFT RIGHT)
    (LIST LEFT ROOT RIGHT))

Vloženie uzla do stromu

Strom je usporiadaný, t.j. všetky uzly v ľavom podstrome sú menšie ako koreň a všetky uzly v pravom podstrome sú väčšie ako koreň.

(DEFUN INSERT-TREE (ELE TREE REL)
    (COND ((NULL TREE) (CREATE-TREE NIL ELE NIL))
          ((FUNCALL REL ELE (ROOT TREE))
                (CREATE-TREE (INSERT-TREE ELE (LEFT TREE) REL)
                             (ROOT TREE)
                             (RIGHT TREE)))
          ( T   (CREATE-TREE (LEFT TREE)
                             (ROOT TREE)
                             (INSERT-TREE ELE (RIGHT TREE) REL)))
))

to Homepage

to Teaching

to FLP

to the Top