1. 트리의 구현과 순회

트리의 정의

=> 저번주의 선형자료구조와 다르게 비선형 자료구조이다.

• 차이점: 선형자료구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형 구조는 표현에 초점이 맞춰져있음

• 트리: 사이클이 없이 모든 정점이 연결되어있는 그래프 (사이클: 시작노드에서 다시 시작노드로 돌아올수있는것)
  EX) 컴퓨터의 디렉토리

• 그래프: 여러 대상들과 대상들 간의 1:1 관계를 도형으로 나타낸것
  (정점(Vertex)+간선(Edge)(방향/무뱡향 + 가중치가 있다))
  트리 중 자식을 최대 2개만 가지고 있는 트리가 이진트리

트리의 순회

: 트리에 있는 모든 노드들을 탐색하는 것
1. 전위 순회 (preorder)
= 깊이 우선 순회(DFT)라고도 함
ROOT방문->왼쪽 서브트리 전위 순회-> 오른쪽 서브트리 전위 순회

 void preorder(Node node) {
 	if(node!=null) {
 		System.out.print(node.data);
 		preorder(node.leftnode);
 		preorder(node.rightnode);
 	}
 }

2. 중위 순회 (inorder)
   =대칭 순회라고도 함 왼쪽 서브 트리를 중위 순회함-> ROOT방문-> 오른쪽 서브트리를 중위순회

     void inorder(Node node) {
     	if(node!=null) {
     		inorder(node.leftnode);
     		System.out.print(node.data);
     		inorder(node.rightnode);
     	}
     }

3. 후위 순회 (postorder)
   삭제할때 주로 사용됨

    void postorder(Node node) {
   	if(node!=null) {
   		postorder(node.leftnode);
   		postorder(node.rightnode);
   		System.out.print(node.data);
   	}

   왼쪽 서브트리를 후위순회-> 오른쪽 서브트리르 후위 순회 -> ROOT방문

import java.io.*;
import java.util.*;
class Node{
	int data;
	Node rightnode;
	Node leftnode;
}
class Traversal{
	Node root;
	Node getroot() {
		return root;
	}
	void setroot(Node root) {
		this.root=root;
	}
	Node makeNode(int data,Node left, Node right) {
		Node node=new Node();
		node.data=data;
		node.leftnode=left;
		node.rightnode=right;
		return node;
	}
}

public class Main {
	static ArrayList<ArrayList<Integer>> list= new ArrayList<>();
    public static void main(String[] args)  {
    	Traversal t=new Traversal();
    	Node n4=t.makeNode(4, null, null);
    	Node n5=t.makeNode(5, null, null);
    	Node n2=t.makeNode(2,n4,n5);
    	Node n3=t.makeNode(3,null,null);
    	Node n1=t.makeNode(1, n2, n3);
    	//root 지정
    	t.setroot(n1);
    	preorder(t.getroot());
    	System.out.println();

    	inorder(t.getroot());
    	System.out.println();

    	postorder(t.getroot());

    
    }
    static void preorder(Node node) {
    	if(node!=null) {
    		System.out.print(node.data);
    		preorder(node.leftnode);
    		preorder(node.rightnode);
    	}
    }
    static void inorder(Node node) {
    	if(node!=null) {
    		inorder(node.leftnode);
    		System.out.print(node.data);
    		inorder(node.rightnode);
    	}

    }
    static void postorder(Node node) {
    	if(node!=null) {
    		postorder(node.leftnode);
    		postorder(node.rightnode);
    		System.out.print(node.data);
    	}

    }
    
    
    
  }

2. 이진 탐색 트리

이진 탐색 트리란

이진트리이면서
1. 중복된 노드가 없어야한다.
2. 루트노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있다.
3. 루트노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있다.
4. 좌우 서브 트리도 모두 이진 탐색 트리여야 한다.
의 조건을 만족하는 트리

• 이진탐색+연결리스트 => 이진탐색의 효율적인 탐색 능력을 유지하면서도 링크드리스트의 장점인 빈번한 자료 입력과 삭제를 가능하게함.

• 순회시 중위 순회 방식을 쓰면 -> 정렬된 순서대로 읽을 수 있다

• 트리의 높이가 h면 O(h)