非递归方式遍历两叉树

//A1.java

import java.util.Stack;

public class A1 {

	public static void main(String[] args) {

		TreeNode root = new TreeNode(1, new TreeNode(2, new TreeNode(3), new TreeNode(4)), new TreeNode(5));
		Tree t = new Tree(root);
		exec(t);
	}

	// 前序遍历
	public static void exec(Tree tree) {

		TreeNode p = tree.root;
		Stack<TreeNode> s = new Stack<TreeNode>();

		while (p != null) {
			System.out.println(p.data);
			s.push(p);

			if (p.left != null) {
				p = p.left;
			} else {
				while (!s.empty()) {
					p = s.pop();
					p = p.right;
					if (p != null) {
						break;
					}
				}
			}
		}
	}
}

// 定义树
class Tree {

	TreeNode root = null;

	public Tree(TreeNode tr) {
		root = tr;
	}

	public Tree() {

	}
}

// 定义节点
class TreeNode {

	int data;
	TreeNode left = null;
	TreeNode right = null;

	public TreeNode() {

	}

	public TreeNode(int d) {
		data = d;
	}

	public TreeNode(int d, TreeNode l, TreeNode r) {
		data = d;
		left = l;
		right = r;
	}
}

 

运行结果：

 

1
2
3
4
5