tree, binary tree, compare, dfs/bfs

그래프와 트리 구분 기준

• 그래프는 순환되는데 트리는 순환되지않음
• 그래프에 트리가 포함됨
• 트리 360p, 깊이우선탐색 순회 364
  

---

compareTo

TreeSetTest

//중복이 불가능
public class TreeSetTest {
	public static void main(String[] args) {
		//TreeSet<Integer> treeset1 = new TreeSet<>();//오름차순
		TreeSet<Integer> treeset1 = new TreeSet<>(Collections.reverseOrder());//내림차순
		treeset1.add(20);
		treeset1.add(10);
		treeset1.add(30);
		treeset1.add(28);
		treeset1.add(55);
		
		for(int data:treeset1) {
			System.out.println(data);
		}
		
		//TreeSet<Integer> treeset2 = new TreeSet<>();//오름차순
		TreeSet<String> treeset2 = new TreeSet<>(Collections.reverseOrder());//내림차순
		//TreeSet은 객체가 저장되면서 내부적으로 Comparable의 하위객체를 찾아서 compareTo를 자동으로 호출한다.
		treeset2.add("지민");
		treeset2.add("뷔");
		treeset2.add("RM");
		treeset2.add("슈가");
		treeset2.add("진");
		
		for(String data:treeset2) {
			System.out.println(data);
		}
		
		TreeSet<Student> treeset3 = new TreeSet<>();
		treeset3.add(new Student("방탄"));
		treeset3.add(new Student("이민호"));
	}
}

Student

//자동으로 정렬이 진행되도록 처리하려면
//Comparable -> 자기자신의 객체와 다른객체를 비교
public class Student implements Comparable<Student>{
	String id;
	String name;
	int avg;//평균점수
	public Student(String id) {
		super();
		this.id = id;
	}
	
	public Student(String id, String name, int avg) {
		super();
		this.id = id;
		this.name = name;
		this.avg = avg;
	}

	public String getId() {
		return id;
	}
	public void setId(String id) {
		this.id = id;
	}
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	public int getAvg() {
		return avg;
	}
	public void setAvg(int avg) {
		this.avg = avg;
	}

	@Override
	public String toString() {
		return "Student [id=" + id + ", name=" + name + ", avg=" + avg + "]";
	}

	@Override
	public int compareTo(Student o) {
		System.out.println("compareTo : "+this.getId()+","+o.getId());
		return o.getAvg()-this.getAvg();
	}
	
}

StudentTreeSet

public class StudentTreeSet {
		private TreeSet<Student> treeset;
		public StudentTreeSet() {
			treeset = new TreeSet<>();
		}
		public void addStudent(Student student) {
			treeset.add(student);
		}
		public void printAll() {
			for(Student student:treeset) {
				System.out.println(student);
			}
			System.out.println();
		}
}

StudentTest

public class StudentTest {
	public static void main(String[] args) {
		StudentTreeSet studentSet = new StudentTreeSet();
		
		studentSet.addStudent(new Student("2101","남준",95));
		studentSet.addStudent(new Student("2102","지민",88));
		studentSet.addStudent(new Student("2103","슈가",100));
		studentSet.addStudent(new Student("2104","뷔",77));
		
		studentSet.printAll();
	}
}

---

깊이우선탐색(DFS : Depth-First Search)(스택활용)

MyTreeNode

이진트리를 이용한 dfs(깊이우선탐색)

public class MyTreeNode {
	int data;
	MyTreeNode leftChild;
	MyTreeNode rightChild;
	
	public MyTreeNode(int data) {
		super();
		this.data = data;
		this.leftChild = null;
		this.rightChild = null;
	}

	public int getData() {
		return data;
	}

	public void setData(int data) {
		this.data = data;
	}

	public MyTreeNode getLeftChild() {
		return leftChild;
	}

	public void setLeftChild(MyTreeNode leftChild) {
		this.leftChild = leftChild;
	}

	public MyTreeNode getRightChild() {
		return rightChild;
	}

	public void setRightChild(MyTreeNode rightChild) {
		this.rightChild = rightChild;
	}
	
}

MyBinaryTree

