二叉树的遍历-递归和非递归

文章目录

1. 二叉树
2. 递归遍历
3. 非递归遍历
4. 演示
5. 参考

二叉树

二叉树是一种较为常见的数据结构，不了解的点我，他在各大公司的笔试/面试中经常出现，特别是它的遍历。
二叉树的遍历共三种：

前序遍历：根节点->左孩子节点->右孩子节点
中序遍历：左孩子节点->根节点->右孩子节点
后续遍历：左孩子节点->右孩子节点->根节点

递归遍历

该遍历最为经典也最为简单的就是使用递归方法来做：

private void preOrderTraversalRecursive(BitNode node)
{
	if(node ==null)
		return;
	
	System.out.print(node.val+",");
	preOrderTraversalRecursive(node.left);
	preOrderTraversalRecursive(node.right);
}



public void inOrderTraversalRecursive(BitNode node)
{
	if(node ==null)
		return;
	inOrderTraversalRecursive(node.left);
	System.out.print(node.val+",");
	inOrderTraversalRecursive(node.right);
}



public void postOrderTraversalRecursive(BitNode node)
{
	if(node ==null)
		return;
	postOrderTraversalRecursive(node.left);
	postOrderTraversalRecursive(node.right);
	System.out.print(node.val+",");
}

本文主要讨论二叉树的非递归遍历（也是面试官们喜欢的提问点）。

非递归遍历

在用非递归进行二叉树的遍历时最主要借助的结构就是Stack

前序遍历

前序遍历使用栈可以轻松的搞定：

将根节点Node压入栈
取出栈顶将其进行打印，同时将取得元素的左右孩子节点分别入栈

直至栈中的元素全部取光

/**
 * 前序遍历 
 */
public void preOrderTraversal()
{
	Stack<BitNode> stack=new Stack<BitNode>();
	BitNode node;
	if(root!=null)
	{
		stack.push(root);
		while(stack.size()>0)
		{
			node=stack.pop();
			System.out.print(node.val+",");
			if(node.right!=null)
				stack.push(node.right);
			if(node.left!=null)
				stack.push(node.left);
		}
	}
}

中序遍历

中序遍历在使用栈是不能简单的按前序的做法进行操作，因为他最先需要输出的左孩子节点

首选将当前节点root的各个左子节点压入栈
然后依次从栈中取数据，进行打印，将当前节点置为栈顶的右孩子节点，回到1

直至栈为空

/**
 * 中序遍历 
 */
public void inOrderTraversal()
{
	Stack<BitNode> stack=new Stack<BitNode>();
	BitNode node=root;
	while(node!=null || stack.size()>0)
	{
		while(node!=null)
		{
			stack.push(node);
			node=node.left;
		}
		
		if(stack.size()>0)
		{
			node=stack.pop();
			System.out.print(node.val+",");
			node=node.right;
		}
	}
}

后续遍历

后序遍历比中序更为复杂一点，不过大致思路类似

首先将当前节点的各个又孩子节点进行入数据栈，同时将该节点的值压入一个值栈
然后依次从数据栈中取数据，将当前节点置为数据栈顶元素的左孩子节点，回到1

直至数据栈为空，此时再依次遍历值栈进行打印即可

/**
 * 后续遍历 
 */
public void postOrderTraversal()
{
	Stack<BitNode> stack=new Stack<BitNode>();
	Stack<Integer> valStack=new Stack<Integer>();
	BitNode node=root;
	while(node!=null || stack.size()>0)
	{
		while(node!=null)
		{
			stack.push(node);
			valStack.push(node.val);
			node=node.right;
		}
		
		node=stack.pop();
		node=node.left;
	}
	
	while(valStack.size()>0)
	{
		System.out.print(valStack.pop()+",");
	}
}

演示

下面给出全部的代码：

import java.util.Stack;

public class BitTree {
	
	
	BitNode root;
	
	
	public static void main(String[] args)
	{
		int[] array={1,2,3,4,5,6,7,0,0,0,0,8,0,0,0};
		
		BitTree tree=BitTree.createBitTree(array);
		System.out.println("前序遍历");
		System.out.println("非递归形式");
		tree.preOrderTraversal();
		System.out.println("\r\n递归形式");
		tree.preOrderTraversalRecursive();
		
		System.out.println("\r\n\r\n中序遍历");
		System.out.println("非递归形式");
		tree.inOrderTraversal();
		System.out.println("\r\n递归形式");
		tree.inOrderTraversalRecursive();
		
		System.out.println("\r\n\r\n后序遍历");
		System.out.println("非递归形式");
		tree.postOrderTraversal();
		System.out.println("\r\n递归形式");
		tree.postOrderTraversalRecursive();
		
	}
	
	
	
	
	
