首页 > 程序开发 > 软件开发 > Java >

Java数据结构系列之——树(4):二叉树的中序遍历的递归与非递归实现

2014-12-06

package tree binarytree; import java util Stack; ** * 二叉树的中序遍历:递归与非递归实现 * * @author wl * * public class BiTreeInOrder { 中序遍历的递归实现 public st

package tree.binarytree;

import java.util.Stack;

/**
 * 二叉树的中序遍历:递归与非递归实现
 * 
 * @author wl
 * 
 */
public class BiTreeInOrder {
	// 中序遍历的递归实现
	public static void biTreeInOrderByRecursion(BiTreeNode root) {
		if (root == null) {
			return;
		}

		biTreeInOrderByRecursion(root.leftNode);
		System.out.println(root.data);
		biTreeInOrderByRecursion(root.rightNode);
	}

	// 中序遍历的非递归实现
	public static void biTreeInOrder(BiTreeNode root) {
		Stack stack = new Stack();// 栈,用于存放二叉树的结点
		BiTreeNode current = root;// 当前结点

		while (current != null || !stack.empty()) {
			while (current != null) {
				stack.push(current);
				current = current.leftNode;
			}

			if (!stack.empty()) {
				current = stack.pop();
				System.out.println(current.data);
				current = current.rightNode;
			}
		}
	}
}

相关文章
最新文章
热点推荐