트리란

트리는 일반적으로 대상 정보의 각 항목들을 계층적으로 연관되도록 구조화시키고자 할 때 사용하는 비선형 자료구조이다.
데이터 요소들의 단순한 나열이 아닌 부모-자식 관계의 계층적 구조로 표현이 된다.
트리는 그래프의 한 종류이며 사이클이 없다.

구성요소

1. 노드(node)
2. 가지(edge)

트리용어

1. 루트: 가장 윗부분에 위치하는 노드
2. 리프: 가장 마지막에 위치한 노드
3. 안쪽 노드: 루트를 포함하고 리프를 제외한 노드
4. 자식: 어떤 노드로 부터 연결된 아래쪽 노드
5. 부모: 어떤 노드로부터 가지로 연결된 위쪽 노드
6. 형제: 같은 부모를 가지는 노드
7. 조상: 어떤 노드에서 가지로 연결된 위쪽 노드 모두
8. 자손: 어떤 노드에서 가지로 연결된 아래쪽 노드 모두를 자손
9. 레벨: 루트로부터 얼마나 떨어져 있는지에 대한 값을 레벨이라고 함. 루트의 레벨은 0
   10 차수: 노드가 갖는 자식의 수

   모든 노드의 차수가 n이하인 트리를 n진 트리라 함

10. 높이: 루트로부터 가장 멀리 떨어진 리프까지의 거리
11. 서브트리 : 트리 안에서 다시 어떤 노드를 루트로 정하고 그 자손으로 이루어진 트리
12. 널 트리 : 노드, 가지가 없는 트리
13. 순서트리와 무순서트리 : 형제 노드의 순서를 따지면 순서트리, 따지지 않으면 무순서트리

순서트리 순회방법

너비우선탐색

너비 우선 탐색(breadth-first Search)은 낮은 레벨에서 시작해 왼쪽에서 오른쪽 방향으로 검색하고 한 레벨에서의 검색이 끝나면 다음 레벨로 내려감

깊이우선탐색

• 깊이 우선 탐색(depth-first Search)은 리프까지 내려가면서 검색하는 것을 우선순위로 하는 탐색 방법.
• 리프에 도달해 더 이상 검색을 진행할 곳이 없는 경우에는 부모에게 돌아감. 그런 다음 다시 자식 노드로 내려감.
• 하지만, 깊이우선탐색에서는 언제 노드를 방문할지에 따라 세 종류로 구분함

1. 전위 순회(Preorder)

노드 방문 -> 왼쪽 자식 -> 오른쪽 자식

2. 중위 순회

왼쪽 자식 -> 노드 방문 -> 오른쪽 자식

3. 후위 순회

왼쪽 자식 -> 오른쪽 자식 -> (돌아와) 노드방문

구현

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BinarySearchTree {
	private TreeNode root;
	
	private class TreeNode {
		private int data;
		private TreeNode left;
		private TreeNode right;
		
		public TreeNode(int data) {
			this.data = data;
		}
	}
	
	public void insert(int value) {
		root = insert(root, value);
	}
	
	
	public TreeNode insert(TreeNode root, int value) {
		if(root == null) {
			root = new TreeNode(value);
			return root;	
		}
		if(value < root.data) {
			root.left =insert(root.left, value);
		} else {
			root.right = insert(root.right, value);
		}
		
		return root;
	}
	
	public void inOrder() {
		inOrder(root);
	}
	
	public void inOrder(TreeNode root) {
		if(root == null) {
			return;
		}
		inOrder(root.left);
		System.out.println(root.data + " ");
		inOrder(root.right);
	}

	public TreeNode search(int key) {
		return search(root,key);
	}
	
	public TreeNode search(TreeNode root, int key) {
		if(root == null || root.data == key) { // base case
			return root;
		}
		
		if(key <root.data) {
			return search(root.left, key);
		} else {
			return search(root.right, key);
		}
	}
	
	
	public static void main(String[] args) {
		BinarySearchTree bst = new BinarySearchTree();
		bst.insert(5);
		bst.insert(3);
		bst.insert(7);
		bst.insert(1);
		
		bst.inOrder(bst.root);
		
		System.out.println();
		
		if(null != bst.search(3)) {
			System.out.println("Key found !!!");
		} else {
			System.out.println("Key not Found !!!");
		}
	}
}

