이진트리

이진탐색트리란? 이진탐색트리는 다음의 조건을 만족하는 이진트리이다. 모든 노드는 각각 유일한 키(key)를 가진다. 루트 노드의 왼쪽 서브 트리는 루트 노드 보다 작은 키 값으로 이루어져 있다. 루트 노드의 오른쪽 서브 트리는 루트 노드 보다 큰 키 값으로 이루어져 있다. 좌우 서브 트리 모두 이진탐색트리이다. 이진트리에 정보가 필요하다면 참고하길 바란다. 2023.11.29 - [자료구조/비선형 자료구조(Non-Linear)] - [자료구조] 이진트리(Binary-Tree)란? [자료구조] 이진트리(Binary-Tree)란? 이진트리란? 각 노드가 최대 2개의 자식을 갖는 트리이다. 하나의 노드의 자식이 3개 이상은 이진트리로 볼 수 없다. 이진트리의 특징 각 노드는 최대 2개의 자식을 가질 수 있으며..

이진트리란? 각 노드가 최대 2개의 자식을 갖는 트리이다. 하나의 노드의 자식이 3개 이상은 이진트리로 볼 수 없다. 이진트리의 특징 각 노드는 최대 2개의 자식을 가질 수 있으며, 왼쪽과 오른쪽 자식노드로 구분한다. 순회 방법은 전위 순회, 중위 순회, 후위 순회가 있다. 이진트리의 종류 전이진트리(Full Binary Tree or Strict Binary Tree) 모든 노드의 자식이 0개, 또는 2개의 자식을 갖는 트리를 말한다. 왼쪽 이미지의 경우, J의 노드가 K라는 자식을 갖고 있기 때문에 전이진트리가 성립하지 않는다. 오른쪽 이미지의 경우, 각 노드가 0개 또는 2개의 자식을 갖고있으므로 전이진트리가 성립한다. 완전이진트리(Complete Binary Tree) 마지막 레벨을 제외하고 모든..