数据结构中有很多树的结构，其中包括二叉树、二叉搜索树、2-3树、红黑树等等。今天讲最简单的二叉树：
比较重要的相关术语
度（Degree）：一个节点拥有的子树数量就是节点的度。
叶子节点（Leaf）：度为0的节点。
深度：树中节点的最大层次
二叉树（BinaryTree）
二叉树是数据结构中一种重要的数据结构，也是树表家族最为基础的结构。
二叉树的定义：二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2i-1个结点；深度为k的二叉树至多有2k-1个结点；对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。
满二叉树和完全二叉树：
满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点。也可以这样理解，除叶子结点外的所有结点均有两个子结点。节点数达到最大值，所有叶子结点必须在同一层上。
满二叉树的性质：
一颗树深度为h，最大层数为k，深度与最大层数相同，k=h;
叶子数为2h;
第k层的结点数是：2k-1;
总结点数是：2k-1，且总节点数一定是奇数。
完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～(h-1)层) 的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树。
他们的 对应关系为一个满二叉树一定是一个完全二叉树，一个完全二叉树不一定是一个满二叉树。
二叉树的遍历
二叉树的遍历分前序遍历（DLR）、中序遍历（LDR）、后序遍历（LRD）。对于二叉树的每个节点而言，遍历都有三个对象，分别是本身、左子、右子，而所谓的前中后，指的就是本身在遍历中的位置，所以前序遍历就是先访问本身，再左右子，中序遍历就是先左子再本身再右子，后序则是先左右子再本身。
关于缩写，我是比较好奇的，D（Degree）L（left child）R（right child）查阅到的英文是这样，暂时这么记。
talk is cheap show me the code（少废话，放码过来）
定义一个二叉树
public class BTreeNode<E> {
E data;
BTreeNode<E> left;
BTreeNode<E> right;
public BTreeNode(E data, BTreeNode<E> left, BTreeNode<E> right) {
this.data = data;
this.left = left;
this.right = right;
}
}
遍历方式
/**
* 前序遍历
* */
public static <E> void dlrTraverse(BTreeNode<E> root){
if(root == null)
return;
println(root.data.toString());
dlrTraverse(root.left);
dlrTraverse(root.right);
}
/**
* 中序遍历
* */
public static <E> void ldrTraverse(BTreeNode<E> root){
if(root == null)
return;
ldrTraverse(root.left);
println(root.data.toString());
ldrTraverse(root.right);
}
/**
* 后序遍历
* */
public static <E> void lrdTraverse(BTreeNode<E> root){
if(root == null)
return;
lrdTraverse(root.left);
lrdTraverse(root.right);
println(root.data.toString());
}
本文代码块引用 怀念小兔 代码。
