1. Intro

계층형 자료구조인 트리 중 이진트리에 대해 알아보고자 한다.

---

2. Contents

2.1.이진트리(Binary Tree)

이진트리란 모든 노드가 정확하게 두개의 서브트리를 가지고 있는 트리이다.
이진트리는 다음과 같은 조건을 만족한다.

• 서브트리는 공백이 될 수 있음
• 왼쪽 서브 트리와 오른쪽 서브 트리를 분명히 구별

2.2.레벨 그리고 높이(깊이)(Level and height(or depth))

레벨은 노드가 속한 층을 의미하며 높이는 트리의 최대 레벨이다.

루트노드는 레벨 0이며, 부모노드의 레벨이 l 이면 자식은 l+1 이다.

level(v)
	if(v=root) then return 0;
    else return (1 + level(v'sparent));
end level()

2.3 이진트리의 종류

2.3.1 편향 이진트리

왼쪽 또는 오른쪽 노드만 존재하는 이진트리

2.3.2 포화 이진트리

이진트리의 최대 개수만큼 노드가 있는 트리
노드의 개수가 2**(h+1)-1 개 만큼 있음

2.3.3 완전 이진트리

포화 이진트리에서 오른쪽 아래의 노드부터 뺀 트리

2.4 이진트리의 표현

2.4.1 일차원 배열 표현

• 포화 이진트리의 번호를 배열의 인덱스로 사용
• 인덱스 0은 사용 X, 1은 항상 루트노드
• 단점 :
  1. 트리가 편향된 경우 배열 공간을 낭비할 수 있음
  2. 노드의 삭제, 삽입 시 다른 노드들의 이동 필요

2.4.2 연결 리스트 표현

각 노드를 3개의 필드(left, data, right)로 구성

• left, right : 왼쪽, 오른쪽 서브트리를 가리키는 링크
• 필요시 부모를 가리키는 parent 필드 추가
  

---

3. 순회 및 연산

먼저 노드를 만들어보자

노드의 데이터는 편의를 위해 String형으로 하였음

class BTNode {
	String data;
	BTNode Lchild;
	BTNode Rchild;

	public BTNode(){ }
	public BTNode(String dt) {
		data = dt;
	}
	public BTNode(BTNode lc, String dt, BTNode rc) {
		data = dt;
    	Lchild = lc;
    	Rchild = rc;
	}
}

이진트리를 구성해보자!

전위, 중위, 후위순회, 트리의 복사, 동등성 결정

class BinaryTree {
	BTNode root;
    
    public BinaryTree() {
		root = null;
    }
    
    // 왼쪽, 오른쪽 서브트리를 받아 새로운 트리 생성
    public BinaryTree(BinaryTree ltree, String data, BinaryTree rtree) { 
    	BTNode node = new BTNode(ltree.root, data, rtree.root); 
        root = node;
    }
    
    // 트리가 비었는지 확인
    public boolean isEmpty() {
    	if(root == null) return true;
        else return false;
    }
    
    // recursion을 통한 중위순회
    public void inorder(BTNode t) {
    	if(t != null) {
        	inorder(t.Lchild);
            System.out.println(t.data);
            inorder(t.Rchild);
        }
    }
    
    // recursion을 통한 전위순회
    public void preorder(BTNode t) {
    	if(t != null) {
            System.out.println(t.data);
        	inorder(t.Lchild);
            inorder(t.Rchild);
        }
    }
    
    // recursion을 통한 후위순회
    public void preorder(BTNode t) {
    	if(t != null) {
        	inorder(t.Lchild);
            inorder(t.Rchild);
            System.out.println(t.data);
        }
    }
    
    // recursion을 통한 트리의 복사
    public BinaryTree copy() {
    	BinaryTree newTree = new BinaryTree();
        newTree.root = theCopy(root);
        return newTree;
    }
    
    private BTNode theCopy(BTNode t) {
    	BTNode newNode = null;
        if(t != null) {
        	BTNode l = theCopy(t.Lchild);
            BTNode r = theCopy(t.Rchild);
            newNode = new BTNode(l, t.data, r);
        }
        return newNode;
    }
    
    // recursion을 통한 트리의 동등성 결정
    public boolean equals(BinaryTree tr) {
    	return theEqual(this.root, tr.root);
    }
    
    private boolean theEqual(BTNode s, BTNode t) {
      if(s == null && t == null) { // 두 트리 모두 비었다면
          return true;
      } else if(s != null && t != null) { // 두 트리 모두 비지 않았다면
          if(s.data.equals(t.data)) { // 값이 같다면?
              if(theEqual(s.Lchild, t.Lchild)) { // 왼쪽 자식들 비교
                  return (theEqual(s.Rchild, t.Rchild)); // 오른쪽 자식들 비교
              }
              else return false;
          }
          else return false;
      }
      else return false;
}

4. review

블로그에 글을 작성하는 게 익숙하지 않아 그런지 글이 굉장히 지저분한 느낌이 든다. 구성은 어떻게 해야 하는지, 어떤식으로 글을 써야하는지 아직은 잘 모르겠지만 꾸준히 포스팅을 하다보면 익숙해지지 않을까 싶다.

다음 글은 Binary Search Tree에 대해 정리해보겠다.