이진 트리 순회2 이진 트리의 순회 지난 포스트에서 이진 트리를 구현해 보면서, 트리 삽입 과정에서 문제가 발생했었습니다. 트리의 하위 트리가 존재하는 경우 그 아래 트리의 메모리가 반환되지 않아 메모리 낭비가 일어나는 과정이었는데요. 이 과정을 순회 라는 개념으로 해결할 수 있다고 했었습니다. 1. 순회 순회는 트리의 모든 노드를 중복이나 빠지는 것 없이 처리하는 연산입니다. 그동안 우리가 다뤘던 스택, 큐같은 자료구조들을 자료가 1:1 구성을 가졌기에 따로 순회할 필요가 없었습니다. 그러나 트리는 1:다수의 관계이기 때문에 현재 노드에서 어떤 다음 노드를 처리할지에 대한 연산이 필요하며, 이 연산을 순회라고 합니다. 순회는 루트 노드의 방문 순서를 기준으로 세 가지 종류로 나뉩니다. 전위 순회 중위 순회 후위 순회 전위 순회는 루트 노.. 2021. 9. 27. 이진 트리 구현 두개의 포스트에 걸쳐서 이진 트리를 설명했으니 드디어 구현에 들어가볼 차례입니다. 1. 배열로 이진 트리 구현하기? 트리도 배열을 이용해서 구현할 수는 있습니다. 그림처럼 노드에 번호를 부여하고 배열의 인덱스와 노드 번호를 일치시켜 데이터를 저장하죠. 다시 말하자면 배열의 크기를 (노드의 수+1) 만큼 잡고 인덱스 0번을 제외한 나머지 번호를 이용해서 구현합니다. 하지만 크기 가변이 힘들고, 위와 같은 그림의 완전 이진 트리가 아닌경우에, 비는 인덱스가 생긴다는 등의 문제로 인해서 일반적으로 트리를 배열로 구현하지는 않습니다. 물론 이진 트리 마지막에 소개드릴 '히프'라는 자료구조가 있는데, 이 구조에서 배열을 이용하게 됩니다. 2. 연결 리스트로 이진 트리 구현하기 노드 특히 양방향 노드를 이용하면 이.. 2021. 9. 24. 이전 1 다음 300x250
