データ構造-----再構成非再帰的に二叉木を巡回します.

class BiTreeNode
{
	public BiTreeNode left;
	public BiTreeNode right;
	public int value;
	public BiTreeNode(int value)
	{
		this.value = value;
	}
}
public class BiTree {
	public int count = 0;
	public static List preOrderList = new ArrayList<>();
	public static List inOrderList = new ArrayList<>();
	public static List postOrderList = new ArrayList<>();
	
	public static List preOrderListNoRecursion = new ArrayList<>();
	public static List inOrderListNoRecursion = new ArrayList<>();
	public static List postOrderListNoRecursion = new ArrayList<>();
	
	public static List levelOrderList = new ArrayList<>();
	/**
	 *              (            -1        )
	 * @param array
	 * @return
	 */
	public BiTreeNode createBiTree(int[] array)
	{
		BiTreeNode[] nodeArray = new BiTreeNode[array.length];
		//current parent             ,parent  current%2==0       
		int current = 0;
		int parent = 0;
		while(current < array.length)
		{
			BiTreeNode node = null;
			if(array[current] != -1)
			{
				node = new BiTreeNode(array[current]);
				nodeArray[current] = node;
			}
			//                ,       if  ,           0,
			//0%0==0   nodeArray[parent].right = node;  ,                      
			if(current > 0)
			{
				if(current % 2 == 1)
					nodeArray[parent].left = node;
				else
				{
					nodeArray[parent].right = node;
					parent++;
				}
			}
			current++;
		}
		return nodeArray[0];
	}
	
	/**
	 *       (  )
	 * @param node
	 * @return
	 */
	public void preOrderTraverse(BiTreeNode node)
	{
		if(node != null)
		{
			preOrderList.add(node.value);
			preOrderTraverse(node.left);
			preOrderTraverse(node.right);
		}
	}
	
	/**
	 *       (   )
	 *     :          ,      ,          ,                  ,        temp,        ,     
	 *       ,  temp        ，     ,        ,                ;      ,              ,   
	 *                  ;
	 * @param node
	 */
	public void preOrderTraverseNoRecursion(BiTreeNode node)
	{
		Stack stack = new Stack<>();
		BiTreeNode temp = node;
		while(temp != null ||!stack.isEmpty())
		{
			while(temp != null)
			{
				preOrderListNoRecursion.add(temp.value);
				stack.push(temp);
				temp = temp.left;
			}
			if(!stack.isEmpty())
			{
				temp = stack.pop();
				temp = temp.right;
			}
		}
	}
	/**
	 *       (  )
	 * @param node
	 */
	public void inOrderTraverse(BiTreeNode node)
	{
		if(node != null)
		{
			inOrderTraverse(node.left);
			inOrderList.add(node.value);
			inOrderTraverse(node.right);
		}
	}
	
	/**
	 *       (   )
	 *     :                ，     Stack              List  
	 * @param node
	 */
	public void inOrderTraverseNoRecursion(BiTreeNode node)
	{
		Stack stack = new Stack<>();
		BiTreeNode temp = node;
		while(temp != null || !stack.isEmpty())
		{
			while(temp != null)
			{
				stack.push(temp);
				temp = temp.left;
			}
			if(!stack.isEmpty())
			{
				temp = stack.pop();
				inOrderListNoRecursion.add(temp.value);
				temp = temp.right;
			}
		}
	}
	/**
	 *       (  )
	 * @param node
	 */
	public void postOrderTraverse(BiTreeNode node)
	{
		if(node != null)
		{
			postOrderTraverse(node.left);
			postOrderTraverse(node.right);
			postOrderList.add(node.value);
		}
	}
	
	/**
	 *       (   )
	 *     :                    ,        ,      ,                   ,      ,    
	 *         ,          ,           pre              ,           ;         ,   
	 *            ，          ,         ,         ;
	 * @param node
	 */
	public void postOrderTraverseNoRecursion(BiTreeNode node)
	{
		BiTreeNode pre = null;//       
		BiTreeNode cur;//      
		Stack stack = new Stack<>();
		if(node == null)
			return;
		stack.push(node);
		while(!stack.isEmpty())
		{
			cur = stack.peek();//      
			if((cur.left == null && cur.right == null) || (pre != null && (pre == cur.left || pre == cur.right)))
			{
				postOrderListNoRecursion.add(cur.value);
				stack.pop();
				pre = cur;
			}else
			{
				if(cur.right != null)
					stack.push(cur.right);
				if(cur.left != null)
					stack.push(cur.left);
			}
		}
	}
	
	/**
	 *       
	 *      :      
	 * @param node
	 */
	public void levelOrderTraverse(BiTreeNode node)
	{
		Queue queue = new LinkedList<>();
		BiTreeNode temp;
		queue.offer(node);
		//    
		while(!queue.isEmpty())
		{
			temp = queue.poll();
			levelOrderList.add(temp.value);
			if(temp.left != null)
				queue.offer(temp.left);
			if(temp.right != null)
				queue.offer(temp.right);
		}
	}
	/**
	 *     
	 * @param list
	 */
	public void print(List list,String content)
	{
		System.out.print(content+": ");
		for(int i = 0;i < list.size();i++)
			System.out.print(list.get(i)+" ");
		System.out.println();
	}
	
	public static void main(String[] args) {
		BiTree tree = new BiTree();
		int[] array = {1,2,3,4,5,-1,-1,-1,-1,6,7};
		BiTreeNode node = null;
		node = tree.createBiTree(array);
		//    
		tree.preOrderTraverse(node);
		tree.print(preOrderList, "    (  )");
		tree.inOrderTraverse(node);
		tree.print(inOrderList, "    (  )");
		tree.postOrderTraverse(node);
		tree.print(postOrderList, "    (  )");
		//     
		tree.preOrderTraverseNoRecursion(node);
		tree.print(preOrderListNoRecursion, "    (   )");
		tree.inOrderTraverseNoRecursion(node);
		tree.print(inOrderListNoRecursion, "    (   )");
		tree.postOrderTraverseNoRecursion(node);
		tree.print(postOrderListNoRecursion, "    (   )");
		//    
		tree.levelOrderTraverse(node);
		tree.print(levelOrderList, "    ");
	}
}