java实现二叉树的非递归遍历与解析

朱雀 2021-09-15 01:16 191阅读 0赞

**先序遍历**

根据先序遍历的访问顺序，先访问根节点，然后再访问左子树和右子树。对于树中的任意一个节点，都可以看作是一个根节点（也可以看成是一个树），因此可以直接访问根节点，访问完根节点，如果它的左子树不为空，用相同的方法访问它的左子树，直到左子树为空，再访问它的右子树。

对于树中的任意一个节点 p:

（1）访问 p，并将节点入栈；

（2）判断节点p的左孩子是否为空，若不为空，则将p的左孩子置为当前的结点p;

（3）若为空，则取栈顶结点并进行出栈操作（根据出栈结点去找该结点的右孩子），并将栈顶结点的右孩子置为当前的结点p，循环至1；

**中序遍历**

根据中序遍历的访问顺序，优先访问根节点的左孩子，而左孩子又可以看成是一个根节点，将当前节点压栈继续访问其左孩子，指代遇到左孩子为空的节点才对该结点进行访问，然后按照相同的方法遍历右孩子。

对于树中的任意结点 p：

（1）若p的左孩子不为空，将p压栈，并将p的左孩子置为当前节点p，然后对当前节点重复操作。

（2）若p的左孩子为空，将栈顶元素出栈并进行访问，把当前节点置为p的右孩子。

（3）直到栈为空且p为空。

**后序遍历**

根据后序遍历的访问顺序，优先访问左孩子，再访问右孩子，之后才能访问根节点。

对于任意一个节点：

（1）直接访问：如果该结点没有左孩子和右孩子可以直接访问该结点；

> 如果其左孩子和右孩子被访问过了，可以直接访问该结点；

这一步实现要借助于当前节点和在当前节点前一个被访问节点之间的关系来判断。如果当前节点的左孩子是前一个被访问的结点，那么右节点是空，可以输出当前根节点，如果当前节点的右孩子是前一个被访问的节点，说明右孩子被访问过了，可以把当前根节点输出。

（2）如果不是（1）中的情况，先将右孩子压栈，再将左孩子压栈，这样出栈顺序就是先出左孩子再出右孩子。

import java.util.Stack;
    
    public class Iterator1
    {
    	//先序遍历
    	 public void preIterator(BiTree root)
    	 {
    		 if(root == null)
    			 return;
    		 Stack<BiTree> stack = new Stack<BiTree>();
    		 BiTree p = root;
    		 while(!stack .empty() || p != null  )
    		 {
    			 
    			while(p != null)
    			{
    				System.out.print(p.val + "-->");//若节点不为空先访问再压栈（每个节点都可以看成根节点）
    				stack.push(p);
    				p = p.left;//将当前节点置为p的左孩子，若不为空继续访问并压栈
    			}
    			//当p为空时，说明根节点和左孩子打印遍历完毕了，接下来出栈遍历右孩子
    			 if(!stack.empty())
    			 {
    				 p = stack.pop();
    				 p = p.right;
    			 }
    		 }
    	 }
    	 //中序遍历
    	 public void inIterator(BiTree root)
    	 {
    		 if(root == null)
    			 return;
    		 Stack<BiTree> stack = new Stack<BiTree>();
    		 BiTree p = root;//让p指向根节点
    		 while(!stack .empty() || p != null  )
    		 {
    			 //一直遍历到左子树最下边，边遍历边保存根节点到栈中(每个节点都可以看成一个新的子树的根节点)
    			 while(p != null)  
    			 {
    				 stack.push(p);//若节点的左孩子不为空，将左孩子压栈，因为需要借助遍历过的节点进入右子树
    				 p = p.left;
    			 }
    			 //当p为空时，说明已经到达左子树最下边，这时需要出栈了
    			 if(stack != null)
    			 {
    				 p = stack.pop();
    				 System.out.print(p.val + "-->");//访问根节点
    				 p = p.right;//进入右子树，此时p是右子树的根节点（开始新一轮的遍历）
    			 }
    		 }
    		 
    	 }
    	 //后序遍历
    	 public  void postIterator(BiTree root)
    	 {
    		 if(root == null)
    			 return;
    		 Stack<BiTree> stack = new Stack<BiTree>();
    		 BiTree pre = null;//当前节点的之前访问的节点
    		 BiTree current;
    		 stack.push(root);
    		 while(!stack.empty())
    		 {
    			 current = stack.peek();
    			 if((current.left == null && current.right == null) ||  //当前节点是叶子节点，可以直接访问该节点
    					 (pre != null &&(pre == current.left|| pre == current.right)))
    				 //当前一个节点不为空并且是当前节点的左孩子或者右孩子，当是左孩子时说明当前节点右孩子为空，当是右孩子时，说明左右孩子都访问过了，且都不为空
    			 {
    				System.out.print(current.val + "-->"); 
    				stack.pop();
    				pre = current;
    			 }
    			 else  //当前节点为栈顶元素  如果当前节点不是叶子节点，在当前节点之前访问的那个节点不是当前节点的孩子，则进行压栈
    			 {
    				 if(current.right != null) //先压栈右节点再压栈左节点 这样出栈时是先左后右
    				 {
    					 stack.push(current.right);
    				 }
    				 if(current.left != null)
    				 {	 
    					 stack.push(current.left);
    				 }
    			 }
    		 }
    	 }
    	 
    	 public static void main(String[] args)
    	{
    		BiTree root = BiTree.buildTree();
    		Iterator1 iterator = new Iterator1();
    		iterator.preIterator(root);
    		System.out.println();
    		iterator.inIterator(root);
    		System.out.println();
    		iterator.postIterator(root);
    	}
    }

**层次遍历：**

public void levelOrder(BiTree root){
    		if(root==null){
    			return;
    		}
    		BiTree node;
    		Queue<BiTree> queue=new LinkedList<BiTree>();
    		queue.add(root);
    		while(queue.size()>0){
    			node=queue.poll();
    			System.out.print(node.val+"-->");
    			if(node.left!=null){
    				queue.add(node.left);
    			}
    			if(node.right!=null){
    				queue.add(node.right);
    			}
    		}
    	}

转自： http://blog.csdn.net/snow\_7/article/details/51788172