2つのリストに基づいてツリーを生成する

Question

2つのリストに基づいてツリーを生成する方法を知りたいと思います。例えば、プリオーダー、インオーダー所望ツリーの一つを生成する第二の1つを表す最初のもの：

data Tree a = Branch a (Tree a) (Tree a) | Leaf deriving Show 
genTree :: [a] -> [a] -> Tree a 
genTree [7,9,2] [9,7,2] = 
Branch 7 (Branch 9 Leaf Leaf) (Branch 2 Leaf Leaf) 

が任意の提案が受け入れられ、ありがとう！

Answer 1

でとプレ配列中ルートの位置を記述する。だから、：inorderシーケンスの

1. 最初要素がルートです。次に、サブツリーを順番に左に並べ、その後に右のサブツリーを続ける。右の部分木シーケンスがどこから始まるのかはわかりません。
2. ルートがpreorderシーケンスにある場合、左側が左側のサブツリーのプリオーダーシーケンス、右側が右側のサブツリーのプリオーダーシーケンスです。

は、私たちがこのようなバイナリツリーがあるとします。

1 
/\ 
2 3 
/\ 
    4 5 

preorder: 1 2 3 4 5 
inorder : 2 1 4 3 5 

のは、それをバック作ろう！さて、予約注文シーケンス1 2 3 4 5を見てください。私たちは1が根であることを知っています。

[1] 2 3 4 5 
2 [1] 4 3 5 

2は、サブツリーのインオーダーの順序です。 4 3 5は右のサブツリーです。 、

1. 左のサブツリーのみノードを持っている右ノードを持っていますし、また、我々は知っています！右の前順シーケンス脇サブツリーの先行順シーケンスを左
2. が結果として2 3 4 5

である、の左の前順は右のは3 4 5で、2です。

そして、再帰が始まります。私たちは何もないまで！それは空のシーケンスです。それから、我々はLeafに会った。

---

要約すると、以下のハスケルコードがあります。 （これは、誤入力の状況を処理しません）

data Tree a = Branch a (Tree a) (Tree a) 
      | Leaf 
      deriving Show 
--     pre in 
genTree :: Eq a => [a] -> [a] -> Tree a 
genTree [] [] = Leaf 
genTree (root:pre_seq) in_seq = Branch root left right 
    where 
    (left_in, _:right_in) = break (== root)  in_seq 
    (left_pre, right_pre) = splitAt (length left_in) pre_seq 
    left = genTree left_pre left_in 
    right = genTree right_pre right_in