트리 그리는 법: 맨 위에 노드를 하나 그리고 간선으로 연결된 노드들을 아랫줄에 그려나간다 트리의 조건: 사이클이 없고 한 노드에서 모든 노드로 갈 수 있어야 한다 루트: 가장 위의 노드 부모 노드: 어떤 노드 위쪽에 있는 노드 자식 노드: 어떤 노드의 아래쪽에 있는 노드 리프: 가장 끝에 있는 노드
노드의 수가 n개 일 때 간선의 수는? n-1개 루트를 제외한 모든 노드는 부모 노드와 연결된다 자식 노드끼리 연결하는 순간 사이클이 생긴다
이진 트리: 모든 자식 노드가 최대 두 개 존재하는 트리
이진 트리 순회: 이진 트리의 모든 노드의 값을 출력하는 방법이 크게 3가지가 있다 이진 트리 순회의 공통점: 루트에서 시작하고 왼쪽을 탐색한 뒤 오른쪽을 탐색한다 1)전위 순회: ABDECFG 현재 보고 있는 노드를 출력한 뒤 왼쪽으로 내려가고 왼쪽에 대한 처리가 끝나면 오른쪽으로 내려간다. 모든 처리가 끝나면 올라간다 2)중위 순회: DBEACFG 현재 보고 있는 노드의 왼쪽으로 내려가고, 왼쪽에 대한 처리가 끝나면 현재 노드를 출력한 뒤 오른쪽으로 내려간다. 모든 처리가 끝나면 올라간다 3)후위 순회: DEBGFCA 현재 보고 있는 노드의 왼쪽으로 내려가고, 왼쪽에 대한 처리가 끝나면 오른쪽으로 내려간다. 오른쪽에 대한 처리가 끝나면 현재 노드를 출력한 뒤 올라간다
트리 복구: 중위 + 전위/후위 통해 나머지 하나의 순회 결과를 알 수 있다
전위와 후위만으로는 트리복구를 할 수 없다 전위 순회는 출력을 먼저 한다. 루트가 맨 앞에 있다 후위 순회는 출력을 마지막에 한다. 루트가 맨 뒤에 있다 중위 순회에서 루트보다 먼저 출력된 것은 루트의 왼쪽에 있는 노드이고 루트보다 나중에 출력된 것은 루트의 오른쪽에 있는 노드이다
예제 - 트리복구
다음 이진 트리 순회결과를 이용해 트리를 복구해보자 전위 순회 결과: A B D C E F G 중위 순회 결과: D B A F E G C
해답
다음 이진 트리 순회결과를 이용해 트리를 복구해보자 중위 순회 결과: D B F E G A C H 후위 순회 결과: D F G E B H C A
