二叉树遍历Java之美[从菜鸟到高手演变]之数据结构基础之树、二叉树

时间紧张，先记一笔，后续优化与完善。

Java口试宝典之二叉树的实现

作者：egg

邮箱：xtfggef@gmail.com

微博：http://weibo.com/xtfggef

客博：http://blog.csdn.net/zhangerqing（转载请明说出处）

我们接着上一篇数据构结继承讲授。本章系数据构结之树与二叉树，从这章开始，我们就要分析非线性构结了，这些内容懂得起来比线性表稍难一些，我尽量写的艰深一些，如果读的程过中有任何问题，请按上述方法联系我！

一、树

树形构结是一类要重的非线性构结。树形构结是点结之间有分支，并有具层次关系的构结。它非常类似于自然界中的树。树构结在客观界世中是量大存在的，例如家谱、行政组织机构都可用树形象地示表。树在计算机领域中也有着泛广的应用，例如在编译程序中，用树来示表源程序的语法构结；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来述描其行执程过。本章重点论讨二叉树的存储示表及其各种运算，并究研一般树和丛林与二叉树的转换关系，最后分析树的应用实例。

二、二叉树

二叉树(BinaryTree)是n(n≥0)个点结的无限集，它或者是空集(n=0)，或者由一个根点结及两棵互不订交的、别分称作这个根的左子树和右子树的二叉树成组。关于更多念概，请大家自己上彀询查，我们这里将用代码实现见常的算法。更多的念概，请拜访：http://student.zjzk.cn/course_ware/data_structure/web/SHU/shu6.2.3.1.htm 。

1、二叉树的建立

首先，我们用采狭义表建立二叉树（关于狭义表的念概，请看查百科的分析：http://baike.baidu.com/view/203611.htm）

我们建立一个字符串型类的狭义表作为输入：

String expression = "A(B(D(,G)),C(E,F))";与该狭义表对应的二叉树为：

写代码前，我们通过视察二叉树和狭义表，先得出一些论结：

每当碰到字母，将要建创节点
每当碰到“（”，表面要建创左孩子节点
每当碰到“，”，明表要建创又孩子节点
每当碰到“）”，明表要回返上一层节点
狭义表中“（”的数量正好是二叉树的层数

根据这些论结，我们基本就能够开始写代码了。首先议建一个节点类（这也属于一种自定义的数据构结）。

package com.xtfggef.algo.tree;

public class Node {

	private char data;
	private Node lchild;
	private Node rchild;

	public Node(){
		
	}
	public char getData() {
		return data;
	}

	public void setData(char data) {
		this.data = data;
	}

	public Node getRchild() {
		return rchild;
	}

	public void setRchild(Node rchild) {
		this.rchild = rchild;
	}

	public Node getLchild() {
		return lchild;
	}

	public void setLchild(Node lchild) {
		this.lchild = lchild;
	}

	public Node(char ch, Node rchild, Node lchild) {
		this.data = ch;
		this.rchild = rchild;
		this.lchild = lchild;
	}

	public String toString() {
		return "" + getData();
	}
}

根据狭义表建创二叉树的代码如下：

public Node createTree(String exp) {
		Node[] nodes = new Node[3];
		Node b, p = null;
		int top = -1, k = 0, j = 0;
		char[] exps = exp.toCharArray();
		char data = exps[j];
		b = null;
		while (j < exps.length - 1) {
			switch (data) {
			case '(':
				top++;
				nodes[top] = p;
				k = 1;
				break;
			case ')':
				top--;
				break;
			case ',':
				k = 2;
				break;
			default:
				p = new Node(data, null, null);
				if (b == null) {
					b = p;
				} else {
					switch (k) {
					case 1:
						nodes[top].setLchild(p);
						break;
					case 2:
						nodes[top].setRchild(p);
						break;
					}
				}
			}
			j++;
			data = exps[j];
		}
		return b;
	}

思绪不难，合结上述的理论，自己断点走一遍程序就懂了！

2、二叉树的递归遍历

二叉树的遍历有三种：先序、序中、后序，每种又分递归和非递归。递归程序懂得起来有定一的难度，但是实现起来比较简单。对于上述二叉树，其：

