トップダウンツリーの検索と置換

Question

ツリー検索をコーディングする際に問題が発生しました&アルゴリズムを置き換えます。入力ツリーには任意にネストされたデータ項目が含まれます。たとえば、tree =（1（2（4（5））6））です。ここで1はルートであり、各レベルは括弧内に埋め込まれています。したがって、1はレベル1にあります。 2,3,4,6はレベル2（1以下）、5はレベル3（4以下）にあります。ツリー全体は、任意のリストの車が常にデータ項目であり、他のデータ項目またはサブツリーが続くことができるように構成されています。問題は、入力項目と一致するツリー内のデータ項目を特定し、既存の古い項目を指定された新しい部分木で置き換えることです（たとえば、（サブツリーの古い項目ツリーを交換するなど））。したがって、ツリーはそれぞれの置換えで成長します。ただし、ツリー内でトップダウン検索を行い、見つかった最初のアイテムのみを交換して終了する必要があります。

いくつかの観察：1）バイナリツリーの場合、検索順序（トップダウン訪問）は通常レベルオーダーと呼ばれ、他の可能な検索順序はpreorder、inorder、postorderですが、ツリーは必ずしもバイナリではありません。 2）幅優先探索アルゴリズムのようなものが動作するかもしれませんが、ノードは生成されるのではなく、ツリートラバーサルによって選択されます。 3）標準の "代用"機能は、ツリーではなくシーケンスに対してのみ機能します。 4） "subst"関数はツリーでは機能しますが、一致するすべてのアイテムを置き換えて深さ優先でトラバースしているように見えます。最初の置換後にcountキーワード（ "substitute"のような）はありません。

どのようなヘルプコーディングやフレームワークでも良いアプローチが評価されます。 （なぜ、common-lispにリストとベクトルの両方の "ツリー"関数がないのか不思議です）

Answer 1

多分私はこれをしてはいけません。自分で宿題をすることになっているかもしれませんが、それを示すよりも、何をすべきかを説明する時間が長くなります。することができます（

(defun search-replace (item new-item lst) 
    (when (listp lst) 
    (let ((found-item (member item lst))) 
     (if found-item 
      (rplaca found-item new-item) 
      (some #'(lambda (sublst) (search-replace item new-item sublst)) lst))))) 

この関数は、すなわち、それはrplacaを使用するためには、元のリストを変更し、それが結果のリストを返しません、破壊的である：ここで は幅優先探索と置換バージョンであります最後に追加してください）。また、テスト機能（equalまたは必要なもの）など、他の素敵な機能を追加することもできます。 carがサブリストであるリストでも機能します（この例では常にアトムです）。 私はそれがあなたが始めるのを助けることを望みます。

Answer 2

@Leo。あなたの簡潔な解決策のように - 理解のためにそれを勉強しなければなりません。幅優先がこれをアプローチする方法だったというのが私の直感を確認するための

(defun add-tree (newsubtree tree) 
    (let ((queue (make-array 0 :adjustable t :fill-pointer t)) 
     (data (first newsubtree)) 
     (index 0)) 
    (vector-push-extend tree queue) 
    (loop until (= index (fill-pointer queue)) 
     do (let ((current-node (elt queue index))) 
      (incf index) 
      (loop for child in (second current-node) 
       for i from 0 
       if (and (numberp child) (= child data)) 
        do (setf (elt (second current-node) i) newsubtree) 
         (return-from add-tree tree) 
        else do (vector-push-extend child queue)))))) 

(add-tree '(2 (5 6)) '(0 ((1 (3 2 4)) 2))) 
(0 ((1 (3 2 4)) (2 (5 6)))) 

ありがとう：それまでの間、ここで別の予備的な幅優先探索の試みです。 （ps：これは宿題ではありません）

Answer 3

ここでは、実際に幅の広い最初の検索があります。 （残念ながら、レオのコード@、滑りやすいとはいえ、それをしません。）

楽しみのためにキューとして循環リストを使用：4にもかかわらず、2,3,6と同じレベルにあるのはなぜ

(setf *print-circle* t) 

(defun one-element-queue (item) 
    (let ((link (list item))) 
    (setf (cdr link) link))) 

(defun enqueue (item &optional queue) 
    (cond ((null queue) (one-element-queue item)) 
     (t (let ((new-link (cons item (cdr queue)))) 
      (setf (cdr queue) new-link))))) 

(defun enqueue-all (items &optional queue) 
    (dolist (item items queue) (setq queue (enqueue item queue)))) 

(defun dequeue (queue) 
    (cond ((eq queue (cdr queue)) (values (car queue) nil)) 
     (t (let ((item (cadr queue))) 
      (setf (cdr queue) (cddr queue)) 
      (values item queue))))) 

(defun node-replace (new-item old-item node) 
    (let ((position (position old-item node :test #'equal))) 
    (when position (setf (nth position node) new-item)) 
    position)) 

(defun tree-replace (new-item old-item tree) 
    (loop with queue = (enqueue tree) and node 
     while queue 
     do (multiple-value-setq (node queue) (dequeue queue)) 
     until (node-replace new-item old-item node) 
     do (setq queue (enqueue-all (remove-if-not #'listp node) queue))) 
    tree) 

(setq tree '(1 ((5 ((41))) 3 (4 (5)) 5))) 

(print (tree-replace 42 5 tree))