레벨 순회2 [Java] 트리 Tree 2 - 이진 트리의 순회(전위, 중위, 후위, 반복, 레벨) / 구현 4. 이진트리의 순회 이진트리에 속하는 모드 노드를 한 번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하는 것을 의미 이진트리를 순회하는 표준적인 방법에는 전위, 중위, 후의의 3가지 방법이 있다. 루트와 왼쪽 서브 트리, 오른쪽 서브 트리 중에서 루트를 언제 방문하느냐에 따라 구분된다. 루트를 방문하는 작업을 V 왼쪽 서브 트리 방문을 L 오른쪽 서브트리 방문을 R 루트를 서브 트리에 앞서서 먼저 방문하면 전위 순회 루트를 왼쪽과 오른쪽 서브 트리 중간에 방문하면 중위 순회 루트를 서브 트리 방문 후에 방문하면 후위 순회가 된다. 이진트리에서 각각의 서브 트리 역시 이진트리이다. 전체 트리 순회의 알고리즘을 서브 트리에도 똑같이 적용해 순회한다. -> 문제의 구조는 같고 크기만 작아지는 경.. 2020. 11. 6. [Java] 트리(tree) 구현 - 1차원 배열 / 2차원 배열 / 클래스 3가지 방법 구현 1. 트리 1차원 배열로 구현 주로 포화 이진 트리나 완전 이진트리의 경우 많이 쓰이는 방법이다. 그외의 이진트리도 저장이 불가능한 것은 아니지만 기억공간의 낭비가 심해진다. 따라서 포화 이진 트리이진트리 또는 완전 이진트리를 1차원 배열로 구현해보자. 루트 노드는 1부터 시작한다.(인덱스 0은 사용하지 않는 편이 계산을 간단하게 함) 원하는 노드 n개까지 총 n+1 크기의 1차원 배열을 만든다. 그다음 이진트리의 번호대로 노드들을 저장한다. 배열 표현법에서는 인덱스만 알면 노드의 부모나 자식을 쉽게 알 수 있다. 노드 i의 부모 노드 인덱스 = i / 2 노드 i의 왼쪽 자식 인덱스 = 2i 노드i의 오른쪽 자식 인덱스 = 2i + 1 /** * @author Gwon Minha * * 루트가 1인 완.. 2020. 11. 5. 이전 1 다음 반응형
