2

私は LISP を学び、実用的な一般的な Lisp を読んでいるので、問題を見つけて解決しようとしました。

preorder と inorder から postorder ツリーを作成できるようにする必要があります

たとえば、次のように指定した場合:

プレオーダー：ABDECF

順序: DBEACF

出力はポストオーダーになります: DEBFCA

私が見ることができることから、inorder の最初の要素は常に postorder の最初の要素であるため、これを反映するコードを書き始めました。

(defun tree-recovery (preorder inorder)
  (let (root)
    (setf root (first inorder))))

しかし、私はここからどこへ行くべきかわからないので、助けていただければ幸いです! ありがとう

4

1 に答える 1

2

関数tree-recoveryに という名前を付けた場合、postorder シーケンスを構築する代わりにツリーを回復させます。(ツリーを実際に再構築せずに問題を解決するには、私よりも賢い人が必要です)。

inorder と postorder は同じ要素で始まりますが、その要素は ルートではありません: preorderシーケンスの最初の要素がルートです。

すべてのシーケンス要素が によって比較可能な非 nil アトムであると仮定して、ツリーを復元しましょうEQL。リーフをアトムの値として、他のノードを として(list root left right)、空のサブツリーを NILとして表します。

(defun tree-recovery (preorder inorder)
  (if (rest preorder)
      (let* ((root (pop preorder))
             (inorder-root-tail
               (member root inorder))
             (inorder-left
               (ldiff inorder inorder-root-tail))
             (left-length
               (length inorder-left))
             (inorder-right
               (rest inorder-root-tail))
             (preorder-left
               (subseq preorder 0 left-length))
             (preorder-right
               (subseq preorder left-length)))
        (list root
              (tree-recovery preorder-left inorder-left)
              (tree-recovery preorder-right inorder-right)))
      (first preorder)))

空のツリーの場合は NIL を返します。1 つのリーフ ノードの自明なツリーの場合、値を返します。

他のツリーについては、最初にルート要素をpreorder(最初の場所から) ポップします。次に、 のルート要素で始まるサブリストを見つけます inorder。これを使用してinorder、左側のサブツリーにinorder対応する の一部と、右側のサブツリーに対応する の一部を取得します。左部分木のサイズがわかれば、左部分と右部分をpreorder簡単に取得できます。

ツリーができたら、ポストオーダー トラバーサルを行うのは簡単です。

(defun postorder (tree)
  (and tree ;; non-empty
       (if (consp tree) ;; non-leaf
           (destructuring-bind (root left right) tree
             (append (postorder left)
                     (postorder right)
                     (postorder root)))
           (list tree))))

やってみよう：

(postorder 
 (tree-recovery '(a b d e c f)
                '(d b e a c f)))
=> (D E B F C A)

うまくいくようです。

于 2013-02-08T22:20:54.497 に答える