Contents

조회 수 8233 댓글 0
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄
트리 순회에 대해서 알아보겠습니다.
트리 순회(tree traversal)
- 트리에 있는 모든 노드를 한번씩 방문하는 것.
- 완전한 순회는 트리에 있는 데이타의 선형순서를 생성.

분류
- 스택을 이용하는 방법
   - 중위순회( Inorder traversal )
   - 전위순회( Preorder traversal )
   - 후위순회( Postorder traversal )
- 큐를 이용하는 방법
   - 레벨 순서 순회( Level order traversal )

순회방법
- 중위순회
  : 일단 널 노드를 만날 때 까지 왼쪽으로 이동한다.
    널 노드를 만나면 널 노드의 부모를 방문한다.
    순회는 오른쪽으로 계속된다.
    오른쪽으로 이동이 불가능 할 때는 바로 위 레벨의 방문하지 
    않은 노드에서 순회가 계속된다.

   void inorder( tree_pointer ptr )
   {
       if( ptr )
       {
           inorder( ptr -> left_child );
           printf("%d", prt -> data );
           inorder( ptr -> right_child );
       }
   }

- 전위순회
  : 노드를 먼저 방문한다.
    다음으로 왼쪽 가지의 모든 노드를 방문한다.
    널 노드에 도달하면 오른쪽 자식을가진 가장 가까운 조상으로 간다.
    오른쪽 자식에게 순회를 계속한다.

   void preorder( tree_pointer ptr )
   {
       if( ptr )
       {
           printf("%d", prt -> data );
           preorder( ptr -> left_child );
           preorder( ptr -> right_child );
       }
   }

- 후위순회
  : 노드를 방문하기 전에 왼쪽 오른쪽 자식을 먼저 방문한다.
    다음으로 왼쪽 가지의 모든 노드를 방문한다.

   void postorder( tree_pointer ptr )
   {
       if( ptr )
       {
           postorder( ptr -> left_child );
           postorder( ptr -> right_child );
           printf("%d", prt -> data );
       }
   }

순회방법
- 레벨순서순회
  : 루트를 큐에 삽입하는 것으로 시작.
    큐에서 노드를 삭제(가져옴)하여 데이타를 출력(방문)하고
    그 노드의 왼쪽 자식과 오른쪽 자식을 큐에 다시 삽입한다.
    큐가 비워질 때까지 계속한다.

   void levelorder( tree_pointer ptr )
   {
       if(!ptr)
           return;
       addq(rear,ptr);
       for(;;)
       {
           ptr = deleteq(front);
           if( ptr )
           {
               printf("%d", prt -> data );
               if( ptr->left_child )
               {
                   addq( rear, ptr -> left_child );
               }
               if( ptr->right_child )
               {
                   addq( rear, ptr -> right_child );
               }
           }
           else break;
       }
   } 


?

List of Articles
번호 분류 제목 글쓴이 날짜 조회 수
129 Develop [c] 단어 입력/수정 프로그램 소스 file hooni 2003.04.23 6994
128 Develop [c] 농구팀 점수 산출 프로그램 소스 file hooni 2003.04.23 7350
127 Develop [자료구조] 트리(tree) 용어정리 file hooni 2003.04.23 11034
126 Develop [c] 이진트리(binary tree)의 특성 file hooni 2003.04.23 9576
» Develop [c] 이진트리(binary tree)의 운행.. hooni 2003.04.23 8233
124 Develop [c] 근의 공식으로 2차방정식 풀기.. file hooni 2003.04.23 7742
123 Develop [c] 학생명단 관리 프로그램 소스 ㅋㅋ 1 file hooni 2003.04.23 7739
122 Develop [jsp][php] 간단한 강좌 자료.. file hooni 2003.04.23 8078
121 Develop [c] flooding 알고리즘 미로 찾기(도스용) 소스코드 9 file hooni 2003.04.23 12432
120 Develop [c] 테트리스(Tetris) 게임(도스용) 소스코드 file hooni 2003.04.23 11441
119 Develop [c] 파일입출력, 링크리스트(linked list)를 이용한 주소록(도스용) 소스코드 1 file hooni 2003.04.23 11118
118 Develop [c] 간단한 자료구조(stack, queue, linked list) 구현 소스 6 file hooni 2003.04.23 10084
Board Pagination Prev 1 ... 83 84 85 86 87 88 89 90 91 92 ... 98 Next
/ 98