【数据结构与算法】二叉树深度遍历（非递归）

淩亂°似流年 2022-08-11 08:58 150阅读 0赞

据说这个笔试面试的时候很容易考到，所以写到这里。

*  图示

![SouthEast][]

*  代码实现

/**
     * 源码名称：TreeIteratorNoRecursion.java 
     * 日期：2014-08-23 
     * 程序功能：二叉树深度遍历（非递归） 
     * 版权：CopyRight@A2BGeek 
     * 作者：A2BGeek
     */
    import java.util.Stack;
    
    public class TreeIteratorNoRecursion {
    	class TreeNode<T> {
    		private T mNodeData;
    		private TreeNode<T> mLeftChild;
    		private TreeNode<T> mRightChild;
    
    		public TreeNode(T data, TreeNode<T> left, TreeNode<T> right) {
    			// TODO Auto-generated constructor stub
    			mNodeData = data;
    			mLeftChild = left;
    			mRightChild = right;
    		}
    
    		public T getData() {
    			return mNodeData;
    		}
    
    		public void setData(T data) {
    			mNodeData = data;
    		}
    
    		public TreeNode<T> getLeft() {
    			return mLeftChild;
    		}
    
    		public void setLeft(TreeNode<T> left) {
    			mLeftChild = left;
    		}
    
    		public TreeNode<T> getRight() {
    			return mRightChild;
    		}
    
    		public void setRight(TreeNode<T> right) {
    			mRightChild = right;
    		}
    	}
    
    	public TreeNode<String> createTree() {
    		TreeNode<String> h = new TreeNode<String>("h", null, null);
    		TreeNode<String> g = new TreeNode<String>("g", null, null);
    		TreeNode<String> f = new TreeNode<String>("f", null, null);
    		TreeNode<String> e = new TreeNode<String>("e", null, null);
    		TreeNode<String> d = new TreeNode<String>("d", null, h);
    		TreeNode<String> c = new TreeNode<String>("c", f, g);
    		TreeNode<String> b = new TreeNode<String>("b", d, e);
    		TreeNode<String> a = new TreeNode<String>("a", b, c);
    		return a;
    	}
    
    	/*
    	 * 1、有左儿子，入栈 
    	 * 2、无左儿子，自己出栈并看右儿子是否为空 
    	 * 3、右儿子为空，出栈 
    	 * 4、右儿子不为空，入栈 
    	 * 5、入栈时输出
    	 */
    	public void preIterate(TreeNode<String> root) {
    		Stack<TreeNode<String>> stack = new Stack<TreeNode<String>>();
    		TreeNode<String> now = root;
    		do {
    			while (now != null) {
    				System.out.print(now.getData() + " ");
    				stack.push(now);
    				now = now.getLeft();
    			}
    			if (stack.size() == 0) {
    				break;
    			}
    			now = stack.pop();
    			now = now.getRight();
    		} while (stack.size() >= 0);
    	}
    
    	/*
    	 * 1、有左儿子，入栈 
    	 * 2、无左儿子，自己出栈并看右儿子是否为空 
    	 * 3、右儿子为空，出栈 
    	 * 4、右儿子不为空，入栈 
    	 * 5、出栈时输出
    	 */
    	public void midIterate(TreeNode<String> root) {
    		Stack<TreeNode<String>> stack = new Stack<TreeNode<String>>();
    		TreeNode<String> now = root;
    		do {
    			while (now != null) {
    				stack.push(now);
    				now = now.getLeft();
    			}
    			if (stack.size() == 0) {
    				break;
    			}
    			now = stack.pop();
    			System.out.print(now.getData() + " ");
    			now = now.getRight();
    		} while (stack.size() >= 0);
    	}
    
    	/*
    	 * 1、有儿子，入栈 
    	 * 2、无儿子，输出自己 
    	 * 3、儿子被输出过，输出自己
    	 */
    	public void postIterate(TreeNode<String> root) {
    		Stack<TreeNode<String>> stack = new Stack<TreeNode<String>>();
    		TreeNode<String> now = root;
    		TreeNode<String> pre = null;
    		stack.push(now);
    		while (stack.size() > 0) {
    			now = stack.peek();
    			if (now.getLeft() == null && now.getRight() == null || pre != null
    					&& (now.getLeft() == pre || now.getRight() == pre)) {
    				System.out.print(now.getData() + " ");
    				pre = now;
    				stack.pop();
    			} else {
    				if (now.getRight() != null) {
    					stack.push(now.getRight());
    				}
    				if (now.getLeft() != null) {
    					stack.push(now.getLeft());
    				}
    			}
    		}
    	}
    
    	public static void main(String[] args) {
    		TreeIteratorNoRecursion treeIteratorNoRecursion = new TreeIteratorNoRecursion();
    		TreeNode<String> root = treeIteratorNoRecursion.createTree();
    		treeIteratorNoRecursion.preIterate(root);
    		System.out.println();
    		treeIteratorNoRecursion.midIterate(root);
    		System.out.println();
    		treeIteratorNoRecursion.postIterate(root);
    	}
    }

[SouthEast]: /images/20220810/44fc7b643c9346fdb6e08bcbce41b1c8.png