广度优先 深度优先访问 树

 

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);
			}
		}
	}