이진트리와 완전이진트리

노드가 왼쪽 자식과 오른쪽 자식을 같는 트리를 이진트리라 함. 이진트리에서 루트로부터 마지막 레벨을 제외한 레벨의 노드가 꽉 채워져 있으면 완전이진트리(complete binary tree)라고 한다.

구현

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BinaryTree {
	private TreeNode root;
	
	private class TreeNode {
		private TreeNode left;
		private TreeNode right;
		private int data; // Generic type
		
		public TreeNode(int data) {
			this.data = data;
		}
	}
	
	// 이진 트리 생성
	public void createBinaryTree() {
		TreeNode first = new TreeNode(1);
		TreeNode second = new TreeNode(2);
		TreeNode third = new TreeNode(3);
		TreeNode forth = new TreeNode(4);
		TreeNode fifth = new TreeNode(5);
		
		root = first; // root ---> first
		first.left = second;
		first.right = third; // second <--- first ----> third
		
		second.left = forth; 
		second.right = fifth;
	}
	
	// 전위 순회 (재귀 방식)
	public void RecursivePreOrder(TreeNode root) {
		if(root == null) {
			return;
		}
		
		System.out.println(root.data + " ");
		RecursivePreOrder(root.left);
		RecursivePreOrder(root.right);
	}
	
	// 전위 순회 (반복문 방식) - stack활용
	public void IterativePreOrder() {
		if(root == null) {
			return;
		}
		Stack<TreeNode> stack = new Stack<>();
		stack.push(root);
		
		while(!stack.isEmpty()) {
			TreeNode temp = stack.pop();
			System.out.println(temp.data + "");
			
			if(temp.right != null) {
				stack.push(temp.right);
			}
			if(temp.left != null) {
				stack.push(temp.left);
			}
		}
		
	}

	// 중위 순회 (재귀 방식)
	public void RecursiveInOrder(TreeNode root) {
		if(root == null) {
			return;
		}
		RecursiveInOrder(root.left);
		System.out.println(root.data + " ");
		RecursiveInOrder(root.right);
	}
	
	// 중위 순회 (반복문 방식) - 스택 사용
	public void IterativeInOrder(TreeNode root) {
		if(root == null) {
			return;
		}
		Stack<TreeNode> stack = new Stack<>();
		TreeNode temp = root;
		
		while(!stack.isEmpty() || temp != null) {
			if(temp != null) {
				stack.push(temp);
				temp = temp.left;
			} else {
				temp = stack.pop();
				System.out.println(temp.data + " ");
				temp = temp.right;
			}
		}
	}
	
	// 후위 순회 (재귀방식)
	public void ReculsivePostOrder(TreeNode root) {
		if(root == null) {
			return;
		}
		ReculsivePostOrder(root.left);
		ReculsivePostOrder(root.right);
		System.out.println(root.data + " ");
	}
	

	public void levelOrder(TreeNode root) {
		if(root == null) {
			return;
		}
		Queue<TreeNode> queue = new LinkedList<>();
		queue.offer(root);
		
		while(!queue.isEmpty()) {
			TreeNode temp = queue.poll();
			System.out.println(temp.data + " ");
			if(temp.left != null) {
				queue.offer(temp.left);
			}
			if(temp.right != null) {
				queue.offer(temp.right);
			}
		}
	}
	
	public int findMax() {
		return findMax(root);
	}
	
	public int findMax(TreeNode root) {
		if(root == null) {
			return Integer.MIN_VALUE;
		} 
		
		int result = root.data;
		int left = findMax(root.left);
		int right = findMax(root.right);
		
		if(left > result) {
			result = left;
		}

		if(right > result) {
			result = right;
		}
		
		return result;
	}
	
	public static void main(String[] args) {
		BinaryTree bt = new BinaryTree();
		bt.createBinaryTree();
		System.out.println(bt.findMax(bt.root));
	}
}