【Java】 二叉树的遍历（递归与循环+层序遍历）

时间：2024-01-06 14:48:14

在【Java】 大话数据结构(9) 树（二叉树、线索二叉树）一文中，已经实现了采用递归方法的前、中、后序遍历，本文补充了采用循环的实现方法、以及层序遍历并进行了一个总结。

递归实现

/*

 * 前序遍历

 */

public void preOrder() {

    preOrderTraverse(root);

    System.out.println();

}

private void preOrderTraverse(BiTNode<E> node) {

    if(node==null)

        return;

    System.out.print(node.data);

    preOrderTraverse(node.lchild);

    preOrderTraverse(node.rchild);

}

/*

 * 中序遍历

 */

public void inOrder() {

    inOrderTraverse(root);

    System.out.println();

}

private void inOrderTraverse(BiTNode<E> node) {

    if(node==null)

        return;

    inOrderTraverse(node.lchild);

    System.out.print(node.data);

    inOrderTraverse(node.rchild);

}

/*

 * 后序遍历

 */

public void postOrder() {

    postOrderTraverse(root);

    System.out.println();

}

private void postOrderTraverse(BiTNode<E> node) {

    if(node==null)

        return;

    postOrderTraverse(node.lchild);

    postOrderTraverse(node.rchild);

    System.out.print(node.data);

}

非递归实现（迭代）

　　 非递归实现，需要先创建一个栈，利用其特性来进行储存和输出。

  • 前序遍历，先输出当前点的值，一直沿着左子树进行读取，没左子树就在右子树重复上述过程。
  • 中序遍历与前序遍历基本一致，只是输出值的代码位置不同。
  • 后序遍历由于要左右子树输出完后才能输出根结点，所以增加一个栈进行标记是否完成左右子树的输出，其余思想基本类似。

　　下面代码中，要注意node的结点位置和stack.peek()的位置关系。

　　此外，在后序非递归遍历的过程中，栈中保留的是当前结点的所有祖先。这是和先序及中序遍历不同的。在某些和祖先有关的算法中，此算法很有价值。

	/**

	 * 前序遍历（非递归）

	 */

	public void preOrder2() {

		preOrder2(root);

		System.out.println();

	}

	private void preOrder2(BiTNode node) {

		Stack<BiTNode> stack = new Stack<BiTNode>();

		while(node!=null||!stack.isEmpty()) {

			while(node!=null) {

				System.out.print(node.data);

				stack.push(node);

				node=node.lchild;

			}

			node=stack.pop().rchild;

		}

	}

	/**

	 * 中序遍历

	 */

	public void inOrder2() {

		inOrder2(root);

		System.out.println();

	}

	private void inOrder2(BiTNode node) {

		Stack<BiTNode> stack = new Stack<BiTNode>();

		while(node!=null||!stack.isEmpty()) {

			while(node!=null) {

				stack.push(node);

				node=node.lchild;

			}

			node=stack.pop();

			System.out.print(node.data);

			node=node.rchild;

		}

	}

	/**

	 * 后序遍历

	 */

	public void postOrder2() {

		postOrder2(root);

		System.out.println();

	}

	private void postOrder2(BiTNode node) {

		Stack<BiTNode> stack = new Stack<BiTNode>();

		Stack<Integer> tag = new Stack<Integer>(); 
//下面这段注释也能实现，与后面未注释部分基本一致。代表了自己的思考过程，就不删除了

//		while(node!=null||!stack.isEmpty()) {

//			while(node!=null){

//				stack.push(node);

//				tag.push(0);

//				node=node.lchild;

//			}

			//注释中的tag用于标记当前结点是否完成左右子结点遍历（所以用0，1表示）

//			while(!tag.isEmpty()&&tag.peek()==1) {  //栈顶节点的左右子结点已完成遍历

//				System.out.print(stack.pop().data);

//				tag.pop();

//			}

//			if(!tag.isEmpty()) {   //上面和这里的 !flag.isEmpty() 不可省略，不然会出错。

//				tag.pop();

//				tag.push(1);

//				node=stack.peek().rchild;

//			}

//		}

		/*后序遍历时，分别从左子树和右子树共两次返回根结点（用tag表示次数），

		 * 只有从右子树返回时才访问根结点，所以增加一个栈标记到达结点的次序。

		 */

		while(node!=null||!stack.isEmpty()) {

			if(node!=null){

				stack.push(node);

				tag.push(1);  //第一次访问

				node=node.lchild;

			}else {

				if(tag.peek()==2) {

					System.out.print(stack.pop().data);

					tag.pop();

				}else {

					tag.pop();

					tag.push(2); //第二次访问

					node=stack.peek().rchild;

				}

			}

		}

	}

　　

