Pre-order traversal
In-order traversal
1
|
2
|
4
|
7
|
8
|
10
|
13
|
14
|
5
|
9
|
11
|
12
|
15
|
3
|
6
|
7
|
4
|
13
|
10
|
14
|
8
|
2
|
5
|
11
|
9
|
12
|
15
|
1
|
3
|
6
|
가 주어졌을 때, 아래와 같은 이진트리를 생성하는 것이다.
Pre-order 순회의 특성상 root node가 먼저 출력되고, in-order 순회의 특성으로는 root node를 기준으로 left sub-tree와 right sub-tree가 나누어진다.
Pre-order traversal
1
|
2
|
4
|
7
|
8
|
10
|
13
|
14
|
5
|
9
|
11
|
12
|
15
|
3
|
6
|
7
|
4
|
13
|
10
|
14
|
8
|
2
|
5
|
11
|
9
|
12
|
15
|
1
|
3
|
6
|
위 표에서 노란색으로 표시한 것이, pre-order traversal의 첫번째 element이자 root node, 분홍색으로 표시한 것은 in-order traversal에서 root node의 left subtree, 연두색으로 표시한 것은 in-order traversal에서 root node의 right subtree이다. In-order traversal에서 left subtree와 right subtree의 크기를 알 수 있으므로, 이를 근거로 pre-order traversal에서도 left subtree와 right subtree에 해당하는 부분을 구할 수 있다 (위 표에서 각각 파란색과 회색으로 표시됨)
Pre-order traversal과 in-order traversal 결과가 주어졌을 때, root node, left subtree, right subtree를 구분할 수 있고, 동일한 방법을 left subtree와 right subtree에 재귀적으로 적용하면, 전체 이진트리를 구성할 수 있다.
func buildTreeFromPreInorderTraversal(preorder, inorder []NodeVal) *Node {
return buildTreeFromPreInorderTraversalUtil(preorder, 0, len(preorder)-1, inorder, 0, len(inorder)-1)
}
func buildTreeFromPreInorderTraversalUtil(preorder []NodeVal, preS, preE int, inorder []NodeVal, inS, inE int) *Node {
if preS > preE {
return nil
}
index := inS - 1
for i := inS; i <= inE; i++ {
if inorder[i] == preorder[preS] {
index = i
break
}
}
node := &Node{
Val: preorder[preS],
Left: buildTreeFromPreInorderTraversalUtil(preorder, preS+1, preS+index-inS, inorder, inS, index-1),
Right: buildTreeFromPreInorderTraversalUtil(preorder, preS+index-inS+1, preE, inorder, index+1, inE),
}
return node
}
댓글 없음:
댓글 쓰기