본문 바로가기

Binary Tree

[자료구조/java] 이진 트리 (Binary Tree) 의 순회 (traversal) * 이진 트리 (Binary Tree) 의 순회 (traversal) "순회(traversal)" 이진 트리에 있는 모든 노드를 한번씩 모두 방문하여 노드가 가지고 있는 데이터를 처리하는 것 - 리스트나 스택, 큐와 같은 선형 자료구조는 순회하는 방법이 한 가지였지만, 트리는 계층적인 구조를 가지고 있기 때문에 여러가지 순회 방법이 있을 수 있다. (1) 현재 노드를 방문하여 데이터를 읽는 작업 D (2) 현재 노드의 왼쪽 서브트리로 이동하는 작업 L (3) 현재 노드의 오른쪽 서브트리로 이동하는 작업 R - 서브트리를 순회하는 순서는 항상 왼쪽 서브트리를 먼저 방문하고, 그 후에 오른쪽 서브트리를 방문한다.- 노드를 방문하는 순서에 따라 전위 순회, 중위 순회, 후위 순회로 나눌 수 있다. ★ 전위 순.. 더보기
[자료구조/java] 이진 트리 (Binary Tree) - 순차 자료구조 방식, 연결 자료구조 방식 * 이진 트리 (Binary Tree) 구현 - 순차 자료구조 방식 - 이진트리를 배열로 표현하는 방법은 높이가 h인 포화 이진 트리의 노드번호를 배열의 인덱스로 사용하여 1차원 배열로 표현 - 1차원 배열에서 인덱스 계산을 간단히 하기 위해서 인덱스 0번은 실제로 사용하지 않고 비워두고 항상 인덱스 1번에 루트를 저장 이진 트리를 표현한 1차원 배열에서의 인덱스 관계를 나타낸 표이다. * 이진 트리 (Binary Tree) 구현 - 연결 자료구조 방식 - 배열을 이용한 순차 자료구조 방식은 쉽게 만들 수 있고, 인덱스 규칙에 따라 노드를 찾는 것이 쉽다. - 하지만 메모리 사용에 있어서 완전 이진 트리의 경우 최적의 공간 사용이 되지만, 편향 이진 트리의 경우 많은 공간이 낭비된다. - 메모리 문제와 .. 더보기
[자료구조/java] 이진 트리 (Binary Tree) * 이진 트리 (Binary Tree) "노드의 차수를 2 이하로 정하여 트리의 노드구조를 일정하게 정의함으로써 연산을 단순화 시킨 트리" - 이진트리는 왼쪽 자식노드와 오른쪽 자식노드 2개만을 가질 수 있다. (공백 노드도 이진 트리의 노드로 취급)- n개의 노드를 가지는 이진 트리는 항상 (n-1)개의 간선을 가진다. - 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 (h+1)개가 되며, 최대 개수는 (2^(h+1)-1)개가 된다. * 이진 트리 (Binary Tree)의 분류 포화 이진 트리(Full Binary Tree)- 모든 레벨에 노드가 꽉 차서 포화 상태인 이진 트리를 의미- 높이가 h 일때 2^(h+1)-1 개의 최대 노드수를 갖는 이진트리 완전 이진 트리(Complete B.. 더보기