[알고리즘 위한 한발짝 두발짝🐾] 트리(tree) 자료구조

<본 블로그는 코딩문 codingmoon 님의 유튜브를 참고해서 공부하며 작성하였습니다 :-)>

=> 코딩테스트 & 기술면접 을 위한 트리(tree) 자료구조

 

🫧 트리(tree) 자료구조

: 노드의 앞 뒤 관계가 1:N or N:M

: 비선형 계층적 구조

: 하나의 tree 에는 하나의 root 가 있음

: 각 node 는 하나의 객체로 표현됨

: node 에 데이터와 자식 노드 저장 가짐

: size 는 root 포함 모든 node 의 수

: depth 는 node 에서 root 까지의 거리

: height는 노드 깊이의 최대값

 

 🐾binary tree (이진 트리)

: 각 노드가 최대 두개의 자식 노드를 가지고 있는 tree

: 각 노드가 0에서 최대 2개의 child 노드 갖는다

 

🐾 binary search tree (이진탐색트리)

: 왼쪽 자식 노드 값 < 부모 노드 값

: 부모 노드 값 < 오른쪽 자식 노드 값

 

🐾 tree traversal (트리 순회)

- in-order traversal (중위 순회) : left -> visit -> right

- pre-order traversal (전 순회) : visit -> left -> right

- post-order traversal (후위 순회) : left -> right -> visit