null 제작자를 통한 순회 (outorder traversal)만으로 이진 트리를 고유하게 재구성 할 수 있습니까?

Question

순서 순회 및 널 제작자만으로 이진 트리를 고유하게 재구성 할 수 있습니까? 그것은이 보인다 널 (null), B, 널 (null), A, 널 (null), C,

Answer 1

A   C 
/\  /\ 
B C  A D 
    \ /
     D B 

널 (null) : 널 (null) 마커

A 
/\ 
B C 

중위 순회는 다음과 같습니다 트리에 대한 예를 들어

, 나무 둘 다 준다 : null, B, null, A, null C, null D, null.

그러나 깊이 N의 이진 트리를 크기 2 ^N -1의 배열로 저장할 수 있습니다.

 A   C 
/ \  / \ 
    B  C  A  D 
/\ /\ /\ /\ 
N N N D B N N N 

NULL, B, NULL, A, C, NULL, D
B, A, NULL, C, D, 널, 널