[자료구조] Tree 트리

• 트리구조 알아보기

- node : 트리의 구성요소

- root : 트리 구조에서 최상위에 존재하는 노드

- depth : 루트를 기준으로, 다른 노드로 접근하기 위한 거리

- height : 바닥(...용어의 한계)을 기준으로, 다른 노드로 접근하기 위한 거리

- edge : 노드와 노드를 잇는 선

- leap : 자식이 없는 노드

- sibling : 같은 부모를 가지며, 같은 depth에 존재하는 노드들은 sibling관계에 있다. (걔네 둘을 siblings라고 칭하나?)

• 트리구조의 특징

- 부모자식 관계를 갖는다/ 계층, 그룹으로 표현할 수 있다.

- 트리는 반드시 하나의 루트 노드를 갖는다

- 노드가 n개인 트리는 n-1개의 엣지를 가진다.

• 이진 트리 binary tree

차일드 노드가 최대 2개까지 // 다른 조건없이 차일드가 2개씩 있으면 됨

• 이진 검색트리 binary search tree

차일드 노드가 최대 2개까지 // 노드의 왼쪽 서브트리에는 노드의 값보다 작은 값이, 오른쪽 서브트리에는 노드의 값과 같거나 값보다 커야한다.

• 이진트리의 종류

- complete binary tree / full binary tree / perfect binary tree

 

우분투에 그림판이 어디있는지 모르겠어서 ,, 갤럭시 노트로 예시를 그려봤다

 

 

- complete binary tree : 모든 노드들이 레벨이 맞으면서 왼쪽부터 채워져있는 트리

- full binary tree : 노드가 차일드를를 안가질거면 가지지말고.. 가질거면 두개가져!

- perfext binary tree : 레벨도 같고 차일드도 2개 꽉꽉 !

 

• 이진탐색트리를 순회하는 방법

 

 

• - Inorder Traversal(중위순회) : left, root, right

 

 

출력값 : 4 2 5 1 3

 

• - Preorder Traversal(전위순회) : root, left, right

출력값 : 1 2 4 5 3

 

• - Postorder Traversal(후위순회) : left, right, root

 

출력 : 4 5 2 3 1

 

참고사이트

코드스테이츠 Data structure Part3

www.youtube.com/watch?v=QN1rZYX6QaA

www.youtube.com/watch?v=LnxEBW29DOw

blog.naver.com/coachmsoox/222112984451

이진 / 바이너리 트리 (Binary Tree) 자료구조의 이해 (C언어)