이진 트리 순회(DFS)
설명
이진 트리의 전위, 중위, 후위 순회를 직접 구현하세요.
코드
public class DFS {
Node root;
public static void main(String[] args) {
DFS tree = new DFS();
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);
DFS(tree.root);
System.out.println();
DFS2(tree.root);
System.out.println();
DFS3(tree.root);
System.out.println();
}
//전위 순회
public static void DFS(Node root){
if(root==null) return ;
System.out.print(root.data+" ");
DFS(root.lt);
DFS(root.rt);
}
//중위 순회
public static void DFS2(Node root){
if(root==null) return ;
DFS(root.lt);
System.out.print(root.data+" ");
DFS(root.rt);
}
//후위 순회
public static void DFS3(Node root){
if(root==null) return ;
DFS(root.lt);
DFS(root.rt);
System.out.print(root.data+" ");
}
}
class Node{
int data;
Node lt,rt;
public Node(int val) {
data = val;
lt=rt = null;
}
}
public class DFS {
Node root;
public static void main(String[] args) {
DFS tree = new DFS();
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);
DFS(tree.root);
System.out.println();
DFS2(tree.root);
System.out.println();
DFS3(tree.root);
System.out.println();
}
//전위 순회
public static void DFS(Node root){
if(root==null) return ;
System.out.print(root.data+" ");
DFS(root.lt);
DFS(root.rt);
}
//중위 순회
public static void DFS2(Node root){
if(root==null) return ;
DFS(root.lt);
System.out.print(root.data+" ");
DFS(root.rt);
}
//후위 순회
public static void DFS3(Node root){
if(root==null) return ;
DFS(root.lt);
DFS(root.rt);
System.out.print(root.data+" ");
}
}
class Node{
int data;
Node lt,rt;
public Node(int val) {
data = val;
lt=rt = null;
}
}
전위
1 2 4 5 3 6 7
중위
4 2 5 1 6 3 7
후위
4 5 2 6 7 3 1
main 에서 만든 Node의 구조
Java의 class의 구조와 전위 중위 후위의 코드에서 Stack Frame의 개념을 알고 있다면 위 실행 결과를 이해하는데 도움이 될것이다.
Author And Source
이 문제에 관하여(이진 트리 순회(DFS)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ililil9482/이진-트리-순회DFS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)