一、二叉树的定义
在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。
二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^{i-1}个结点；深度为k的二叉树至多有2^k-1个结点；对任何一棵二叉树T，如果其终端结点数为n_0，度为2的结点数为n_2，则n_0=n_2 1。
一棵深度为k，且有2^k-1个节点称之为满二叉树；深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时，称之为完全二叉树。
二、二叉树的实现
本篇文章主要讲一下二叉树的实现，以及遍历方法（递归与非递归）包括前序、中序、后序。
1、节点类Node
这边我其实用一个内部类简单实现了一下二叉树的节点定义。
代码语言：javascript复制private class BinaryTreeNode {
private BinaryTreeNode left = null; //左节点
private BinaryTreeNode right = null; //右节点
private String data;
private int key;
public BinaryTreeNode(int key, String data) {
this.data = data;
this.left = null;
this.right = null;
}
public String getData() {
return data;
}
public void setData(String data) {
this.data = data;
}
public BinaryTreeNode getLeft() {
return left;
}
public void setLeft(BinaryTreeNode left) {
this.left = left;
}
public BinaryTreeNode getRight() {
return right;
}
public void setRight(BinaryTreeNode right) {
this.right = right;
}
}2、创建二叉树
代码语言：javascript复制 public void createTree() {
//自己创建节点，用于组成二叉树
BinaryTreeNode newNodeB = new BinaryTreeNode(2, "B");
BinaryTreeNode newNodeC = new BinaryTreeNode(3, "C");
BinaryTreeNode newNodeD = new BinaryTreeNode(4, "D");
BinaryTreeNode newNodeE = new BinaryTreeNode(5, "E");
BinaryTreeNode newNodeF = new BinaryTreeNode(6, "F");
BinaryTreeNode newNodeG = new BinaryTreeNode(7, "G");
BinaryTreeNode newNodeH = new BinaryTreeNode(8, "H");
BinaryTreeNode nodes[] = { root, newNodeB, newNodeC, newNodeD,
newNodeE, newNodeF, newNodeG, newNodeH };
//这是根据二叉树的定义，第i个节点的子节点为i * 2 1和i * 2 2
for (int i = 0; i < nodes.length / 2 - 1; i ) {
nodes[i].setLeft(nodes[i * 2 1]);
nodes[i].setRight(nodes[i * 2 2]);
}
//最后一个节点需要单独考虑，因为如果节点总数为奇数那么最后一个为右子节点，反正偶数为左子节点
int lastIndex = nodes.length / 2 - 1;
if (nodes.length % 2 == 1) {
nodes[lastIndex].setRight(nodes[lastIndex * 2 2]);
} else {
nodes[lastIndex].setLeft(nodes[lastIndex * 2 1]);
}
}3、递归遍历算法
3.1 前序
代码语言：javascript复制 // 递归遍历 前序
public void preOrder(BinaryTreeNode node) {
if (node == null)
return;
System.out.print(node.getData());
preOrder(node.getRight());
preOrder(node.getLeft());
}3.2 中序
代码语言：javascript复制 // 递归遍历 中序
public void inOrder(BinaryTreeNode node) {
if (node != null) {
inOrder(node.getLeft());
System.out.print(node.getData());
inOrder(node.getRight());
}
}3.3 后序
代码语言：javascript复制 // 递归遍历 后序
public void backOrder(BinaryTreeNode node) {
if (node != null) {
backOrder(node.getLeft());
backOrder(node.getRight());
System.out.print(node.getData());
}
}其实从上面的三个方法，大家可以看到，就是三句话换个顺序。换句话说就是打印的那句话换位置：前序放前面，中序放中间，后序放后面。
4、非递归遍历算法
4.1 前序
代码语言：javascript复制 // 非递归遍历 前序
public void preorderNoRec(BinaryTreeNode node) {
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
BinaryTreeNode tempNode = node;
while (tempNode != null || stack.size() > 0) {
while (tempNode != null) {
System.out.print(tempNode.getData());
stack.push(tempNode);
tempNode = tempNode.getLeft();
}
if (stack.size() > 0) {
tempNode = stack.pop();
tempNode = tempNode.getRight();
}
}
}从根节点开始，然后把左子树放入stack，同时打印出顺序。然后再查找右子树。
4.2 中序
代码语言：javascript复制 // 非递归遍历 中序
public void inOrderNoRec(BinaryTreeNode node) {
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
BinaryTreeNode tempNode = node;
while (tempNode != null || stack.size() > 0) {
while (tempNode != null) {
stack.push(tempNode);
tempNode = tempNode.getLeft();
}
if (stack.size() > 0) {
tempNode = stack.pop();
System.out.print(tempNode.getData());
tempNode = tempNode.getRight();
}
}
}这个和前序的区别就在于利用了Stack后进先出的特性。后入栈的左子树先打印再到根节点，最后右子树。
4.3 后序
代码语言：javascript复制 // 非递归遍历 后序
public void backOrderNoRec(BinaryTreeNode node) {
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
BinaryTreeNode tempNode = node;
while (node != null) {
for (; node.getLeft() != null; node = node.getLeft())
stack.push(node);
while (node != null
&& (node.getRight() == null || node.getRight() == tempNode)) {
System.out.print(node.getData());
tempNode = node;
if (stack.empty())
return;
node = stack.pop();
}
stack.push(node);
node = node.getRight();
}
}后序和前两个区别比较多，先把左子树放入stack，通过判断是否含有右子树，含有就先打印左子节点，再放入stack，打印其右节点。其实最后就形成了先把节点的子节点都打印在打印父节点。而根节点是最终的父节点，所以根节点最后打印。
5、打印结果
代码语言：javascript复制 public static void main(String[] args) {
BinaryTree test = new BinaryTree();
test.createTree();
System.out.println("*******前序递归********");
test.preOrder(test.root);
System.out.println();
System.out.println("*******前序非递归********");
test.preorderNoRec(test.root);
System.out.println();
System.out.println("*******中序递归********");
test.inOrder(test.root);
System.out.println();
System.out.println("*******中序非递归********");
test.inOrderNoRec(test.root);
System.out.println();
System.out.println("*******后序递归********");
test.backOrder(test.root);
System.out.println();
System.out.println("*******后序非递归********");
test.backOrderNoRec(test.root);
}结果显示：
代码语言：javascript复制*******前序递归********
(root)ACGFBEDH
*******前序非递归********
(root)ABDHECFG
*******中序递归********
HDBE(root)AFCG
*******中序非递归********
HDBE(root)AFCG
*******后序递归********
HDEBFGC(root)A
*******后序非递归********
HDEBFGC(root)A
