데이터 구조 9 (Linked list 활용 , Trees)

• Linked List 활용

 

   ex) list 두 개 같은지 확인하는 프로그램

     재귀함수로 구현

 

  - General  If 둘 다 첫 노드가 가리키는 게 NULL이다 => True

                 + 둘 중 하나가 NULL => False

 

  - NULL 판단 함수 ( 리스트 a , 리스트 b ){

return (같은지 판단하는 함수 (a.head , b.head))

}

 

  - 같은지 판단하는 함수 (*p , *q){

  if ((p ==NULL) and (q==NULL)) ==>  return true // 둘 다 NULL로서 같은 거니까

 

  if ((p ==NULL) or (q==NULL)) ==>  return false; //and조건은 처리 됐으니 이렇게 해도 됨.

 

  if(데이터 내용이 같다(*p,*q)) ==> return(같은지 판단하는 함수(p->link , q->link))

  else ==> return false;

}

 

 

  - '데이터 내용이 같다' 함수 ( node t1 , node t2 ){

if (t1.name != t2.name) ==> return false;

if (t1.score != t2.score) ==> return false;

 

return true;

}

 

 

---

 

• Trees

-Binary trees

→ left subtree, right subtree : 순서는 왼쪽이 먼저임.

 

 

lemma 에서... ->  k-ary 는 degree = k인 노드들을 뜻함.

 

- 임의의 구조로 된 Tree를 Binary로 바꾸는 법

  : Left - (first) child , Right - sibling 

     → [ 모든 tree 는 binary 로 바꿀 수 있다. ] 까지만 알면 됨, 레벨이 달라진다 이런 생각 안 해도 됨.

 

• Traversal  이것도 내려가는 건 왼쪽 먼저 (그냥 트리는 웬만하면 왼쪽으로 내려간다고 생각하셈 , 필요한 경우 빼고)

   → 중복, 누락 없이 모든 데이터를 거치는 것.

 

Inorder  : 거칠 때, [ 노드의 밑 ] 을 지나야 인식함.      

→  노드에서 실을 매달아 바닥에 떨어뜨린다고 생각하고 그 순서대로 해도 된다고 하심.

 

Preorder :    " "     [ 노드의 왼쪽 ] "    "           "     .

 

Postorder :   " "     [ 노드의 오른쪽 ] "    "           "     . 

 

Lv order : Level 순으로 Root부터 인식함, 동일 Lv일 땐, 왼쪽부터

 

참고 - https://youtu.be/kGdnFfi2uz8

 

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