섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 5. 이진트리순회(DFS : Depth-First Search)

문제

• 아래 그림과 같은 이진트리를 전위순회와 후위순회를 연습해보세요.

• 전위순회 출력 : 1 2 4 5 3 6 7
• 중위순회 출력 : 4 2 5 1 6 3 7
• 후위순회 출력 : 4 5 2 6 7 3 1

---

풀이방식

이번 문제는 이진트라와 재귀함수를(을) 사용하여 푸는 문제이다.

---

더 자세한 설명은 아래 글을 참조해서 확인해보기 바랍니다.

섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 6. 부분집합 구하기(DFS)

---

설계과정

1. 노드에 값이 없으면 말단 노드임을 의미하므로 바로 리턴한다.

2. 왼쪽과 오른쪽을 나누어서 각각의 노드를 생성한다.

---

아래 이미지를 통해 자세히 알아보자.

• 코드중에 tree.root.lt = new Node(2)  가 수행되면 주소값이 200인 lt를 생성하고, 그 주소인 200을 root 의 lt에 준다.
• 말단 노드는 자식이 없으므로 lt, rt 주소가 null 이다.

---

3. 전위, 중위, 후위에 맞게 출력한다.

---

 

풀이과정

1. Node 클래스를 통해 data, lt, rt 를 선언하고 값을 초기화한다.

• data : 각 트리의 값이 들어갈 변수이다.
• lt : 왼쪽 자식의 노드이다.
• rt : 오른쪽 자식의 노드이다.
• lt 와 rt 는 인스턴스 변수로, 노드 클래스의 객체 주소를 저장하는 변수이다.
• val : data 값이 넘어온다.

2.  DFS() 메소드를 작성하자.

 

3. 먼저 root 값이 null이면 그대로 리턴한다.

• 말단 노드이면 자식이 없고, 끝을 의미하므로 바로 리턴한다.

4. null이 아니라면 DFS()를 통해 lt와 rt 노드를 생성한다.

 

5. 전위, 중위, 후위순회에 맞는 위치에서 값을 출력한다.

• 이 때, 출력문은 총 3개지만 2개는 주석처리해야 정상적은 값이 출력된다.

 

---

해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.