순차적자료구조 vs Tree
지금까지 학습한 내용은 순차적인 자료구조라고 할 수 있다.
스택, 큐, 배열, 연결리스트 등의 자료구조는 순차적인 자료구조로, 데이터의 저장이 순차적으로 된다는 특징이 있으며, 데이터의 접근이 인덱스나, 링크를 통해서 가능하다.
스택, 큐는 리스트를 기반으로 구현되기 때문에 인덱스를 이용한 접근이 가능하다.
연결리스트의 경우는 링크르 따라가면서 특정 데이터가 저장된 노드에 접근이 가능하다.
트리는 위의 순차적자료구조와는 다른 자료구조를 의미한다.
트리
연결리스트를 상상해보자.
head노드 부터 시작해서 링크로 연결되었는데, 이를 수직으로 본다면 하나의 긴 직선이 될 것이다. 트리는 이런 연결리스트에 하나가 아닌 여러개의 노드가 연결되어 있는 것을 의미한다.
연결리스트도 다음 노드가 하나만 있는 특별한 트리형태라고 말할 수 있다.
트리의 형태는 다양하나 가장 일반적인 트리의 형태는 이진트리(Binary Tree)이다.
이진트리는 다음 노드의 갯수가 최대 2개인 것으로 노드가 하나도 없거나, 1개 또는 2개인 것을 의미한다.
트리의 기본 용어는 다음과 같다.
- 루트노드
- 노드
- 링크&에지
- 리프노드
- 레벨
- 높이
- 경로
- 부모노드
- 자식노드
- 형제노드
이진트리를 코드상에 표현하는 방법
코드상에 이진트리를 표현하는 방법은 3가지가 있다.
- 리스트 표현법1
- 리스트 표현법2
- 노드 클래스 표현법
첫번째 방법은 리스트를 이용해서 레벨별로 데이터를 리스트안에 저장해서 표현하는 방법이다. 만약 자식노드가 없는 경우는 None으로 표현해서 빈 공간을 메워준다.
두번째 방법은 재귀적인 표현방법으로 하나의 노드의 왼쪽부트리와 오른쪽 부트리를 표현하는 방법이다. 그리고 다시 왼쪽 부트리를 중심으로 왼쪽부트리와 오른쪽 부트리를 표현하고, 오르쪽부트리를 기준으로 왼쪽부트리와 오른쪽 부트리를 구현하는 방법으로 재귀적으로 표현한다.
세번째 방법은 노드 class를 구현해서 트리를 구현하는 것이다.
트리의 기본 속성으로는 key와 왼쪽, 오른쪽, 부모 노드가 있을 것이다.
