[자료구조] Tree -2

본문과 관련하여 실습한 전체코드는 리파지토리에 별도 작성하였습니다.: https://github.com/ejImDev/data_structure_study.git

다른 형태의 이진트리

포화 이진트리(Full Binary Tree) : 각 내부노드가 2개의 자식노드를 가지는 트리
완전 이진트리(Complete Binary Tree) : 마지막 레벨을 제외한 각 레벨이 노드들로 꽉 차있고, 마지막 레벨에는 노드들이 왼쪽부터 빠짐없이 채워진 트리
포화트리는 완전 이진트리이다.

이진트리의 속성

레벨 k에 있는 최대 노드 수 = 2의 k-1승
높이가 h인 포화이진트리에 있는 노드 수 = 2의 h승 - 1
N개의 노드를 가진 완전 이진트리의 높이 = log2(N+1)

배열에 저장된 이진트리
- a[i]의 부모노드는 a[i/2]에 있다. 단 i>1
- a[i]의 왼쪽 자식노드는 a[2i], 오른쪽 자식노드는 a[2i+1]에 있다. 단 2i<=N
- 편향이진트리를 배열에 저장하는 경우, 트리의 높이가 커질수록 메모리 낭비가 심화됨
- 일반적인 경우의 이진트리의 노드는 키와 2개의 레퍼런스필드, 즉 left와 right를 가진다

이진트리를 위한 Node 클래스

TreeNode 클래스

public class TreeNode<Key extends Comparable<Key>> {
 private Key item;
 private Node<Key> left;
 private Node<Key> right;
 public Node(Key newItem, Node lt, Node rt){
   item = newItem;
   left = lt;
   right = rt;
 }
 public Key getKey() { return item; }
 public Node<Key> getLeft() { return left; }
 public Node<Key> getRight() { return right; }
 public void setKey(Key newItem) { item = newItem; }
 public void setLeft(Node<Key> lt) { left = lt; }
 public void setRight(Node<Key> rt) { right = rt; }
}

이진트리 클래스

public class BinaryTree <Key extends Comparable<Key>> {
 private Node root;
 public BinaryTree() { root = null; }
 public Node getRoot() { return root; }
 public void setRoot(Node newRoot) { root = newRoot; }
 public boolean isEmpty() { return root == null; }
 ...
}

참고 자료 : ‘경기대학교 소프트웨어중심대학사업단 - JAVA 자료구조’ https://youtu.be/ukq0-uYdTQ8

IM

다른 형태의 이진트리

이진트리의 속성