参考：http://blog.csdn.net/zhangerqing/article/details/8822476
前面已经提到过树和二叉树的相关概念内容，下面主要来介绍下关于二叉树的创建，遍历，查找等相关内容。在此之间先说一个概念，广义表
一、广义表
广义表是一种非线性的数据结构，广义表是n个数据元素d1，d2，d3，…，dn的有限序列，但线性表不同的是，广义表中的di 则既可以是单个元素，还可以是一个广义表，通
常记作：GL=（d1，d2，d3，…，dn）。GL是广义表的名字，通常广义表的名字用大写字母表示。n是广义表的长度。若其中di是一个广义表，则称di是广义表GL的子表。在
广义表GL中，d1是广义表GL的表头，而广义表GL其余部分组成的表（d2，d3，…，dn）称为广义表的表尾。由此可见广义表的定义是递归定义的。
二、创建二叉树
采用广义表的方式创建二叉树。创建的二叉树结构如下：
1 定义Node节点
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();
}
}2. 二叉树创建类
Node createTree(String express, char split){
String[] array = StringUtils.split(express, split);
int length = array.length-1;
int capicity = (1<<(length-1))-1;
Node[] nodes = new Node[capicity];
Node head =null;
Node p = null;
int level = -1;
int childType = 0;
int index =0;
char data;
char[] charArray = express.toCharArray();
while(index < charArray.length-1){
data = charArray[index];
switch(data){
case '(':
level++;
childType = 1;
nodes[level]=p;
break;
case ',':
childType = 2;
break;
case ')':
level--;
break;
default:
p = new Node(data, null, null);
if(head == null){
head = p;
break;
}else{
switch(childType){
case 1: nodes[level].setLchild(p);break;
case 2: nodes[level].setRchild(p);break;
}
}
}
data = charArray[++index];
}
return head;
}
三、二叉树的遍历
1. 先序遍历
此种遍历模式是先读取父节点，然后再读取左右节点。
1.1 递归先序遍历
/**
* 递归先序遍历
* @param node
*/
public void preTraversal(Node node){
if(null == node){
return;
}else{
System.out.print(node.getData()+" ");
preTraversal(node.getLchild());
preTraversal(node.getRchild());
}
}
1.2 非递归先序遍历
/**
* 非递归先序遍历
* @param node
*/
public void preTraversalNoRecursive(Node node){
if(null == node){
return;
}
Node p = null;
int level=0;
Node[] stack = new Node[1024];
stack[0] = node;//先将树根节点压入栈中
while(level > -1){
p = stack[level];
level--;//移除栈的顶层节点
System.out.print(p.getData()+" ");
if(null != p.getRchild()){//如果树右子节点不为null，则压入栈中
stack[++level] = p.getRchild();
}
if(null != p.getLchild()){//如果树左子节点不为Null,则压入栈中
stack[++level] = p.getLchild();
}
}
}
2. 中序遍历
此种遍历模式是先读取左子节点，然后读取父节点，最后读取右节点。
2.1 递归中序遍历
<span style="white-space:pre"> </span>/**
* 递归中序遍历
* @param node
*/
public void midTraversal(Node node){
if(null == node){
return;
}else{
midTraversal(node.getLchild());
System.out.print(node.getData()+" ");
midTraversal(node.getRchild());
}
}
2.2 非递归中序遍历
/**
* 非递归中序遍历
* @param node
*/
public void midTraversalNoRecursive(Node node){
if(null == node){
return;
}
int level = -1;
Node[] stack = new Node[1024];
Node p = node;
while(p != null || level > -1){//节点不为null或则当前层数不为-1
while(p != null){
stack[++level] = p;//将p压入栈
p = p.getLchild();//获取p的左子结点
}
if(level > -1){
p = stack[level];//获取栈顶层节点
level--;
System.out.print(p.getData()+" ");
p = p.getRchild();//读取为最下方的左子节点，接着访问该节点的右子节点
}
}
}3. 后序遍历
此种遍历模式是先读取左右节点，然后再读取父节点。
3.1 递归后序遍历
<span style="white-space:pre"> </span>/**
* 递归后序遍历
* @param node
*/
public void lastTraversal(Node node){
if(null == node){
return;
}else{
lastTraversal(node.getLchild());
lastTraversal(node.getRchild());
System.out.print(node.getData()+" ");
}
}4. 二叉树的深度遍历
待补充
5. 二叉树的广度遍历
待补充