二叉树的各种非递归遍历

二叉树的结构：

package com.ydp.tree.btree;public class BTreeNode {		public BTreeNode rchild = null;		public BTreeNode lchild = null;		public int	data;				public boolean isFirst = true;//后序遍历使用，是否是首次入栈				public BTreeNode(){}		public BTreeNode(int data){			this.data=data;		}	}

二叉树的各种遍历：

package com.ydp.tree.btree;import java.util.ArrayList;import java.util.List;import java.util.Queue;import java.util.Stack;import java.util.concurrent.ArrayBlockingQueue;public class BTree {	public static void main(String[] args) {		BTree tree = new BTree();		BTreeNode root = new BTreeNode();			ArrayList<Integer> list = new ArrayList<Integer>();		for(int i=1;i<=10;i++){			list.add(i);		}		tree.createTree(root,list);		System.out.println("层次遍历：");		tree.levelOrder(root);		System.out.println("\n先序遍历：");		tree.preOrder(root);		System.out.println("\n中序遍历：");		tree.midOrder(root);		System.out.println("\n后序遍历：");		tree.postOrder(root);	}			//创建二叉树	 void createTree(BTreeNode root,List<Integer> list){			 BTreeNode node = root;		 root.data=list.get(0);		 int index = 1;		 Queue<BTreeNode> queue = new ArrayBlockingQueue<BTreeNode>(100);		 		 while(index < list.size() && node != null){			 node.lchild=new BTreeNode(list.get(index));			 queue.add(node.lchild);			 if(++index < list.size()){				 node.rchild=new BTreeNode(list.get(index));				 queue.add(node.rchild);			 }			 index++;			 node = queue.poll();		 }		 }	//层次遍历	 void levelOrder(BTreeNode root){		 Queue<BTreeNode> queue = new ArrayBlockingQueue<BTreeNode>(100);		 queue.add(root);		 BTreeNode node = null;		 while(queue.size()>0){			 node = queue.poll();			 System.out.print(node.data+" ");			 if(node.lchild != null){				 queue.add(node.lchild);			 }			 if(node.rchild != null){				 queue.add(node.rchild);			 }		 }		 	 }	 	 //先序遍历	 void preOrder(BTreeNode root){		 Stack<BTreeNode> stack = new Stack<BTreeNode>();		 BTreeNode node = root;			 		 while(node != null || !stack.empty()){			 while(node != null){				 System.out.print(node.data+" ");				 stack.push(node);				 node = node.lchild;			 }			 			 node = stack.pop();						 node = node.rchild;		 }		 }	 	 //中序遍历	 void midOrder(BTreeNode root){		 Stack<BTreeNode> stack = new Stack<BTreeNode>();		 BTreeNode node = root;				 		 while(node != null || !stack.empty()){			 while(node != null){				 stack.push(node);				 node = node.lchild;			 }			 			 node = stack.pop();			 System.out.print(node.data+" ");			 node = node.rchild;		 }			 }	 	//后序遍历	 void postOrder(BTreeNode root){		 Stack<BTreeNode> stack = new Stack<BTreeNode>();		 BTreeNode node = root;		 		 while(node != null || !stack.empty() ){			 while(node != null && node.isFirst != false){				 stack.push(node);				 node = node.lchild;			 }			 node = stack.pop();			 if(node.isFirst == false || node.rchild == null ){				 System.out.print(node.data +" ");				 node = null;			 }else{				 node.isFirst = false;				 stack.push(node);				 node = node.rchild;			 }		 }	 }	}

原标题：二叉树的各种非递归遍历

关键词：