깊이우선탐색을 위한 메소드

public class MyBinaryTree {
	MyTreeNode root;
	public void dfs(MyTreeNode root) {
		if(root==null) {
			return;//널이라는 의미는 터미널노드라는 의미이므로 재귀를 빠져나온다.
		}else {
			//왼쪽노드와 오른쪽노드를 계속 탐색하면서 내려가야 한다. 재귀를 써야한다.
			//System.out.print(root.data+" "); //전위순회
			dfs(root.leftChild);
			//System.out.print(root.data+" ");//중위순회
			dfs(root.rightChild);
			System.out.print(root.data+" ");//후위순회
		}
	}
}

MyBinaryTreeTest

public class MyBinaryTreeTest {
	public static void main(String[] args) {
		MyBinaryTree tree = new MyBinaryTree();
		tree.root = new MyTreeNode(1);
		tree.root.leftChild = new MyTreeNode(2);
		tree.root.rightChild = new MyTreeNode(3);
		
		tree.root.leftChild.leftChild = new MyTreeNode(4);
		tree.root.leftChild.rightChild = new MyTreeNode(5);
		
		tree.root.rightChild.leftChild = new MyTreeNode(6);
		tree.root.rightChild.rightChild = new MyTreeNode(7);
		
		tree.dfs(tree.root);//1번노드객체
	}
}

너비우선탐색(BFS : Breadth-First Search)(Queue 활용)

BFSTreeNode

이진트리를 이용한 dfs

public class BFSTreeNode {
	int data;
	BFSTreeNode leftChild;
	BFSTreeNode rightChild;
	
	public BFSTreeNode(int data) {
		super();
		this.data = data;
		this.leftChild = null;
		this.rightChild = null;
	}

	public int getData() {
		return data;
	}

	public void setData(int data) {
		this.data = data;
	}

	public BFSTreeNode getLeftChild() {
		return leftChild;
	}

	public void setLeftChild(BFSTreeNode leftChild) {
		this.leftChild = leftChild;
	}

	public BFSTreeNode getRightChild() {
		return rightChild;
	}

	public void setRightChild(BFSTreeNode rightChild) {
		this.rightChild = rightChild;
	}
	
}

MyBinaryTreeBFS

Queue를 이용해서 작업

public class MyBinaryTreeBFS {
	BFSTreeNode root;
	public void bfs(BFSTreeNode root) {
		//트리를 탐색하면서 노드들이 저장될 큐를 생성
		Queue<BFSTreeNode> myqueue = new LinkedList<>();
		myqueue.offer(root);
		int level = 0;//레벨
		//큐에 데이터가 없을때까지 반복작업 - 이진트리의 모든 노드의 검색이 완료될때까지
		while(!myqueue.isEmpty()) {
			int size = myqueue.size();
			System.out.print(level+":");
			for(int i=0;i<size;i++) {
				BFSTreeNode currentNode = myqueue.poll();
				System.out.print(currentNode.data+" ");
				if(currentNode.leftChild!=null) {
					myqueue.offer(currentNode.leftChild);
				}
				if(currentNode.rightChild!=null) {
					myqueue.offer(currentNode.rightChild);
				}
			}
			level++;
			System.out.println();
		}
	}
}

MyBinaryTreeTest

public class MyBinaryTreeTest {
	public static void main(String[] args) {
		MyBinaryTreeBFS tree = new MyBinaryTreeBFS();
		tree.root = new BFSTreeNode(1);
		tree.root.leftChild = new BFSTreeNode(2);
		tree.root.rightChild = new BFSTreeNode(3);
		
		tree.root.leftChild.leftChild = new BFSTreeNode(4);
		tree.root.leftChild.rightChild = new BFSTreeNode(5);
		
		tree.root.rightChild.leftChild = new BFSTreeNode(6);
		tree.root.rightChild.rightChild = new BFSTreeNode(7);
		
		tree.bfs(tree.root);//1번노드객체
	}
}

과제

https://www.acmicpc.net/problem/2178

본 포스팅은 멀티캠퍼스의 멀티잇 백엔드 개발(Java)의 교육을 수강하고 작성되었습니다.