# 在预订和按顺序之后用两个列表重建二叉树

##### 问题描述投票：0回答：2

- 给出了两个列表，一个按预订排序，另一个按顺序排序。这两个列表来自同一个二叉树。使用这两个列表，二叉树是--reconstructed。

- 我还没有在网上找到“排名”功能。我的教授告诉我们，函数“rank”可以输出列表中一个元素的位置。

1. 功能如何“排名”？
2. 表达式“reconstruct :: [Int] - > IntTree”是否正确？我不确定。
``````main :: IO ()    -- This says that main is an IO action.
main = return () -- This tells main to do nothing

data IntTree = Empty | Branch IntTree Int IntTree deriving (Show, Eq)

reconstruct :: [Int]->IntTree
--  Pattern matching
reconstruct (x:xs) y = Branch (reconstruct take((rank x y) xs) take ((rank x y) y)) x x (reconstruct drop ((rank x y)+1 xs) drop ((rank x y)+1 y))
``````

``````import Data.List

main :: IO ()    -- This says that main is an IO action.
main = return () -- This tells main to do nothing

data IntTree = Empty | Branch IntTree Int IntTree deriving (Show, Eq)

--Two lists are given, one sorted by preorder, the other sorted by inorder.
-- And the two lists are from the same binary tree. With the two lists the binary tree is reconstructed.

reconstruct :: [Int]->[Int]->IntTree
--  Pattern matching
reconstruct [] [] = Empty
reconstruct (x:xs) y = Branch (reconstruct take (length (fst p) xs) (fst p)) x (reconstruct drop (length (fst p) xs) (snd p))
where p = span (x/=) y

reconstruct _ _ = error "incomplete pattern"

``````

``````
* Couldn't match expected type `[Int] -> IntTree'
with actual type `IntTree'
* The function `reconstruct' is applied to three arguments,
but its type `[Int] -> [Int] -> IntTree' has only two
In the first argument of `Branch', namely
`(reconstruct take (length (fst p) xs) (fst p))'
In the expression:
Branch
(reconstruct take (length (fst p) xs) (fst p))
x
(reconstruct drop (length (fst p) xs) (snd p))
|
15 | reconstruct (x:xs) y = Branch (reconstruct take (length (fst p) xs) (fst p)) x (reconstruct drop (length (fst p) xs) (snd p))

|                                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

* Couldn't match expected type `[Int]'
with actual type `Int -> [a0] -> [a0]'
* Probable cause: `take' is applied to too few arguments
In the first argument of `reconstruct', namely `take'
In the first argument of `Branch', namely
`(reconstruct take (length (fst p) xs) (fst p))'
In the expression:
Branch
(reconstruct take (length (fst p) xs) (fst p))
x
(reconstruct drop (length (fst p) xs) (snd p))
|
15 | reconstruct (x:xs) y = Branch (reconstruct take (length (fst p) xs) (fst p)) x (reconstruct drop (length (fst p) xs) (snd p))

|                                            ^^^^

* Couldn't match expected type `[Int] -> [Int]'
with actual type `Int'
* The function `length' is applied to two arguments,
but its type `[Int] -> Int' has only one
In the second argument of `reconstruct', namely
`(length (fst p) xs)'
In the first argument of `Branch', namely
`(reconstruct take (length (fst p) xs) (fst p))'
|
15 | reconstruct (x:xs) y = Branch (reconstruct take (length (fst p) xs) (fst p)) x (reconstruct drop (length (fst p) xs) (snd p))

|                                                  ^^^^^^^^^^^^^^^^^

* Couldn't match expected type `[Int] -> IntTree'
with actual type `IntTree'
* The function `reconstruct' is applied to three arguments,
but its type `[Int] -> [Int] -> IntTree' has only two
In the third argument of `Branch', namely
`(reconstruct drop (length (fst p) xs) (snd p))'
In the expression:
Branch
(reconstruct take (length (fst p) xs) (fst p))
x
(reconstruct drop (length (fst p) xs) (snd p))
|
15 | reconstruct (x:xs) y = Branch (reconstruct take (length (fst p) xs) (fst p)) x (reconstruct drop (length (fst p) xs) (snd p))

|                                                                                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

* Couldn't match expected type `[Int]'
with actual type `Int -> [a1] -> [a1]'
* Probable cause: `drop' is applied to too few arguments
In the first argument of `reconstruct', namely `drop'
In the third argument of `Branch', namely
`(reconstruct drop (length (fst p) xs) (snd p))'
In the expression:
Branch
(reconstruct take (length (fst p) xs) (fst p))
x
(reconstruct drop (length (fst p) xs) (snd p))
|
15 | reconstruct (x:xs) y = Branch (reconstruct take (length (fst p) xs) (fst p)) x (reconstruct drop (length (fst p) xs) (snd p))

|                                                                                             ^^^^

* Couldn't match expected type `[Int] -> [Int]'
with actual type `Int'
* The function `length' is applied to two arguments,
but its type `[Int] -> Int' has only one
In the second argument of `reconstruct', namely
`(length (fst p) xs)'
In the third argument of `Branch', namely
`(reconstruct drop (length (fst p) xs) (snd p))'
|
15 | reconstruct (x:xs) y = Branch (reconstruct take (length (fst p) xs) (fst p)) x (reconstruct drop (length (fst p) xs) (snd p))

|                                                                                                   ^^^^^^^^^^^^^^^^^
[Finished in 0.5s]

``````
##### 2个回答
1

``````reconstruct :: [Int] -> [Int] -> IntTree
reconstruct [] [] = Empty
reconstruct (x:xs) y = let (l,_:r) = span (x /=) y
(l',r') = splitAt (length l) xs
in Branch (reconstruct l' l) x (reconstruct r' r)
reconstruct _ _ = error "incomplete pattern"
``````

0

``````(reconstruct take (length (fst p) xs) (fst p))
``````

``````(reconstruct (take (length (fst p)) xs) (fst p))
``````