이진트리순회(DFS)

이진트리를 깊이우선탐색으로 돌때 

전위, 중위, 후위 순회 3가지가 있다

 

1 2 3 4 5 6 7 으로 된 7개 노드가 있을떄 

전위순회 부 - 왼 - 오 1 2 4 5 3 6 7

중위순회 왼 - 부 - 오 4 2 5 1 6 3 7

후위순회 왼 - 오 - 부 4 5 2 6 7 3 1

 

이 순서로 돈다

 

코드로 구현할 때는 Node 클래스와 Node 클래스를 재귀적으로 순회할 함수 2개를 만든다

 

class Node{
    int data;
    Node lt, rt;
    
    //노드 생성자
    public Node(int val) {
        data=val;
        //처음 생성시 좌우 노드는 null
        lt=rt=null;
    }
}

 

데이터와 양쪽에 노드를 가지는 노드 클래스를 만들고 처음에 좌우 노드는 null로 만든다

 

public void DFS(Node root){
        //루트가 없으면 리턴
        if(root==null)
            return;
        else{
            //노드 순회, 출력을 어디에 하는지에 따라 전위, 후위, 중위가 달라짐
            DFS(root.lt);
            System.out.print(root.data+" ");
            DFS(root.rt);
        }
    }

노드를 순회하는 함수에서는 루트가 null이면 리턴, 아니면 쭉 순회하게 하는 함수를 만든다

 

 

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);
tree.DFS(tree.root);

노드를 삽입하고 dfs 함수로 순회한다