定义
二叉树（Binary Tree）是一个树（Tree），并且其中每个节点最多有两个子树，分别称为左子树和右子树。
如下是一个二叉树：
特殊类型
完全二叉树（Complete Binary Tree）
完全二叉树除了最下层外，其他几层的节点数都达到了最大值，并且最下层的节点都集中在左边。
如下是一个完全二叉树：
满二叉树（Full Binary Tree）
国内和国外对于满二叉树的定义有所不同：
国内定义
满二叉树的每一层节点数都达到了最大值。
如下是一个满足该定义的满二叉树：
国外定义
满二叉树中的每个节点，要么没有子树，要么有两个子树。
如下是一个满足该定义的满二叉树：
实现
通过二叉树的定义，我们发现它是由一系列的节点组合起来的，每个节点可能会有左右两个子二叉树，因此我们先定义二叉树节点和二叉树两个接口：
接口类
二叉树节点和二叉树的接口定义如下：
/**
* 二叉树接口
*
* @param <V> 存储的值类型
*/
public interface IBinaryTree<V> {
/**
* @return 根节点
*/
INode<V> getRoot();
/**
* 二叉树节点接口
*
* @param <V> 存储的值类型
*/
interface INode<V> {
/**
* @return 存储的值
*/
V getValue();
/**
* @return 左子树
*/
INode<V> getLeft();
/**
* @return 右子树
*/
INode<V> getRight();
}
}
其中，IBinaryTree 中的 getRoot 函数用来获取当前二叉树的根节点。
为了方便，我们将 INode 定义成了 IBinaryTree 的内部接口，其中的 getLeft 和 getRight 函数分别用来获取当前节点所指向的左、右子节点。
实现类
定义好接口以后，对应的实现也比较简单，只需要定义对应的字段和getter、setter函数即可：
/**
* 二叉树实现
*
* @param <V> 存储的值类型
*/
public class BinaryTree<V> implements IBinaryTree<V> {
private Node<V> root;
// 以下省略构造函数以及getter和setter
/**
* 二叉树节点实现
*
* @param <V> 存储的值类型
*/
public static class Node<V> implements INode<V> {
private V value;
private Node<V> left;
private Node<V> right;
// 以下省略构造函数以及getter和setter
}
}
类似的，为了方便，我们将 Node 类定义成了 BinaryTree 的内部类。
测试示例
下面通过一段Demo程序来测试和展示二叉树的功能：
public class Demo {
public static void main(String[] args) {
System.out.println("初始化一个空二叉树：");
BinaryTree<Character> tree = new BinaryTree<>();
PrintUtil.print(tree);
BinaryTree.Node<Character> a = new BinaryTree.Node<>('A');
BinaryTree.Node<Character> b = new BinaryTree.Node<>('B');
BinaryTree.Node<Character> c = new BinaryTree.Node<>('C');
BinaryTree.Node<Character> d = new BinaryTree.Node<>('D');
BinaryTree.Node<Character> e = new BinaryTree.Node<>('E');
BinaryTree.Node<Character> f = new BinaryTree.Node<>('F');
BinaryTree.Node<Character> g = new BinaryTree.Node<>('G');
BinaryTree.Node<Character> h = new BinaryTree.Node<>('H');
System.out.println("将A设置为二叉树的根节点：");
tree.setRoot(a);
PrintUtil.print(tree);
System.out.println("将B、C分别设置为A的左、右子节点，将D、E分别设置为B的左、右子节点：");
a.setLeft(b);
a.setRight(c);
b.setLeft(d);
b.setRight(e);
PrintUtil.print(tree);
System.out.println("将F设置为C的左子节点，将G、H分别设置为F的左、右子节点：");
c.setLeft(f);
f.setLeft(g);
f.setRight(h);
PrintUtil.print(tree);
}
}
上面代码中通过前面实现的函数分步构建出了一个二叉树，并通过工具类中的方法 PrintUtil.print 将每一步的二叉树打印出来，最终输出的结果如下：
