[Algorithm]트리와 이진트리의 기본 개념

트리(Tree): 계층형 자료구조

 - 하나의 node = 그 자체로 트리 = root

 - 트리의 기본 성질: 노드가 N개인 트리는 항상 N - 1개의 링크를 가짐           

* node: 데이터 필드 + 링크 필드

* 노드의 차수(degree): 한 노드가 가진 서브 트리의 수(=각 노드의 가지 수)

* 노드의 부모 및 자식

* 트리의 차수: 노드들 차수 중 최대 차수

* 노드의 레벨: root = level 0, 트리의 특정 깊이

* 노드의 높이 또는 깊이: 루트 도달하기 위해 거쳐하는 간선 수 ex. I의 깊이= 2, L의 깊이=3

 

 

이진 트리(Binary Tree): node의 유한 집합

 - 각 노드는 최대 2개의 자식을 가짐( 왼, 오 중 하나가 공백도 허용)

 - 리프 노드(leaf node): 둘다 공백일 때도 허용

 - 이진 트리의 종류

   a. 편향 이진 트리

 

 

 

 

 

b. 포화 이진 트리

 - 높이가 h,  노드 수 (2^h+1) - 1 인 이진 트리( 노드가 모두 채워져 있음을 의미)

 

 

 

c. 완전 이진 트리

 - 마지막 레벨 제외하고 노드가 모두 채워져 있는 트리

 - 노드 수와 번호 부여 수가 같다

 

 

-  이진 트리의 성질

 ▷ 높이가 h(h>0)인 이진 트리의 최대 노드 수: (2 ^ h+1) - 1

 ▷ 레벨 i(i>0) 최대 노드 수:  2 ^ i

- 이진 트리의 표현 

a. 순차 표현 방식: 일차원 배열로 표현

 -> index[0]: 실제로 사용 x

 -> index[1]: 항상 루트 노드

  단, 편향 이진 트리의 경우 공간 낭비가 심하다. 

                                        ※ 이진 트리를 표현한 1차원 배열과 인덱스 관계 표  

   * 배열을 이용해 이진 트리 구현*

public int leftSubTree(int bt) {
		left = bt*2;
		return left;
	}
	public int rightSubTree(int bt) {
		right = bt*2+1;
		return right;
	}

 

b. 연결 리스트 표현 방식

   -> left, right: 각각 왼쪽 오른쪽 서브 트리를 가르키는 링크( 순차의 비효율에 최적화)

  -> 연결리스트를 이용한 이진 트리 메소드

  * 구현 *

	public BinaryTree leftSubTree(BinaryTree btree) {
		if (isEmpty(btree)==true)  // 이진트리가 비어있는지
			return null;
		else
			return btree.ltree;
		// 왼쪽 서브 반환
	} // End of leftSubTree

	public BinaryTree rightSubTree(BinaryTree btree) {
		if (isEmpty(btree)==true)
			return null;
		else
			return btree.rtree;
		// 오른쪽 서브 반환
	} // End of rightSubTree

	public Object rootData(BinaryTree btree) {
		if (isEmpty(btree)==true)
			return null;
		else
			return btree;
		// 루트 데이타 반환
	} // End of rootData

---

    ☞ 실습 Project

Java를 이용해 연결리스트를 이용한 이진트리를 이렇게 구현 가능하다.

연결리스트를 이용해 이진 트리 구현

 

// "A(B, C)" 만들기 
ltree = new BinaryTree(new BinaryTree(), "B", new BinaryTree());
rtree = new BinaryTree(new BinaryTree(), "C", new BinaryTree());
btree = new BinaryTree(ltree, "A", rtree); 
// "G(null, H)" 만들기 
rtree = new BinaryTree(new BinaryTree(), "H", new BinaryTree());
btree = new BinaryTree(new BinaryTree(), "G", rtree);
      //  빈칸을 채워서 이진 트리를 완성하라. (ppt에 주이진 이진트리)     
// "E(G(null, H), null)" 만들기 
ltree = btree;
btree = new BinaryTree(new BinaryTree(),"E",ltree);
// "B(D, E(G(null, H), null))" 만들기  
ltree = new BinaryTree(new BinaryTree(),"D",new BinaryTree());
rtree = btree;
btree = new BinaryTree(ltree,"B",rtree);
// "C(F, null)" 만들기
ltree = new BinaryTree(new BinaryTree(),"F",new BinaryTree());
current = new BinaryTree(ltree,"C",new BinaryTree());