이진트리2 8장 - 트리 지금껏 살펴본 자료구조들은 선형 자료구조였다. 파일 디렉토리처럼 계층적인 자료를 나타낼 때는 트리라는 자료구조를 사용한다. 트리는 노드라는 데이터 단위들이 수직으로 연결되어 있는 형태다. 트리 용어 정리 노드, 루트, 서브트리, 간선, 부모노드, 자식노드, 단말노드,레벨는 기본적으로 알고 있을 것이다. 차수(Degree)란 어떤 노드가 가지고 있는 자식 노드의 개수를 의미한다. 트리의 차수는 차수 중 최대값이다. 트리의 높이는 트리의 최대 레벨을 의미한다. 레벨 h는 log2(n+1)보다 크고 n보다 작다. 차수가 동적이면 표현하기 복잡하니 노드들의 차수가 모두 2인 트리인 이진트리만 다루도록 하자. (이진트리의 단말 노드도 차수가 2이다.) 이진트리란? 1. 공집합이거나 2. 루트와 왼쪽 서브트리, 오.. 2020. 11. 14. 이진트리와 순회 이진트리는 모든 노드가 두개의 서브트리를 가지고 있는 트리를 이진트리라고 한다. 서브트리는 공집합일 수 있다. 따라서 이진트리의 노드에는 최대 두개의 자식노드를 가질 수 있다. 또한 서브 트리간에 순서가 존재한다. 정확히 설명하자면 1. 공집합이거나 2. 루트와 왼쪽 서브트리, 오른쪽 서브트리로 구성된 노드들의 유한집합으로 정의된다. 이진트리의 서브 트리들은 모두 이진트리여야한다. 이처럼 이진트리는 재귀적으로 정의되기 때문에 재귀 알고리즘을 쓰는 것이 여러모로 편리하다 이진트리의 종류 포화 이진트리 트리의 각 레벨에 노드가 꽉 차 있는 트리, 높이를 k라 한다면 등비수열 합 공식에 의해 노드 수는 2^k -1개 완전 이진트리 트리의 높이가 k일 때 k-1까지는 노드가 모두 채워져있고 마지막 레벨에서는 노.. 2020. 9. 7. 이전 1 다음
