[자료구조] Tree

Binary Tree(이진 트리)

노드가 하나 이상의 자식을 가지면 트리라고 부른다. 그중에 child Node가 최대 2개까지만 붙는 Tree를 binary tree라고 부른다. (3개 붙는 트리는 ternary tree)

Binary Search Tree

• 왼쪽 Node와 그 이하 child Node들은 현재 노드 보다 작아야 하고
• 오른쪽 Node와 그 이하 child Node들은 현재 노드보다 커야 된다.

Complete Binary Tree(완전 이진 트리)

마지막 level을 제외한 모든 서브 트리의 레벨이 같아야하고 마지막 레벨은 왼쪽부터 채워져 있으면 완전 이진 트리이다.

Full Binary Tree

노드들의 child가 하나도 없거나 2개인 경우로만 구성된 트리

Perfect Binary Tree

빈공간 없이 모든 노드가 2개의 자식을 가지고 레벨도 정확하게 딱 떨어지는 완벽한 피라미드 구조 형성

Binary Tree의 3가지 순회방법

• Inorder

1. Left
2. Root
3. Right

• Preorder

1. Root
2. Left
3. Right

• Postorder

1. Left
2. Right
3. Root

# Tree 구현 코드
/*
       (1)
      ↙ ↘
    (2)  (3)
   ↙ ↘
 (4)  (5)
 Inorder (Left, Root, Right): 4 2 5 1 3
 Preorder (Root, Left, Right): 1 2 4 5 3
 Postorder (Left, Right, Root): 4 5 2 3 1
*/
class Node{
	int data;
    Node left;
    Node right;
}

class Tree{
	public Node root;
	
    public void setRoot(Node node){
    	this.root = node;
    }
    public Node getRoot(){
    	return root;
    }
    public Node makeNode(Node left, int data, Node right){
    	Node node = new Node();
        node.data = data;
        node.left = left;
        node.right = right;
        return node;
    }
    public void inorder(Node node){
    	if(node != null){
        	inorder(node.left);
            System.out.println(node.data);
            inorder(node.right);
        }
    }
    
    public void preorder(Node node){
    	if(node != null){
        	System.out.println(node.data);
        	preorder(node.left);
            preorder(node.right);
        }
    }
    
    public void postorder(Node node){
    	if(node != null){
        	postorder(node.left);
            postorder(node.right);
            System.out.println(node.data);
        }
    }
}

# 테스트 클래스
public class TreeTest{
	public static void main(String[] args){
    	Tree t = new Tree();
        Node n4 = t.makeNode(null, 4, null);
        Node n5 = t.makeNode(null, 5, null);
        Node n2 = t.makeNode(n4, 2, n5);
        Node n3 = t.makeNode(null, 3, null);
        Node n1 = t.makeNode(n2, 1, n3);
        t.setRoot(1);
        t.inorder(t.getRoot());
        t.preorder(t.getRoot());
        t.postorder(t.getRoot());
    }
}

# 결과 값
4
2
5
1
3

1
2
4
5
3

4
5
2
3
1

Binary Heaps

최대값이나 최소값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진 트리를 기본으로 한 자료구조

• Min Heap: 작은 값을 항상 위에 있게 해서 트리의 루트에는 가장 작은 값이 오도록하는 힙
• Max Heap: 가장 큰 값이 맨 위에 오도록 모든 노드들은 자기 부모 노드의 자기보다 큰 값을 가지는 트리구조

Trie

문자열에서 검색을 빠르게 해주는 트리 구조

배열을 이진검색트리로 만들기

# 배열을 이진검색트리로 만드는 구현 코드
class Tree{
	class Node{
    	int data;
        Node left;
        Node right;
        
        Node(int data){
			this.data = data;
        }
        
        Node root;
        public void makeTree(int[] a){
        	root = makeTreeR(a, 0, a.length - 1);
        }
        
        public Node makeTreeR(int[] a, int start, int end){
        	if(start > end) return null;
            int mid = (start + end) / 2;
            Node node = new Node(a[mid]);
            node.left = makeTreeR(a, start, mid - 1);
            node.right = makeTreeR(a, mid + 1, end);
            return node;
        }
        
        public void searchBTree(Node n, int find){
        	if(find < n.data){
            	System.out.println("Data is smaller than " + n.data);
                searchBTree(n.left, find);
            }
            else if(find > n.data){
            	System.out.println("Data is bigger than" + n.data);
                searchBTree(n.right);
            }
            else{
            	System.out.println("Data found!");
            }
        }
    }
}

# 테스트 클래스
public class ArrBinaryTreeTest{
	public static void main(String[] args){
    	int[] a = new int[10];
        for(int i = 0;i < a.length;i++){
        	a[i] = i;
        }
        
        Tree t = new Tree();
        t.makeTree(a);
        t.searchBTree(t.root, 2);
    }
}

# 결과 값
Data is smaller than 4
Data is bigger than 1
Data found!