는 중위

Question

예 트리

2 -> root 
1 -> Left 
3 -> right 

순서로 배열에 저장 [1, 2, 3]

어떻게 트리 아는 루트 노드를 검색하여 어레이에 저장된 이진 트리의 루트 노드를 찾아 inorder에 저장되어 있습니까?

나에게 3 가지 가능한 루트 노드 후보자에 따르면.

Answer 1

실제로 3 가지 후보가 모두 가능합니다. (지속적으로 루트를 식별하여 등)

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

인 - 순서 탐색 고유 나무를 식별 할 필요는 충분하지 않습니다 :

여기에 주어진에서 주문 탐색 초래 할 수 나무입니다. 고유 한 트리 요소가 있다고 가정 할 때 선행 순회 또는 순차 순회 탐색과 순서 순회가 필요합니다.

참고 - Which combinations of pre-, post- and in-order sequentialisation are unique?