파이썬 트리 tree !!!

큐, 스택은 선형구조이다.

선형구조랑 자료를 구성하고 있는 데이터들이 순차적으로 나열된 형태이다.

 

트리는 비선형 구조이다.

비선형 구조는 선형구조와는 다르게 데이터가 계층적 혹은 망으로 구성되어 있습니다.

선형구조와 비선형구조의 차이점은 형태뿐만 아니라 용도에서도 차이점이 많다.

 

선형구조는 자료를 저장하고 꺼내는 것에 초점,

비선형 구조는 표현에 초점 ( 폴더 구조가 대표적인 트리 )

 

트리는 계층형 구조이다. 위 아래가 구분되어 있다.

 

트리는 이진 트리, 이틴 탐색 트리, 균형 트리, 이진 힙 등 다양한 트리가 있다.

이진 트리와, 완전 이진 트리만 배워보자

 

이진 트리의 특징은 바로 각 노드가 최대 두개의 자식을 가진다는 것이다.

하위 노드가 4 ~ 5개 일 수 없다. 무조건 0이거나 1이거나 2이어야 한다.

 

완전 이진 트리의 특징은 바로 노드를 삽입할 때 최다한 왼쪽 노드부터 차례대로 삽입해야한다는 것이다.

트리 구조를 표현하는 방법은 직접 클래스를 구현해서 사용하는 방법과,

배열로 표현하는 방법이 있다.

 

완전 이진 트리를 쓰는 경우에는 배열로 표현할 수 있다.

완전 이진 트리는 왼쪽부터 데이터가 쌓이게 되는데, 이를 순서대로 배열에 쌓으면서 표현할 수 있다.

 

예를들어 1번째 인덱스인 8의 왼쪽 자식은 6 오른쪽자식은 3이다.

그럼, 1*2  = 2번째 인덱스 6이고, 

       1*2 + 1 3번째 인덱스 3이다.

부모를 찾아보면 3 // 2 1번째 인덱스 8이므로 부모도 찾을 수 있다.

 

 

트리의 높이는 루트 노드부터 가장 아래 리프 노드까지의 길이이다.

예를들어 다음과 같은 트리의 높이는 2라고 할 수 있다.