자료구조 <의사결정트리> 알고리즘 이해

의사결정트리

부모 자식을 나타내는 알고리즘

서브트리

트리의 리부를 때다가 보면 그 친구도 트리형태를 띄고 있다라는 것

즉, 트리의 일부도 트리다. 재귀적이다. 그럼 재귀함수를 이용해서 탐색하고 호출할 수 있게 된다.

이진트리

자식을 최대 2개까지만 제한하는 것이 이진트리이다.

공집합도 이진트리에서는 노드로 간주

비어있는 노드도 자식노드라고 이해해야 한다.

즉, 자식이 2개를 초과하지 않으면 이진트리라고 할 수 있다.

포화이진트리 → 모든 레벨에 노드가 꽉 찬 트리

완전이진트리 → 위에서 아래로 왼쪽에서 오른쪽으로 채워진 트리

 

이진트리는 레벨별로 개수가 보장이 된다는 장점을 가지고 있다.

즉, 레벨에 대한 순번 및 개수가 정해진다는 소리

 

편의상 배열의 첫번째 요소는 사용하지 않는다.

그래서 배열의 arr[0]는 비워둔다는 소리

이진트리 알고리즘 이해하기

한 줄씩 코드 이해하기