每日一道理
这浓浓的母爱使我深深地认识到：即使你是一只矫健的雄鹰，也永远飞不出母爱的长空；即使你是一条扬帆行驶的快船，也永远驶不出母爱的长河！在人生的路上不管我们已走过多远，还要走多远，我们都要经过母亲精心营造的那座桥！

a 先序遍历

A B D G C E F

b 序中遍历

D G B A E C F

c 后序遍历

G D B E F C A

先、中、后序递归遍历如下：

/**
	 * pre order recursive
	 * 
	 * @param node
	 */
	public void PreOrder(Node node) {
		if (node == null) {
			return;
		} else {
			System.out.print(node.getData() + " ");
			PreOrder(node.getLchild());
			PreOrder(node.getRchild());

		}
	}

	/**
	 * in order recursive
	 * 
	 * @param node
	 */
	public void InOrder(Node node) {
		if (node == null) {
			return;
		} else {
			InOrder(node.getLchild());
			System.out.print(node.getData() + " ");
			InOrder(node.getRchild());
		}
	}

	/**
	 * post order recursive
	 * 
	 * @param node
	 */
	public void PostOrder(Node node) {
		if (node == null) {
			return;
		} else {
			PostOrder(node.getLchild());
			PostOrder(node.getRchild());
			System.out.print(node.getData() + " ");
		}
	}

二叉树的递归遍历实现起来很简单，症结长短递归遍历有些难度，请看上面的代码：

3、二叉树的非递归遍历

先序非递归遍历：

public void PreOrderNoRecursive(Node node) {
		Node nodes[] = new Node[CAPACITY];
		Node p = null;
		int top = -1;
		if (node != null) {
			top++;
			nodes[top] = node;
			while (top > -1) {
				p = nodes[top];
				top--;
				System.out.print(p.getData() + " ");
				if (p.getRchild() != null) {
					top++;
					nodes[top] = p.getRchild();
				}
				if (p.getLchild() != null) {
					top++;
					nodes[top] = p.getLchild();
				}
			}
		}
	}

道理：利用一个栈，先序遍历即为根先遍历，先将根入栈，然后出栈，是凡出栈的素元都印打值，入栈之前top++，出栈后之top--，利用栈后进先出的道理，右节点先于左节点进栈，根出栈后，开始处置左子树，然后是右子树，读者朋友们可以自己走一遍程序看看，也不算难懂得！

序中非递归遍历：

public void InOrderNoRecursive(Node node) {
		Node nodes[] = new Node[CAPACITY];
		Node p = null;
		int top = -1;
		if (node != null)
			p = node;
		while (p != null || top > -1) {
			while (p != null) {
				top++;
				nodes[top] = p;
				p = p.getLchild();
			}
			if (top > -1) {
				p = nodes[top];
				top--;
				System.out.print(p.getData() + " ");
				p = p.getRchild();
			}
		}
	}

道理略省。

后续非递归遍历：

public void PostOrderNoRecursive(Node node) {
		Node[] nodes = new Node[CAPACITY];
		Node p = null;
		int flag = 0, top = -1;
		if (node != null) {
			do {
				while (node != null) {
					top++;
					nodes[top] = node;
					node = node.getLchild();
				}
				p = null;
				flag = 1;
				while (top != -1 && flag != 0) {
					node = nodes[top];
					if (node.getRchild() == p) {
						System.out.print(node.getData() + " ");
						top--;
						p = node;
					} else {
						node = node.getRchild();
						flag = 0;
					}
				}
			} while (top != -1);
		}
	}

三、树与二叉树的转换

本人之前总结的：

这分部念概的其他识知，请读者自己上彀看查。

作者：egg

邮箱：xtfggef@gmail.com

微博：http://weibo.com/xtfggef

客博：http://blog.csdn.net/zhangerqing（转载请明说出处）

文章结束给大家分享下程序员的一些笑话语录：腾讯的动作好快，2010年3月5日19时28分58秒，QQ同时在线人数1亿！刚刚看到编辑发布的文章，相差才2分钟，然后连专题页面都做出来了，他们早就预料到了吧？（其实，每人赠送10Q币，轻轻松松上两亿！）