×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 2,791,955명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)
busyhuman: 5000원(유용한 지식 감사합니다.)
익명 : 5000원(알고리즘 학습러)
반응형

이진트리를 조사하기 위해서는 마음대로 찾아도 되지만, 정형화 된 방법들이 있다.


이것을 순회라고 하는데 그중 가장 많이 쓰이는 순회가 전위 순회, 중위 순회, 후위 순회가 있다.



높이가 2 이상인 트리 또한 같은 방법으로 순회를 하면 된다.


이 과정을 하나하나 표현 할 필요 없이, 재귀(Recursive)형태로 순회를 구성하면 높이에 무관한 순회를 할 수 있게 된다. 




중위 순회 이진 트리의 예




중위 순회의 추상적 관점으로의 단계 해석


1단계 왼쪽 서브 트리의 순회를 시작한다.

2단계 루트 노드를 방문한다.

3단계 오른쪽 서브 트리의 순회를 시작한다.




중위 순회의 간단한 코드


1
2
3
4
5
6
void InorderTraverse(BTreeNode *bt)
{
    InorderTraverse(bt->left);
    printf("%d \n", bt->data);
    InorderTraverse(bt->right);
}
Crocus



왼쪽을 들리고 재귀로 형성되니 왼쪽으로 계속 돌게 될것이다.


그다음 다 돌고나면 자신의 data를 print하고


마지막으로 오른쪽으로 도는데 오른쪽으로 가자마자 왼쪽에 노드가 또 있다면 다시 왼쪽부터 계속돌게 되는 재귀형식이다.


(이 코드는 불완전한 코드(재귀의 탈출 조건을 제대로 하지 않았다.)이지만, 이러한 형식으로 이루어 지다는 것을 알아두자.)



반응형
  1. 가을하늘 2016.06.09 03:38

    좋은 정보 잘보고 갑니다