이진트리
-
자료구조 - 이진트리CS/자료구조 2021. 2. 18. 23:03
이진트리 트리 노드가 N개인 트리는 N - 1개의 링크를 가진다. 트리의 루트에서 어떤 노드로 가는 경로는 유일하다. 또한 임의 두 노드간의 경로도 유일하다. 이진트리 각 노드는 최대 2개의 자식노드를 가진다. 종류 perfect binary tree 이진 트리의 모든 노드가 꽉 차있는 트리이다. 높이가 h인 perfect binary tree는 2^h - 1개의 노드를 가진다. full binary tree 이진 트리의 모든 노드가 0개 또는 2개의 자식을 갖는 트리이다. complete binary tree 이진 트리에서 노드가 왼쪽에서 오른쪽 순서로 순차적으로 존재하는 트리이다. 각 노드는 하나의 데이터 필드와 왼쪽 자식, 오른쪽 자식의 주소를 저장한다. 노드가 N개인 full, complete b..