欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二叉树前序、中序、后序、层序遍历非递归方式

程序员文章站 2022-05-16 14:21:57
...

我们先回顾一下二叉树的遍历

二叉树前序、中序、后序、层序遍历非递归方式

前序遍历:根——左——右

ABDECFG

中序遍历:左——根——右

DBEAFCG

后序遍历:左——右——根

DEBFGCA

层序遍历:从上到下从左到右

ABCDEFG

前序遍历

思路:思路很简单,从根节点开始,输出节点的值,然后分别遍历该节点的左子树和右子树,具体实现是创建一个栈stack,用来存储节点,用while循环,如果当前节点不为null或者stack不为null,则输出当前节点,并把当前节点入栈,将当前节点指向左子树,如果当前节点为null,则从stack中取出赋给当前节点,然后将当前节点的右子树赋给当前节点。

代码:

/**
 * 
 * @param 先序遍历非递归
 *       A
 *     /   \
      B      C
    /  \    / \
   D    E  F   G
   
   ABDECFG
 */
public static void preOrder(TreeNode t)
 {
		Stack<TreeNode> stack = new Stack<TreeNode>();
		TreeNode currnode = t;
		while (currnode != null || !stack.isEmpty()) {
			if (currnode != null) {
				System.out.println(currnode.data);
				stack.push(currnode);
				currnode = currnode.left;
			} else {
				currnode = stack.pop();
				currnode = currnode.right;
			}
		}
	}

中序遍历

思路:和前序遍历一样,不同的是输出的位置不一样。

代码:

/**
 * 
 * @param 中序遍历非递归
 *       A
 *     /   \
      B      C
    /  \    / \
   D    E  F   G
   
   DBEAFCG
 */
public static void inOrder(TreeNode t)
{
	Stack<TreeNode> stack = new Stack<TreeNode>();
	TreeNode currnode = t;
	while (currnode != null || !stack.isEmpty()) {
		if (currnode != null) {
			
			stack.push(currnode);
			
			currnode = currnode.left;
		} else {
			currnode = stack.pop();
			System.out.println(currnode.data);
			currnode = currnode.right;
		}
	}
}

后序遍历

思路:我们需要构造两个stack分别为stack和result,一个用来存储逆序后的结果(用来最终输出),另一个用于过程存储。

具体思路是,使当前节点等于根节点,当当前节点不为null,或者stack不为null的时候,循环遍历该树,先将当前节点存入stack和result,如果当前节点的左子树不为null,则把左子树赋给当前节点,否则将栈中的第一个元素赋给当前节点,然后将当前节点 指向他的右子树,最后输出result中的值

代码:

/**
 * 
 * @param 后序遍历非递归
 *       A
 *     /   \
      B      C
    /  \    / \
   D    E  F   G
   
   DEBFGCA
 */
public static void postOrder(TreeNode t)
{
	Stack<TreeNode> stack = new Stack<TreeNode>();
	Stack<TreeNode> result = new Stack<TreeNode>();
	TreeNode node = t;
	while(node!=null||!stack.isEmpty()){
	  if(node!=null)
	  {
		  stack.push(node);
		  result.push(node);
		  node = node.right;
	  }else{
		  node = stack.pop();
		  node = node.left;
	  }
		  
		
	}
	System.out.println(result.size());
	while(!result.isEmpty())
	{
		System.out.println(result.pop().data);
	}
 }

层序遍历

思路:利用队列先进先出,从根节点开始放入队列,如果该节点的左子树不为null,放入队列,如果该节点的右子树也不为null,放入队列,将当前节点赋值为队列头节点(poll取出并删除)循环该过程

代码:

public static void lingOrder(TreeNode t)
{
    Queue<TreeNode> q = new LinkedList<TreeNode>();	
    q.add(t);
    while(!q.isEmpty())
    {TreeNode node = q.poll();
    	System.out.println(node.data);
    	if(node.left!=null)
    	{
    		q.add(node.left);
    	}if(node.right!=null)
    	{
    		q.add(node.right);
    	}
    	
    }
}

 

参考:https://www.cnblogs.com/yaobolove/p/6213936.html