범위 우선 깊이 우선 접근 트 리

public class Tst {
	static TreeNode treeFactory() {
		TreeNode a = new TreeNode("a");
		TreeNode b = new TreeNode("b");
		TreeNode c = new TreeNode("c");
		TreeNode d = new TreeNode("d");
		TreeNode e = new TreeNode("e");
		TreeNode f = new TreeNode("f");
		TreeNode g = new TreeNode("g");
		TreeNode h = new TreeNode("h");
		
		a.children.add(b); a.children.add(c);
		
		b.children.add(d); b.children.add(e);
		c.children.add(f); c.children.add(g);
		
		e.children.add(h);
		
		return a;
	}
	static void printTreeDepthFirst(TreeNode root) {
		System.out.print(root);
		if(! root.children.isEmpty()) {
			for(TreeNode child : root.children)
				printTreeDepthFirst(child);
		}
	}
	
	static ArrayList<ArrayList<TreeNode>> row;
	static void printTreeWidthFirst(TreeNode root) {
		transferTree(root, 0);
		for(ArrayList<TreeNode> list : row) {
			for(TreeNode node : list)
				System.out.print(node);
		}
	}
	
	private static void transferTree(TreeNode root, int i) {
		putNode2row(root, i);
		if(! root.children.isEmpty()) {
			i++;
			for(TreeNode child : root.children)
				transferTree(child, i);
		}
	}
	private static void putNode2row(TreeNode node, int i) {
		if(row.size() <= i) {
			row.add(new ArrayList<TreeNode>());
		}
		row.get(i).add(node);
	}
	
	public static void main(String[] args) {
		printTreeDepthFirst(treeFactory());
		
		System.out.println();
		row = new ArrayList<ArrayList<TreeNode>>();
		printTreeWidthFirst(treeFactory());
		
	}
}
class TreeNode {
	List<TreeNode> children = new ArrayList<TreeNode>();
	String name;
	public TreeNode(String name) {
		this.name = name;
	}
	public String toString() {
		return name;
	}
}

 
출력
abdehcfg
abcdefgh
 
위의 코드 의 넓이 가 우선 적 인 것 은 먼저 재 귀적 으로 옮 겨 다 니 며 재 귀적 인 데 이 터 를 List 의 List 에 넣 고 층 의 구조 로 바 꾸 는 것 입 니 다.공간 과 시간 을 비교적 많이 사용한다.'데이터 구조 P170' 을 보고 그림 의 넓이 를 우선적으로 옮 겨 다 녔 다.Queue 를 사용 하여 현재 층 의 노드 를 저장 하고 이 방법 을 최적화 할 수 있 습 니 다.
 
	static void printTreeWidthFirst(TreeNode root) {
		Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
		queue.add(root);
		System.out.print(root);
		while(!queue.isEmpty()) {
			root = queue.poll();
			for(TreeNode child : root.children) {
				System.out.print(child);
				queue.add(child);
			}
		}
	}

좋은 웹페이지 즐겨찾기