20191104：前序和后序的非递归遍历还可以合理利用栈的性质来实现，与上面的稍有不同。

前序：

    public List<Integer> preorderTraversal(TreeNode root) {

        ArrayList<Integer> list = new ArrayList<Integer>();

        Stack<TreeNode> stk = new Stack<>();

        stk.push(root);

        while(!stk.isEmpty()){

            TreeNode node = stk.pop();

            if(node==null)

                continue;

            list.add(node.val);

            stk.push(node.right);

            stk.push(node.left);

        }

        return list;

    }

后序：

    public List<Integer> postorderTraversal(TreeNode root) {

        LinkedList<Integer> list = new LinkedList<Integer>();

        Stack<TreeNode> stk = new Stack<>();

        stk.push(root);

        while(!stk.isEmpty()){

            TreeNode node = stk.pop();

            if(node==null)

                continue;

            list.addFirst(node.val);  //LinkedList's method. If using ArrayList here,then using 'Collections.reverse(list)'' in the end;

            stk.push(node.left);

            stk.push(node.right);

        }

        return list;

    }

　　

层序遍历

　　合理利用队列的性质即可。

	public void levelOrder() {

		BiTNode<E> node =root;

		LinkedList<BiTNode<E>> list = new LinkedList<>();

		list.add(node);

		while(!list.isEmpty()) {

			node=list.poll();

			System.out.print(node.data);

			if(node.lchild!=null)

				list.offer(node.lchild);

			if(node.rchild!=null)

				list.offer(node.rchild);

		}

	}

　　

完整代码（含测试代码）

package BiTree;

import java.util.LinkedList;

import java.util.Stack;

class BiTNode<E>{

	E data;

	BiTNode<E> lchild,rchild;

	public BiTNode(E data) {

		this.data=data;

		this.lchild=null;

		this.rchild=null;

	}

}

public class BiTree<E> {

	private BiTNode<E> root;

	public BiTree() {

		//root=new BiTNode(null, null, null);

		root=null;

	}

	/*

	 * 前序遍历

	 */

	public void preOrder() {

		preOrderTraverse(root);

		System.out.println();

	}

	private void preOrderTraverse(BiTNode<E> node) {

		if(node==null)

			return;

		System.out.print(node.data);

		preOrderTraverse(node.lchild);

		preOrderTraverse(node.rchild);

	}

	/*

	 * 中序遍历

	 */

	public void inOrder() {

		inOrderTraverse(root);

		System.out.println();

	}

	private void inOrderTraverse(BiTNode<E> node) {

		if(node==null)

			return;

		inOrderTraverse(node.lchild);

		System.out.print(node.data);

		inOrderTraverse(node.rchild);

	}

	/*

	 * 后序遍历

	 */

	public void postOrder() {

		postOrderTraverse(root);

		System.out.println();

	}

	private void postOrderTraverse(BiTNode<E> node) {

		if(node==null)

			return;

		postOrderTraverse(node.lchild);

		postOrderTraverse(node.rchild);

		System.out.print(node.data);

	}

	//===============循环遍历===============

	/**

	 * 前序遍历（非递归）

	 */

	public void preOrder2() {

		preOrder2(root);

		System.out.println();

	}

	private void preOrder2(BiTNode node) {

		Stack<BiTNode> stack = new Stack<BiTNode>();

		while(node!=null||!stack.isEmpty()) {

			while(node!=null) {

				System.out.print(node.data);

				stack.push(node);

				node=node.lchild;

			}

			node=stack.pop().rchild;

		}

	}

