【本文详细介绍了 JAVA 应用开发中的 二叉树 ，欢迎读者朋友们阅读、转发和收藏！】

1 基本概念

1.1 二叉树的定义

二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。

二叉树 (BinaryTree) 是 n(n ≥ 0) 个结点的有限集，它或者是 空集 (n=0) ，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。

这个定义是递归的。由于左、右子树也是二叉树， 因此子树也可为空树。下图中展现了五种不同基本形态的二叉树。

其中 (a) 为空树， (b) 为仅有一个结点的二叉树， (c) 是仅有左子树而右子树为空的二叉树， (d) 是仅有右子树而左子树为空的二叉树， (e) 是左、右子树均非空的二叉树。这里应特别注意的是，二叉树的左子树和右子树是严格区分并且不能随意颠倒的，图 (c) 与图 (d) 就是两棵不同的二叉树。

1.2 二叉 树的遍历

对于二叉树来讲最主要、最基本的运算是遍历。

遍历二叉树 是指以一定的次序访问二叉树中的每个结点。所谓 访问结点 是指对结点进行各种操作的简称。例如，查询结点数据域的内容，或输出它的值，或找出结点位置，或是执行对结点的其他操作。遍历二叉树的过程实质是把二叉树的结点进行线性排列的过程。假设遍历二叉树时访问结点的操作就是输出结点数据域的值，那么遍历的结果得到一个线性序列。

1.3 二叉树有 3 种遍历方式 :

1, 前序遍历 :

首先访问根，再先序遍历左（右）子树，最后先序遍历右（左）子树

2, 中序遍历 :

首先中序遍历左（右）子树，再访问根，最后中序遍历右（左）子树

3, 后序遍历 :

首先后序遍历左（右）子树，再后序遍历右（左）子树，最后访问根

2 二叉树的 java 实现

首先创建一棵二叉树如下图，然后对这棵叉树进行遍历操作（遍历操作的实现分为递归实现和非递归实现），同时还提供一些方法如获取双亲结点、获取左孩子、右孩子等。

 import java.util.Stack;
/**
* 二叉树的链式存储
*/public class BinaryTree {

private TreeNode root=null;
public BinaryTree(){
root=new TreeNode(1,"rootNode(A)");
}

/**
* 创建一棵二叉树
* <pre>
* A
* B C
* D E F
* </pre>
* @param root
* @author WWX
*/public void createBinTree(TreeNode root){
TreeNode newNodeB = new TreeNode(2,"B");
TreeNode newNodeC = new TreeNode(3,"C");
TreeNode newNodeD = new TreeNode(4,"D");
TreeNode newNodeE = new TreeNode(5,"E");
TreeNode newNodeF = new TreeNode(6,"F");
root.leftChild=newNodeB;
root.rightChild=newNodeC;
root.leftChild.leftChild=newNodeD;
root.leftChild.rightChild=newNodeE;
root.rightChild.rightChild=newNodeF;
}

public boolean isEmpty(){
return root==null;
}
// 树的高度
public int height(){
return height(root);
}

// 节点个数
public int size(){
return size(root);
}

private int height(TreeNode subTree){
if(subTree==null)
return 0;// 递归结束：空树高度为 0
else{
int i=height(subTree.leftChild);
int j=height(subTree.rightChild);
return (i<j)?(j+1):(i+1);
}
}

private int size(TreeNode subTree){
if(subTree==null){
return 0;
}else{
return 1+size(subTree.leftChild)+size(subTree.rightChild);
}
}