이진 트리의 운행법(Traversal)

트리를 구성하는 각 노드들을 찾아가는 방법을 운행법이라 합니다

이진 트리를 운행하는 방법은 산술식의 표기법과 연관성을 갖습니다.

---

트리의 운행법

이진 트리의 운행법은 다음 세 가지가 있다.

• Preorder 운행 : Root -> Left -> Right 순으로 운행한다.
• Inorder 운행 : Left -> Root -> Right 순으로 운행한다. 
• Postorer 운행 : Left -> Right  -> Root 순으로 운행한다. 

---

수식의 표기법

산술식을 계산하기 위해 기억공간에 기억시키는 방법으로 이진 트리를 많이 사용한다.

이진 트리로 만들어진 수식을 인오더, 프리오더, 포스트오더로 운행하면 각각 중위, 전위, 후위 표기법이 됩니다.

---

스레드 이진 트리(Threaded Binary Tree)

스레드 이진 트리는 이진 트리엣어 발생하는 널 링크를 트리운행에 필요한 다른 노드의 포인터로 사용하도록 고안된 트리를 말합니다

이진 트리를 이중 연결 리스트로 표현할 때 임의의 노드에 대한 자식 노드가 없는 부분의 링크 포인터로 Nil Pointer를 기억시키게 됩니다.

 

스레드 이진 트리 표현 방법은

1. 어떤 노드의 왼쪽 링크 포인터가 Nil.이면 그 노드의 직전에 검사된 노드를 가리키는 포인터로 사용하고, 오른쪽 링크 포인터각 Nil이면 그 노드의 직후에 검사될 노드를 카리키는 포인터로 사용합니다.

 

2.해당 노드의 직전, 직후 노드는 트리의 운행법에 따라 방문한 노드의 순서대로 결정합니다.