이진 트리

트리의 특징: 노드 사이의 연결 관계가 계급적인 구조를 가진다.

트리의 형태와 용어들

이진 트리의 순회 방법

전위 순회(preorder traversal): root B C

중위 순회(inorder traversal): B root C 

후위 순회(postorder traversal): B C root

전위 순회: root -> b -> c 순으로 크게 생각을 하고 b의 묶음으로 들어가서 2 -> 4 다음에 왼쪽 자식이 없으면 오른쪽으로 넘어간다. 이렇게 생각을 한다. 이런 식으로 반복을 한다면 2-> 4-> 7-> 8-> 9 형태의 b 묶음이 나온다.

다음으로 c 묶음이다. c도 마찬가지로 3-> 5-> 6이 된다.

1 -> 2 ->4 ->7- 8 -> 9 -> 3-> 5 ->6  명심하자! root(1)는 처음이다! 

 

중위 순회: b -> root -> c 순으로 크게 생각을 하고 b의 묶음으로 들어가면  4-> 8-> 7-> 9 -> 2 가 나올 것이다. 예를 들자면, 만약에 4왼쪽에도 7,8,9와 같은 자식이 있다.(a, b, c라고 가정했을 때) 그렇다면 b-> a-> c-> 4-> 8-> 7-> 9 -> 2 이렇게 생각을 한다면. b형태의 묶음이 나온다.

다음으로 c 묶음이다. c도 마찬가지로 5-> 3-> 6 이 된다.

4-> 8-> 7-> 9 -> 2 -> 1 -> 5-> 3-> 6  명심하자! root(1)는 중간이다! 

 

후위 순회: b -> c-> root순으로 크게 생각을 하고 b의 묶음으로 들어가면  8-> 9-> 7-> 4 -> 2 가 나올 것이다. 예를 들자면, 만약에 4왼쪽에도 7,8,9와 같은 자식이 있다.(a, b, c라고 가정했을 때) 그렇다면 b-> c-> a-> 8-> 9-> 7 -> 4 -> 2 이렇게 생각을 한다면. b형태의 묶음이 나온다.

다음으로 c 묶음이다. c도 마찬가지로 5-> 6-> 3이 된다.

8-> 9-> 7 -> 4 -> 2 -> 5-> 6-> 3 -> 1명심하자! root(1)는 마지막이다!