Java迭代实现二叉树的前序、中序、后序遍历

冷不防 2022-08-07 06:52 169阅读 0赞

我们都知道，二叉树的遍历有三种形式：前序遍历、中序遍历、后序遍历，三种遍历的规则分别如下：

1）前序遍历：先遍历根节点，然后遍历左子节点，最后遍历右子节点，简记为“根-左-右”；

2）中序遍历：先遍历左子节点，然后遍历根节点，最后遍历右子节点，简记为“左-根-右”；

3）后序遍历：先遍历左子节点，然后遍历右子节点，最后遍历根节点，简记为“左-右-根”；

根据遍历规则，我们可以采用“递归”的方式很快的实现，这些程序相对比较简单，我在这里就不一一写了，今天主要写一下通过迭代的方式实现二叉树的三种遍历。

二叉树的定义如下：

<span style="font-size:14px;">public class TreeNode {
    	int val;
    	TreeNode left;
    	TreeNode right;
    	TreeNode(int x) { 
    		val = x; 
    	}
    }</span>

在使用迭代的方式遍历的过程中，需要维护一个栈用来保存遍历的节点信息，同时在程序中维护了一个List用来保存树节点对应的值，相应代码如下所示：

前序遍历：

public class PreorderTraversal {
    	
    	List<Integer> result = new ArrayList<Integer>();
    	
    	/**
    	 * 迭代实现，维护一个栈，因为入栈顺序按照根右左进行入栈，因此首先将根出栈，然后出栈左子节点，
    	 * 最后出栈右子节点。
    	 * @param root
    	 * @return
    	 */
    	public List<Integer> preorderTraversal(TreeNode root) {
    		if(root == null) 
    			return result;
    		Stack<TreeNode> stack = new Stack<TreeNode>();
    		stack.push(root);
    		while(!stack.isEmpty()) {
    			TreeNode node = stack.pop();
    			result.add(node.val);
    			if(node.right != null)
    				stack.push(node.right);
    			if(node.left != null) 
    				stack.push(node.left);
    		}
    		return result;
    	}
    }

中序遍历：

public class InorderTraversal {
    	
    	private List<Integer> result = new ArrayList<Integer>();
    	
    	/**
    	 * 迭代实现，首先依次将左子节点全部加入栈中，所以第一个while循环后栈顶元素对应一个子树的最
    	 * 左子节点，然后将该元素出栈加入list，并判断该元素的遍历该节点的右子树。
    	 * @param root
    	 * @return
    	 */
    	public List<Integer> inorderTraversal(TreeNode root) {
    		if(root == null)
    			return result;
    		Stack<TreeNode> stack = new Stack<TreeNode>();
    		do {
    			//依次将左节点均加入栈中
    			while(root != null) {
    				stack.push(root);
    				root = root.left;
    			}
    			if (!stack.isEmpty()) {
    				root = stack.pop();
    				result.add(root.val);  
    				root = root.right;
    			}
    		} while(!stack.isEmpty() || root != null);
    		return result;
    	}
    }

后序遍历：

public class PostorderTraversal {
    	
    	private List<Integer> result = new ArrayList<Integer>();
    	
    	/**
    	 * 迭代实现，使用栈实现，出栈得到节点顺序为根右左，每次向list最开头插入元素
    	 * @param root
    	 * @return
    	 */
    	public List<Integer> postorderTraversal(TreeNode root) {
    		if(root == null)
    			return result;
    		Stack<TreeNode> stack = new Stack<TreeNode>();
    		stack.push(root);   //首先将根节点压栈
    		while(!stack.isEmpty()) {
    			TreeNode ele = stack.pop(); //首先出栈的为根节点，其后先出右子节点，后出左子节点
    			if(ele.left != null)
    				stack.push(ele.left);  //将左子节点压栈
    			if(ele.right != null) {
    				stack.push(ele.right); //将右子节点压栈
    			}
    			result.add(0, ele.val); //因为出栈顺序为“根右左”，所以需要每次将元素插入list开头
    		}
    		return result;
    	}
    }