주어진 순회에서 어떻게 이진 트리를 찾을 수 있습니까?

Question

주어진 순회 방법 (inorder, post-order 또는 pre-order)에서 이진 트리를 어떻게 찾을 수 있습니까?

Answer 1

중위에 대한 위키 피 디아 기사는, 이후 순서는 예약 주문 트리 탐색은 여기에 있습니다 :

http://en.wikipedia.org/wiki/Tree_traversal.

찾고있는 트리는 검색어와 일치하는 노드에서 시작됩니다.

Answer 2

트래버스 결과를 사용하여 원본 트리를 복원하려는 경우 몇 가지 나쁜 소식이 있습니다. 명확한 해결책은 없습니다. 동일한 트래버스 결과를 생성 할 수있는 여러 개의 트리가 있습니다.

동일한 결과를 생성합니다 중위 순회 다음 나무에 대한 예를 들면 : 당신은 하나의 통과 (중위, 예약 주문 또는 Postorder)로하여이 작업을 수행 할 수 없습니다 1, 2, 3

2   3  1 
/\  /  \ 
    1 3  2   2 
      /   \ 
      1    3 

Answer 3

.

트리의 중위 & 전순 주사가 주어진다면 그것은 수행 할 수 있습니다

: 전순의

1. 첫 번째 요소는 나무의 뿌리가 될 것입니다. (A라고 가정하십시오)
2. Inorder에 Searc 루트가 있으므로 root의 왼쪽에있는 모든 노드는 왼쪽 하위 트리의 Inorder이고 오른쪽 노드는 오른쪽 하위 트리의 Inorder입니다. 루트의 왼쪽에있는 노드의 수를 계산하십시오. L.
3. 두 번째 L 노드로부터의 포스트 오더는 왼쪽 하위 트리의 선주문이되며 그 후에 오른쪽 하위 트리의 사전 순서입니다.

우리는 루트 요소를 발견하고 왼쪽 하위 트리의 Inorder, 오른쪽 하위 트리의 Inorder 및 Preorder를 왼쪽 하위 트리와 오른쪽 하위 트리의 사전 주문에 배치했습니다. 그래서 하나의 노드 만 남아있을 때까지 재귀를 통해이를 수행 할 수 있습니다.

마찬가지로 Inorder와 Postorder에서 root가 게시물 순서의 마지막 요소가 될 수 있습니다.

Answer 4

(좋아, 우리는 amended question뿐만 아니라 거기에 내 대답을 게시, 여기해야한다고 결정했습니다 이후) 이진 트리의

Postorder 및 중위 순회가 가능 얻기 위해 below.Is 주어진다 이 순회의 고유 한 이진 트리?

가능합니다.

포스트 트리 탐색 (왼쪽 - 오른쪽 루트)에서 전체 트리의 루트 노드는 항상 마지막 것입니다 (귀하의 경우에는 A입니다). inorder traversal (left-root-right)에서 루트 이전의 노드는 왼쪽 서브 트리에 속하고 루트 뒤의 노드는 오른쪽 노드에 속합니다. 이미 루트를 결정 했으므로 왼쪽 하위 트리와 오른쪽 하위 트리에서 노드를 결정할 수 있습니다.

결론은 우리는 후순위 목록에서 왼쪽 및 오른쪽 하위 트리를 구분할 수 있다는 것입니다.이제 왼쪽 및 오른쪽 하위 트리와 루트 노드를 결정했습니다.

postorder: left|right|root 
inorder : left|root|right 

이제 우리는 왼쪽 및 오른쪽 하위 트리를 재귀 적으로 만들어야합니다. 지느러미.