`
dwlovehcy
  • 浏览: 32885 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

非递归(栈)完成二叉树的前中后序遍历

 
阅读更多
import java.util.Stack;

/**
 *
 * @author ss
 * 用栈完成二叉树的遍历
 */
public class Node {

	//三个属性   值 左节点 右节点
	private String value;
	private Node nodeLeft;
	private Node nodeRight;
	
	public Node(String value){
		this.value=value;
	}
	
	private static void showValue(String value){
		System.out.println(value);
	}
	/**
	 * 构造二叉树
	 * @return
	 */
	private static Node init(){
		Node node1=new Node("A");
		Node node2=new Node("B");
		Node node3=new Node("C");
		Node node4=new Node("D");
		Node node5=new Node("E");
		Node node6=new Node("F");
		Node node7=new Node("G");
		node1.nodeLeft=node2;
		node1.nodeRight=node3;
		node2.nodeLeft=node4;
		node2.nodeRight=node5;
		node3.nodeLeft=node6;
		node3.nodeRight=node7;
		//返回根节点
		return node1;
	}
	/**
	 * 前序遍历二叉树
	 * @param node
	 */
	public static void iteratorPreNodeTree(Node node){
		Stack<Node> stack=new Stack<Node>();
		if(node!=null){
			stack.push(node);
			while(!stack.empty()){
				node=stack.pop();
				showValue(node.value);
				if(node.nodeRight!=null){
					stack.push(node.nodeRight);
				}
				if(node.nodeLeft!=null){
					stack.push(node.nodeLeft);
				}
			}
		}
	}
	
	/**
	 * 中序遍历二叉树
	 * @param args
	 */
	public static void iterarorMidNodeTree(Node node){
        Stack<Node> stack=new Stack<Node>();
        while(node!=null){
        	while(node!=null){
        		if(node.nodeRight!=null){
        			stack.push(node.nodeRight);//将右节点压入栈
        		}
        		stack.push(node);//将当前节点压入栈
        		node=node.nodeLeft;
        	}
        	node=stack.pop();
        	while(!stack.empty()&&node.nodeRight==null){
        		showValue(node.value);
        		node=stack.pop();//取出左节点之后取出根节点
        	}
        	showValue(node.value);
        	if(!stack.empty()){
        		node=stack.pop();
        	}else{
        		node=null;
        	}
        }
	}
	
	/**
	 * 后序遍历二叉树
	 * @param node
	 */
	public static void iteratorPostNodeTree(Node node){
		//定义标记node 记录上一个节点
		Node tempNode=node;
		Stack<Node> stack=new Stack<Node>();
		while(node!=null){
			//左节点入栈
			for(;node.nodeLeft!=null;node=node.nodeLeft){
				stack.push(node);
			}
				//当前节点无右子 或者右子已经输出
				while(node!=null&&(node.nodeRight==null||node.nodeRight==tempNode)){
					showValue(node.value);
					tempNode=node;
					if(stack.empty()){
						return;
					}
					node=stack.pop();
		}
				
				//处理右子
				stack.push(node);
				node=node.nodeRight;
		}
	}
	//单元测试
	public static void main(String[] args) {
		Node root=init();
		System.out.println("前序遍历二叉树");
		iteratorPreNodeTree(root);
		System.out.println("中序遍历二叉树");
		iterarorMidNodeTree(root);
		System.out.println("后序遍历二叉树");
		iteratorPostNodeTree(root);
	}
	
}

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics