[Ch.07 - DFS] 01. 이진트리 순회 (+ 깊이우선탐색 DFS)

1. 이진트리 순회 (깊이우선탐색)

/_ 전위 순회 : 1234567

∧ 중위 순회 : 4251637

_\ 후위 순회 : 4526731

 

Depth First Search (DFS : 깊이우선탐색)

-> 가장 낮은 깊이 부터 우선 탐색한다.

 

 

 

구현

1. 노드 클래스 -> 생성자 정의
2. 트리 만들기 -> root -> 데이터 삽입
3. 트리 객체를 인스턴스변수로 만들어서 메서드 생성 후, 호출하는 방식

 

package dfsbfs.ch07;
//DFS -> 백트래킹

//Depth frist search; 깊이 우선 탐색
//이진트리 -> 부모노드, 왼쪽자식노드, 오른쪽자식노드

//루트 노드 -> 왼쪽 노드 -> 왼쪽 노드 [마지막 노드면] -> 오른쪽 노드 [마지막 노드면] -> 오른쪽 노드 
//왼쪽 노드 -> 왼쪽 노드 -> 왼쪽 노드 [마지막 노드면] -> 오른쪽 노드 [마지막 노드면]
//전위 순회 : 1 2 4 5 3 6 7 [부모 -> 왼쪽 자식 -> 오른쪽 자식]
//중위 순회 : 4 2 5 1 6 3 7 [왼쪽 자식 -> 부모 -> 오른쪽 자식]
//후위 순회 : 4 5 2 6 7 3 1 [왼쪽 자식 -> 오른쪽 자식 -> 부모]
//즉 순회의 기준은 부모이고, 탐색은 가장 깊은 곳부터 우선 방문. 부트리에서 마무리 순회 후 다음 트리로 넘어간다.
//후위 순회 : 일반적인 순회로, 병합 정렬에서 사용한다.

//노드 클래스
class Node {
	int data;
	Node lt, rt;
	//왼쪽 자식, 오른쪽 자식 노드 생성 [인스턴스 변수 : 노드 클래스의 객체 주소 저장]
	
	public Node(int val) {
		//생성자
		data = val;
		// 데이터에 값 저장
		lt = rt = null;
		// 두 포인터에 널값 저장
	}
}

public class Dfsbfs01 {
	Node root; //참조형 변수
	public void DFS(Node root) {
		//트리 객체의 인스턴스 메서드 -> 1번 노드
		if(root==null)
			return;
		//가리키는 주소가 없으므로, 말단 노드이다.
		else {
			// 두 가닥으로 뻗는다. [함수 호출 2번]
			
			//전위 순회 : System.out.print(root.data+" ");

			DFS(root.lt);
			//왼쪽 자식 호출
			//중위 순회 : System.out.print(root.data+" ");
			
			DFS(root.rt);
			//오른쪽 자식 호출
			//후위 순회 : 
			//System.out.print(root.data+" ");
			
			
			//[D(100)] : 100번지를 가리키다가 lt를 호출하면, [D(200)] : 200번 주소를 가리킨다. [D(300)] : rt를 호출하면 300번 주소를 가리킨다.
			//[D(400)] : 왼쪽 자식 노드의 왼쪽 자식 노드
			//[D(500)] : 왼쪽 자식 노드의 오른쪽 자식 노드
		}
		
	}
	public static void main(String[] args) {
		Dfsbfs01 tree = new Dfsbfs01();
		
		tree.root=new Node(1);
		//메인 클래스 생성한 객체를 루트 변수가 가리킴
		//메인 클래스의 참조형을 이용해 노드 루트 노드 객체 생성
		tree.root.lt=new Node(2);
		tree.root.rt=new Node(3);
		tree.root.lt.lt=new Node(4);
		tree.root.lt.rt=new Node(5);
		tree.root.rt.lt=new Node(6);
		tree.root.rt.rt=new Node(7);
		//말단 노드는 lt,rt 값이 모두 null을 갖는다.
		tree.DFS(tree.root);
	}
	//중위순회 -> 백트래킹 문제
	//스택으로 그리기 : D(100) -> D(200) -> D(400) -> D(null) -> D(null) pop -> root.data 출력 = 4 -> D(root.rt) -> D(null) -> D(null) pop 
	//root : 100 ->200 -> 400 -> root==null인 말단노드이므로 return -> root==null인 말단노드이므로 return  
	//스택으로 그리기 : D(400) pop -> D(200)에서 root.data 출력=2 -> D(200) root.rt -> D(500) root.lt -> D(null) -> D(null) pop -> D(500) root.data 출력=5 
	//-> D(500) root.rt -> D(null) -> D(null) pop -> D(500) pop
	//D(200) -> D(200) pop -> D(100) root .data 출력=1 -> D(100) root.rt
	
}

 

---

1. D(100)
2. D(200)
3. D(400)
4. D(null)
5. print(root.data) =4
6. D(400)
7. D(null)
8. pop
9. D(200)
10. print(root.data) =2
11. D(500)
12. D(null)
13. D(500)
14. print(root.data) =5
15. D(null)
16. pop
17. D(200)
18. pop
19. print(root.data)=1
20. D(300)

중위순회 순서-> 4251637