使用 Java 遍历二叉树

在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有个结点；深度为k的二叉树至多有个结点；对任何一棵二叉树T，如果其终端结点数为，度为2的结点数为，则。

树和二叉树的三个主要差别：

1. 树的结点个数至少为1，而二叉树的结点个数可以为0；
2. 树中结点的最大度数没有限制，而二叉树结点的最大度数为2；
3. 树的结点无左、右之分，而二叉树的结点有左、右之分。

<完全二叉树和满二叉树>

1. 满二叉树：一棵深度为k，且有（2的k次方）－1个节点成为满二叉树
2. 完全二叉树：深度为k，有n个节点的二叉树，当且仅当其每一个节点都深度为k的满二叉树，称之为完全二叉树

满二叉结构：

                                                            00001

                           00010                                                             00011

           00100                            00101                        00102                         00103  

   01000       01001       01002       01003       01004       01005       01006       01007

TreeBean:

public class TreeBean {
	private String treeName;
	private TreeBean leftTree;
	private TreeBean rightTree;

	public TreeBean() {
		super();
	}

	public TreeBean(TreeBean leftTree, TreeBean rightTree, String treeName) {
		super();
		this.leftTree = leftTree;
		this.rightTree = rightTree;
		this.treeName = treeName;
	}

	public String getTreeName() {
		return treeName;
	}

	public void setTreeName(String treeName) {
		this.treeName = treeName;
	}

	public TreeBean getLeftTree() {
		return leftTree;
	}

	public void setLeftTree(TreeBean leftTree) {
		this.leftTree = leftTree;
	}

	public TreeBean getRightTree() {
		return rightTree;
	}

	public void setRightTree(TreeBean rightTree) {
		this.rightTree = rightTree;
	}

}

 

Main:

public class Test {
	public TreeBean initTree(int level) {
		TreeBean tb01000 = new TreeBean(null, null, "01000");
		TreeBean tb01001 = new TreeBean(null, null, "01001");
		TreeBean tb01002 = new TreeBean(null, null, "01002");
		TreeBean tb01003 = new TreeBean(null, null, "01003");
		TreeBean tb01004 = new TreeBean(null, null, "01004");
		TreeBean tb01005 = new TreeBean(null, null, "01005");
		TreeBean tb01006 = new TreeBean(null, null, "01006");
		TreeBean tb01007 = new TreeBean(null, null, "01007");
		TreeBean tb00100 = new TreeBean(tb01000, tb01001, "00100");
		TreeBean tb00101 = new TreeBean(tb01002, tb01003, "00101");
		TreeBean tb00102 = new TreeBean(tb01004, tb01005, "00102");
		TreeBean tb00103 = new TreeBean(tb01006, tb01007, "00103");
		TreeBean tb00011 = new TreeBean(tb00102, tb00103, "00011");
		TreeBean tb00010 = new TreeBean(tb00100, tb00101, "00010");
		TreeBean tb00001 = new TreeBean(tb00010, tb00011, "00001");
		return tb00001;
	}

	//递归便利
	public void printAllTreeForRecursion(TreeBean tb) {
		if (tb != null) {
			System.out.println(tb.getTreeName());
			printAllTreeForRecursion(tb.getLeftTree());
			printAllTreeForRecursion(tb.getRightTree());
		}
	}

	//堆栈遍历
	public void printAllTreeForStack(TreeBean tb) {
		Stack<TreeBean> tbs = new Stack<TreeBean>();
		if (tbs != null) {
			tbs.push(tb);
			while (!tbs.isEmpty()) {
				tb = tbs.pop();
				System.out.println(tb.getTreeName());
				if (tb.getLeftTree() != null) {
					tbs.push(tb.getLeftTree());
				}
				if (tb.getRightTree() != null) {
					tbs.push(tb.getRightTree());
				}
			}
		}
	}

	public static void main(String[] args) {
		Test t = new Test();
		TreeBean tb = t.initTree(1);
		t.printAllTreeForRecursion(tb);
		t.printAllTreeForStack(tb);
	}
}

  

借鉴：http://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E6%A0%91