	/**
	 * 创建一颗树
	 * @param array
	 * @return
	 */
	public static BitTree createBitTree(int[] array)
	{
		BitTree bitTree=new BitTree();
		bitTree.root=bitTree.createBitTree(array,0);
		return bitTree;
	}
	
	private BitNode createBitTree(int[] array,int i)
	{
		if(i>=array.length || array[i]==0)
			return null;
		
		BitNode node=new BitNode();
		node.val=array[i];
		
		node.left=createBitTree(array,2*i+1);
		node.right=createBitTree(array,2*i+2);
		return node;
	}
	
	/**
	 * 前序遍历 
	 */
	public void preOrderTraversal()
	{
		Stack<BitNode> stack=new Stack<BitNode>();
		BitNode node;
		if(root!=null)
		{
			stack.push(root);
			while(stack.size()>0)
			{
				node=stack.pop();
				System.out.print(node.val+",");
				if(node.right!=null)
					stack.push(node.right);
				if(node.left!=null)
					stack.push(node.left);
			}
		}
	}
	
	/**
	 * 中序遍历 
	 */
	public void inOrderTraversal()
	{
		Stack<BitNode> stack=new Stack<BitNode>();
		BitNode node=root;
		while(node!=null || stack.size()>0)
		{
			while(node!=null)
			{
				stack.push(node);
				node=node.left;
			}
			
			if(stack.size()>0)
			{
				node=stack.pop();
				System.out.print(node.val+",");
				node=node.right;
			}
		}
	}
	
	/**
	 * 后续遍历 
	 */
	public void postOrderTraversal()
	{
		Stack<BitNode> stack=new Stack<BitNode>();
		Stack<Integer> valStack=new Stack<Integer>();
		BitNode node=root;
		while(node!=null || stack.size()>0)
		{
			while(node!=null)
			{
				stack.push(node);
				valStack.push(node.val);
				node=node.right;
			}
			
			node=stack.pop();
			node=node.left;
		}
		
		while(valStack.size()>0)
		{
			System.out.print(valStack.pop()+",");
		}
	}
	
	
	
	/**
	 * 前序遍历（递归形式）
	 */
	public void preOrderTraversalRecursive()
	{
		preOrderTraversalRecursive(root);
	}
	
	private void preOrderTraversalRecursive(BitNode node)
	{
		if(node ==null)
			return;
		
		System.out.print(node.val+",");
		preOrderTraversalRecursive(node.left);
		preOrderTraversalRecursive(node.right);
	}
	
	/**
	 * 中序遍历（递归形式）
	 */
	public void inOrderTraversalRecursive()
	{
		inOrderTraversalRecursive(root);
	}
	
	public void inOrderTraversalRecursive(BitNode node)
	{
		if(node ==null)
			return;
		inOrderTraversalRecursive(node.left);
		System.out.print(node.val+",");
		inOrderTraversalRecursive(node.right);
	}
	
	/**
	 * 后序遍历（递归形式）
	 */
	public void postOrderTraversalRecursive()
	{
		postOrderTraversalRecursive(root);
	}
	
	public void postOrderTraversalRecursive(BitNode node)
	{
		if(node ==null)
			return;
		postOrderTraversalRecursive(node.left);
		postOrderTraversalRecursive(node.right);
		System.out.print(node.val+",");
	}
	
	/**
	 * 二叉树的节点
	 * @author Administrator
	 *
	 */
	static class BitNode
	{
		int val;
		BitNode left,right;
	}
}

该二叉树使用数组来表示建立，对应为：

最终得到的结果为：

前序遍历
非递归形式
1,2,4,5,3,6,8,7,
递归形式
1,2,4,5,3,6,8,7,

中序遍历
非递归形式
4,2,5,1,8,6,3,7,
递归形式
4,2,5,1,8,6,3,7,

后序遍历
非递归形式
4,5,2,8,6,7,3,1,
递归形式
4,5,2,8,6,7,3,1,

参考

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权kubiCode，并且，不得用于商业用途。如您有任何疑问或者授权方面的协商，请给我留言。

Kubi Code'Blog

The palest ink is better than the best memory.