[자료구조] forest/traverse

forest F에 대응하는 binary tree T의 preorder, inorder traverse는 F의 순회와 자연스러운 대응 관계를 가진다. 

[Preorder Traverse]

T의 preorder traverse는 다음과 같이 정의된 forest preorder로 F의 노드들을 traverse하는 것과 동일하다. 

(1)F의 첫번째 tree의 node 방문

(2)첫번째 tree의 subtree를 preorder traverse한다.

(3) F의 나머지 tree들을 preorder traverse한다

 

[Inorder Traverse]

T의 preorder traverse는 다음과 같이 정의된 forest inorder로 F의 노드들을 traverse하는 것과 동일하다. 

(1)F의 첫번째 tree의 subtree를 forest inorder로 traverse한다.

(2)첫번째 tree의 root를 방문

(3) 나머지 tree를 forest inorder로 traverse

 

 

[Postorder Traverse]은 없다. 

(1)F의 첫번째 tree의 subtree를 forest postorder로 traverse한다.

(2) 나머지 tree를 forest postorder로 traverse

(3)첫번째 tree의 root를 방문

은 아니다. 

 

 

binary tree를 traverse해서 원하는 결과는 

D C B F I H G E A 이다. 

 

하지만...

F I H G E 이런식으로 섞인것을 볼 수 있다.