꿈꾸며 개발하기

이진 트리 구현. 배열 : 레벨 순회 순으로 배열에 구성 연결 리스트 : 값과 간선을 관리하기 위한 연결리스트 구성 이진 트리의 순회(Traversal). 모든 노드를 빠뜨리거나 중복하지 않고 방문하는 연산 전위/중위/후위 순회, 레벨순회로 분류할 수 있다. 전위 순회(preorder traversal) 순서 : 부모 노드 → 왼쪽 서브트리 → 오른쪽 서브트리 순서로 노드를 방문 경로 : A → B → D → H → I → E → J → C → F → G 1. 현재 노드 A 출력 → A의 왼쪽 노드 B 출력 → B의 왼쪽 노드 D 출력 → D의 왼쪽 노드 H 출력 (하위 노드 없음) 2. D의 오른쪽 노드 I 출력 → B의 오른쪽 노드 E 출력 -> E의 왼쪽 노트 J 출력 (하위 노드 없음) 3. A의..

시작하며. 지난 글에서 트리 자료구조는 어떤 것인지 왜 이진 트리가 중요한지 등 정리했었다. 이진 트리는 성격에 따라 여러 가지 종류로 분류되며 오늘은 이진 트리란 무엇이고 종류와 특징에 대해서 알아보고자 한다. 이진 트리(Binary Tree). 각 노드는 최대 2개의 자식을 가질 수 있는 트리 자식 노드는 좌우를 구분하여 값을 저장 (왼쪽 자식 : 부모 노드의 왼쪽 / 오른쪽 자식 : 부모 노드의 오른쪽 아래) 이진 트리의 서브 트리는 공백이 될 수도 있고 하나의 서브트리만 가지거나 두 개 모두 가질 수도 있다. 이진 트리의 종류. Perfect binary Tree : 포화 이진 트리 - 모든 레벨의 노드들이 2개씩 다 채워져 있는 트리 - 모든 리프 노드가 같은 레벨에 있어야 함 Complete ..