	/**

	 * 中序遍历

	 */

	public void inOrder2() {

		inOrder2(root);

		System.out.println();

	}

	private void inOrder2(BiTNode node) {

		Stack<BiTNode> stack = new Stack<BiTNode>();

		while(node!=null||!stack.isEmpty()) {

			while(node!=null) {

				stack.push(node);

				node=node.lchild;

			}

			node=stack.pop();

			System.out.print(node.data);

			node=node.rchild;

		}

	}

	/**

	 * 后序遍历

	 */

	public void postOrder2() {

		postOrder2(root);

		System.out.println();

	}

	private void postOrder2(BiTNode node) {

		Stack<BiTNode> stack = new Stack<BiTNode>();

		Stack<Integer> tag = new Stack<Integer>();

//		while(node!=null||!stack.isEmpty()) {

//			while(node!=null){

//				stack.push(node);

//				tag.push(0);

//				node=node.lchild;

//			}

			//这里的tag用于标记当前结点是否完成左右子结点遍历（所以用0，1表示）

//			while(!tag.isEmpty()&&tag.peek()==1) {  //栈顶节点的左右子结点已完成遍历

//				System.out.print(stack.pop().data);

//				tag.pop();

//			}

//			if(!tag.isEmpty()) {   //上面和这里的 !flag.isEmpty() 不可省略，不然会出错。

//				tag.pop();

//				tag.push(1);

//				node=stack.peek().rchild;

//			}

//		}

		/*后序遍历时，分别从左子树和右子树共两次返回根结点（用tag表示次数），

		 * 只有从右子树返回时才访问根结点，所以增加一个栈标记到达结点的次序。

		 */

		while(node!=null||!stack.isEmpty()) {

			if(node!=null){

				stack.push(node);

				tag.push(1);  //第一次访问

				node=node.lchild;

			}else {

				if(tag.peek()==2) {

					System.out.print(stack.pop().data);

					tag.pop();

				}else {

					tag.pop();

					tag.push(2); //第二次访问

					node=stack.peek().rchild;

				}

			}

		}

	}

	//=========层序遍历============

	public void levelOrder() {

		BiTNode<E> node =root;

		LinkedList<BiTNode<E>> list = new LinkedList<>();

		list.add(node);

		while(!list.isEmpty()) {

			node=list.poll();

			System.out.print(node.data);

			if(node.lchild!=null)

				list.offer(node.lchild);

			if(node.rchild!=null)

				list.offer(node.rchild);

		}

	}

	public static void main(String[] args) {

		BiTree<String> aBiTree = new BiTree<String>();

		aBiTree.root=new BiTNode<String>("A");

		aBiTree.root.lchild=new BiTNode<String>("B");

		aBiTree.root.rchild=new BiTNode<String>("C");

		aBiTree.root.lchild.rchild=new BiTNode<String>("D");

//		BiTree<String> aBiTree = new BiTree<String>();

//		aBiTree.root=new BiTNode("A");

//		aBiTree.root.lchild=new BiTNode("B");

//		aBiTree.root.lchild.lchild=new BiTNode("C");

//		aBiTree.root.lchild.lchild.lchild=new BiTNode("D");

//		aBiTree.root.lchild.rchild=new BiTNode("E");

//		aBiTree.root.lchild.rchild.lchild=new BiTNode("F");

//		aBiTree.root.lchild.rchild.lchild.rchild=new BiTNode("G");

//		aBiTree.root.lchild.rchild.lchild.rchild.rchild=new BiTNode("H");

		System.out.println("————前序————");

		aBiTree.preOrder();

		aBiTree.preOrder2();

		System.out.println("————中序————");

		aBiTree.inOrder();

		aBiTree.inOrder2();

		System.out.println("————后序————");

		aBiTree.postOrder();

		aBiTree.postOrder2();

		System.out.println("————层序遍历————");

		aBiTree.levelOrder();

	}

}

　

————前序————

ABDC

ABDC

————中序————

BDAC

BDAC

————后序————

DBCA

DBCA

————层序遍历————

ABCD

遍历结果

参考：常用数据结构算法：二叉树的遍历（递归和非递归）

相关文章