树的深度优先与广度优先遍历

原题出自百度的笔试：

简述树的深度优先及广度优先遍历算法,并说明非递归实现。

 

当时我看到这个题目的时候，已经完全记不得非递归算法该怎么实现了，后来查阅了一下，要用到两个辅助的数据结构：

深度优先遍历--->栈；

广度优先遍历--->队列；

这里以二叉树为例来实现。

import java.util.ArrayDeque;

public class BinaryTree {
	static class TreeNode{
		int value;
		TreeNode left;
		TreeNode right;
		
		public TreeNode(int value){
			this.value=value;
		}
	}
	
	TreeNode root;
	
	public BinaryTree(int[] array){
		root=makeBinaryTreeByArray(array,1);
	}

	/**
	 * 采用递归的方式创建一颗二叉树
	 * 传入的是二叉树的数组表示法
	 * 构造后是二叉树的二叉链表表示法
	 */
	public static TreeNode makeBinaryTreeByArray(int[] array,int index){
		if(index<array.length){
			int value=array[index];
			if(value!=0){
				TreeNode t=new TreeNode(value);
				array[index]=0;
				t.left=makeBinaryTreeByArray(array,index*2);
				t.right=makeBinaryTreeByArray(array,index*2+1);
				return t;
			}
		}
		return null;
	}
	
	/**
	 * 深度优先遍历，相当于先根遍历
	 * 采用非递归实现
	 * 需要辅助数据结构：栈
	 */
	public void depthOrderTraversal(){
		if(root==null){
			System.out.println("empty tree");
			return;
		}		
		ArrayDeque<TreeNode> stack=new ArrayDeque<TreeNode>();
		stack.push(root);		
		while(stack.isEmpty()==false){
			TreeNode node=stack.pop();
			System.out.print(node.value+"    ");
			if(node.right!=null){
				stack.push(node.right);
			}
			if(node.left!=null){
				stack.push(node.left);
			}			
		}
		System.out.print("\n");
	}

	/**
	 * 广度优先遍历
	 * 采用非递归实现
	 * 需要辅助数据结构：队列
	 */
	public void levelOrderTraversal(){
		if(root==null){
			System.out.println("empty tree");
			return;
		}
		ArrayDeque<TreeNode> queue=new ArrayDeque<TreeNode>();
		queue.add(root);
		while(queue.isEmpty()==false){
			TreeNode node=queue.remove();
			System.out.print(node.value+"    ");
			if(node.left!=null){
				queue.add(node.left);
			}
			if(node.right!=null){
				queue.add(node.right);
			}
		}
		System.out.print("\n");
	}
	
	/** 
	 *                  13
	 *                 /  \
	 *               65    5
	 *              /  \    \
	 *             97  25   37
	 *            /    /\   /
	 *           22   4 28 32
	 */
	public static void main(String[] args) {
		int[] arr={0,13,65,5,97,25,0,37,22,0,4,28,0,0,32,0};
		BinaryTree tree=new BinaryTree(arr);
		tree.depthOrderTraversal();
		tree.levelOrderTraversal();
	}
}