[자료구조] 이진 트리의 이해

[자료구조] 이진 트리의 이해

연결 리스트는 대표적인 선형 구조의 예이다.

오늘 포스팅할 이진 트리는 비선형 구조의

대표적인 예라 할 수 있겠다.

일단 이진 트리는 

1. 배열 기반

2. 연결 리스트 기반

으로 나눌 수 있는데 연결 리스트 기반으로 알아보자.

이진 트리에 들어가기 앞서 알아둘 내용은

1. 2개의 자식 노드를 가질 수 있다는 점과

2. 하나의 노드도 이진 트리라는 점이다.

자식 노드가 없는 노드는 공집합 노드를 가지게 되는데

자식이 하나 혹은 하나도 없는 노드 또한 이진 트리라고

기대할 수 있게 하기 위함이라고 한다.

이진 트리를 표현한 구조체

헤더 파일에 선언된 함수들

구현

예시

짚고 넘어가야할 부분

구현 부분의 MakeLeftSubTree() 함수를 보면

추가하려는 자리에 기존 데이터가 있으면

삭제하고 대체하게 되는데 이 과정에서

삭제하려는 노드의 서브트리가 존재하게 되면

메모리 누수로 이어지게 된다.

이 해결책으로 순회라는 방법이 있는데

다음 포스팅에 계속 이어 가보도록 하겠다.

이진 트리를 이해하기 위해 간단한 구현을 해보았다.

앞으로 이진 트리에 대한 어마어마한 내용이 남아 있기 때문에

꼭 마스터 하고 넘어가도록 하자.