데이터 구조 10 (Traversal w/o recursion)

Inorder Traversal  <--- stack으로 구현

 

1. 스택 생성 ( pointer type의 노드 원소를 저장함)

2. root부터 시작하여 다음을 반복

 2-1) 현재 node에서 왼쪽으로 가고 NULL이 나올 때까지 Push한다.

 2-2) stack이 empty면 return

      아니면 stack 하나 pop

 2-3) pop한 원소를 traverse.

 2-4) 위에 걸 수행했다는 건, 왼쪽으로 더 갈 수 없다는 의미이므로, 방금 pop한 원소의 오른쪽으로 간다.

 다시 2-1) 부터 반복

 

 

Level order  <--- queue로 구현

 

1. 큐 생성 ( pointer type의 노드 원소를 저장함)

2. root 가 NULL이면 return

3. root를 queue에 넣는다.

4. 다음을 반복

  4-1) queue가 empty면 종료

  4-2) queue로부터 원소하나 가져온다.

  4-3) 그 원소를 traverse

  4-4) 그 원소의 Left가 NULL이 아니면 queue에 넣음

  그런 다음에 그 원소의 Right가 NULL이 아니면 queue에 넣음

  ==> 다음 레벨 애들을 큐에 넣는 거임

 

 

 

 

Tree copy

 

개념은 Root 의 왼쪽노드에는 왼쪽subtree을 붙이고, 

오른쪽 노드에는 오른쪽 subtree을 붙인다

1. 새로운 tree node를 생성

2. node_count 를 copy

3. root 이하의 내용과 동일한 tree 생성하여 root에 copy

 

복사본 만드는 함수

 

 3-1) 주어진 pointer가 Null이면 Null return

         아니면,  node 공간 생성

 3-2) *t = *p 데이터 카피

 3-3) root의 왼쪽을 copy하여 연결          t->left = make_copy(p->left)

 3-4) root의 오른쪽을 copy하여 연결       t->right = make_copy(p->right)

 3-5) 새로 생성한 node의 pointer를 return  return t;

 

 

 

 

Equal test

 

- 시작 전

 Node 개수가 다르면 false

 같으면 동일 여부 판단 실행 

 

root 이하 내용이 같은지 check 하여 그 결과를 return

 

- 동작

  두 root가 모두 NULL -> true 리턴

  두 root 중 한 개만 NULL ->false 리턴

 

  두 root의 data값이 다르면  -> false 리턴

  

  ((왼쪽 내용이 같다) and (오른쪽 내용이 같다)) --> 이거 short evaluation 임! 왼쪽이 false면 다음 조건 실행 안 함

    true 리턴

아니면 false 

 

주의할 점으로는 첫 함수에서 parameter로 복사하는 tree는 주소로 들어오고

                                                                    복사해서 새로 만들어질 tree는 그냥 tree 클래스로 들어온다

 

 

 

 

출처 한동대학교 김호준 교수님 - 데이터 구조 PPT