[DS] 트리(Tree)에서 이진트리(Binary Tree)로 변환하는 방법

Left_Child-Right_Sibling이란?

트리(tree)를 이진트리(binary tree)로 변형하는 규칙입니다.

left child와 right sibling을 기억해 주세요!

 

 

트리(tree) → 이진트리(binary tree)

---

아래의 트리(tree)를 이진트리(binary tree)로 변형해 보도록 하겠습니다.

Tree

 

처음에는 root(ⓐ)를 하나 그려줍니다.

 

root node의 left child는 ⓑ 노드이고, root(ⓐ) 노드의 sibling(형제)은 없기 때문에 아래와 같이 그려집니다.

 

ⓑ 노드의 left child는 ⓔ 노드이고, sibling(형제)는 ⓒ 노드입니다.

 

ⓔ 노드의 child는 없고 sibling은 ⓕ 노드이며,

ⓒ 노드의 child도 없고 sibling은 ⓓ 노드이므로 아래와 같이 그려줍니다.

 

ⓕ node는 left child도 sibling도 없습니다.

ⓓ 노드는 left child만 있으므로 left child 자리에 ⓖ 노드를 그려줍니다.

 

ⓖ 노드도 left child만 존재하므로 left child 자리에 ⓗ 노드를 그려줍니다.

 

반대로 ⓗ 노드는 sibling만 존재하므로 right child 자리에 ⓘ 노드를 그려줍니다.

 

 

 

이진트리(binary tree) → 트리(tree)

left child와 right sibling를 생각해 보면 right child의 위치가 모두 한 level의 sibling임을 알 수 있습니다.

Right childs을 한 level로 생각해서 다시 그리면 

 

처음 상태인 트리(tree)로 변환할 수 있습니다.

 

 

 

◡̈