Java Tree Traversal example

자바 트리탐색 (깊이우선탐색, 너비우선탐색) 예제

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

너비우선탐색 (Breadth First Search), BFS

package tree.traversal;

import java.util.*;
import java.util.List;

public class Main 
{
	public static void main(String[] args) 
	{
		Node root = new Node(1,1);
		Node node2 = new Node(2,2);
		root.addChild(node2);
		Node node9 = new Node(9,0);
		node2.addChild(node9);
		node9.addChild(new Node(10,2));
		root.addChild(new Node(3,2));
		Node node4 = new Node(4,2);
		root.addChild(node4);
		
		node4.addChild(new Node(5,3));
		Node node6 = new Node(6,3);
		node4.addChild(node6);
		
		node6.addChild(new Node(7,4));
		node6.addChild(new Node(8,4));
		/*        1
		 *   2    3    4
		 *   9       5   6
		 *  10          7 8
		*/            
		depthFirst(root);
		//breadthFirst(root);
		System.out.println("result="+result+", "+nodeCnt+"노드");
	}
	
	static int result;
	static int nodeCnt;
	
	static void depthFirst(Node node){
		nodeCnt++;
		result += node.value;
		System.out.printf("%d ", node.id);
		if(node.childList.size()>0){
			for(int i=0;i<node.childList.size();i++){
				depthFirst(node.childList.get(i));
			}
		}
	}
	
	static void breadthFirst(Node node){
        List<Node> list = new ArrayList<>();
        list.add(node);

        while(!list.isEmpty()){
        	nodeCnt++;
            node = list.get(0);
            if(node.childList.size()>0){
            	list.addAll(node.childList);
            }
            result += list.get(0).value;
            System.out.printf("id:%d, value=%d %n", list.get(0).id, list.get(0).value);
            list.remove(0);
        }
    }
}

class Node 
{
	int id;
	Node parent;
    int value;
    
    LinkedList<Node> childList = new LinkedList<>();//자식노드 리스트

    Node() {}
    
    Node(int value){
        this.value = value;
    }
    
    Node(int id, int value){
    	this.id = id;
    	this.value = value;
    }

    void addChild(Node child){
    	child.parent = this;
    	childList.add(child);
    }
    
    Node removeChild(Node child){
    	child.parent = null;
    	childList.remove(child);
    	return child;
    }
} // end of Node