트리

트리 = 사이클(엣지를타고 자기자신으로 돌아오는거)이 없는 연결된 그래프 !

 

* 무조건 e=n-1 !

if e>n-1 

-> 사이클이 생겨서 트리아님 !!

 

-차수 = 자식노드 개수 / 트리의 차수=트리에 있는 노드의 최대 차수

 

이진트리 : 노드의 자식이 최대 두개인 트리 !

여기서

*n레벨의 노드 최대 갯수 : 2의 n-1 승

*트리(높이: h) 에서

   -노드 최대 갯수: (2의h승) -1

   -노드 최소 갯수: h

 

• 포화 이진트리 : 다 찬거. 최대로 있는거
• 완전 이진 트리: 높이가 h일때, h-1까진 다채워져있고(노드(2^n-1) -1 개), 노드가 왼쪽에서 오른쪽으로 채워지는 트리
• 편향 이진 트리: 왼쪽이나 오른쪽 서브트리만 가진 트리(쭉쭉쭉 하나씩만)

 

이진트리의 순회 ! - 모든 노드 방문하기 ^.^

-> DFS(스택), BFS(큐)

 

1. DFS - 전위순회, 중위순회, 후위순회

2. BFS - 레벨 순서 순회

 

 

전위순회 = 자기->왼쪽->오른쪽

1) 재귀함수

 자기검사, 왼쪽검사, 오른쪽검사가 반복됨 

자기검사(프린트) -> 왼쪽노드에대해 재귀 -> 오른쪽노드에 대해 재귀

(모든점에 대해 자기검사->왼쪽검사->오른쪽검사해야하므로 !!)

 

종료 조건: 해당노드가 None이면 그냥 return (끝냄)

 

2) 스택자료구조

* 검사를한다 = 프린트를한다 !

검사 대상 = cur !, 검사는 print(cur) 이렇게 !

*stack = 오른쪽 검사 못하고 내려온, 더 검사할 필요가 있는 노드들을 넣어놓는 곳 ! stack이 비면 탐색 끝

 

전체는 while문

cur이 존재하는 애면 cur을 검사하고

계속 left로 내려간다, 그리고 그 cur을 stack에 추가한다 (나중에 더 검사를 해야되니깐)

-> while문으로 구현

 

cur이 이제 none 이 되면 while문 나옴

그러면

stack pop함 (cur=pop())

-> 마지막에 넣은 요소 나옴

그 마지막요소가 none->걍 다 검색한거니까 끝 ! while문 탈출 (탐색 끝)

그 마지막요소가 none아님-> 이제 그친구의 오른쪽을 다시 검색해서 쭈루룩 해야함 ! cur = cur.right

 

(정리 : 현재 노드에서 시작해서 왼쪽 자식 노드가 있으면 쭉 내려감. 왼쪽 자식 노드 다 순회하면 pop이용해서 이전 노드로 이동한 후, 오른쪽 순회함. 오른쪽 순회=현재노드가 그 오른쪽 노드. 이거의 반복)

 

중위 순회 = 왼->자기->오

코드 동일, 순서만 다름

 

스택쓰는 코드 -> pop하고나서 print(방문) ! 나머지는 동일

(pop 순서가 왼쪽갓다가->그위의 중간노드갓다가->오른쪽 가는 순서니까 그냥 pop 순서로 하면 됨)

 

후위 순회 = 왼->오-> 자기

레벨 순서 순회 - 큐 !

자기 래벨인애 - 다음 층에잇는애들 - 다음층에잇는애들 --..