在实现之前我们首先对二叉树进行一些说明，二叉树中大部分操作的运行时间平绝为O(log N)。从节点n1到nk的路径定义为节点n1, n2, ..., nk的一个序列，使得对于1<=i<=k节点ni是n(i+1)的父亲。这条路径的长是为该路径上的边的条数，即k-1。从每一个节点到它自己有一条长为0的路径。注意：在一棵树中从根到每个节点恰好存在一条路径。对任意节点ni，ni的深度为从根到ni的唯一路径的长。因此，根的深度为0。ni的高是从ni到一片树叶的最长路径的长。因此所有的树叶高度都是0。一棵树的高等于它的根的高。一棵树的深度等于它的最深的树叶的深度，该深度总是等于这棵树的高。下面我们看相关实现。
一、查找二叉树
package cn.list;
import java.util.LinkedList;
import java.util.Queue;
//查找二叉树实现
public class MySearchBinaryTree<T extends Comparable<? super T>> {
private static class BinaryNode<T> {
T element;
BinaryNode<T> left;
BinaryNode<T> right;
BinaryNode(T element) {
this(element, null, null);
}
BinaryNode(T element, BinaryNode<T> left, BinaryNode<T> right) {
this.element = element;
this.left = left;
this.right = right;
}
}
private BinaryNode<T> root;
// 初始状态下根节点是空
public MySearchBinaryTree() {
root = null;
}
// 清空树
public void makeEmpty() {
root = null;
}
public boolean isEmpty() {
return root == null;
}
// 查看是否包含，或者将搜索方法
public boolean contains(T x) {
return contains(x, root);
}
// 获取最小元素
public T findMin() {
if (isEmpty()) {
System.out.println("Empty tree");
throw new RuntimeException();
}
return findMin(root).element;
}
// 获取最大元素
public T findMax() {
if (isEmpty()) {
System.out.println("Empty tree");
throw new RuntimeException();
}
return findMax(root).element;
}
// 插入
public void insert(T x) {
root = insert(x, root);
}
// 删除
public void remove(T x) {
root = remove(x, root);
}
// 打印
public void printTree() {
if (isEmpty()) {
System.out.println("Empty tree");
} else {
printTree(root);
}
}
// 取得树中元素个数
public int size() {
return (size(root));
}
private int size(BinaryNode node) {
if (node == null)
return 0;
else {
return (size(node.left) + 1 + size(node.right));
}
}
//取得树的深度
public int maxDepth() {
return (maxDepth(root));
}
private int maxDepth(BinaryNode node) {
if (node == null) {
return 0;
} else {
int lDepth = maxDepth(node.left);
int rDepth = maxDepth(node.right);
return (Math.max(lDepth, rDepth) + 1);
}
}
//树的深度
private int height(BinaryNode<T> t){
if(t == null){
return -1;
}else{
return 1 + Math.max(height(t.left), height(t.right));
}
}
//中序遍历打印树
private void printTree(BinaryNode<T> t) {
if (t != null) {
printTree(t.left);
System.out.println(t.element);
printTree(t.right);
}
}
//先序遍历打印
private void prePrint(BinaryNode<T> t) {
if (t != null) {
System.out.print(t.element + "-");
prePrint(t.left);
prePrint(t.right);
}
}
//后序遍历打印
private void postPrint(BinaryNode<T> t) {
if (t != null) {
postPrint(t.left);
postPrint(t.right);
System.out.print(t.element + "---");
}
}
//层序遍历
public void levelTraverse(MySearchBinaryTree<T> tree){
levelTraverse(tree.root);
}
private void levelTraverse(BinaryNode<T> root){
if(root == null){
return;
}
Queue<BinaryNode<T>> queue = new LinkedList<BinaryNode<T>>();//层序遍历时保存结点的队列
queue.offer(root);//初始化
while(!queue.isEmpty()){
BinaryNode<T> node = queue.poll();
System.out.print(node.element + " ");//访问节点
if(node.left != null)
queue.offer(node.left);
if(node.right != null)
queue.offer(node.right);
}
}
// 这个函数很简单，就是进行比较，如果小，则往左子树遍历，如果大，则往
// 右子树遍历，直到找到为止
private boolean contains(T x, BinaryNode<T> t) {
if (t == null) {
return false;
}
int compareResult = x.compareTo(t.element);
if (compareResult < 0) {
return contains(x, t.left);
} else if (compareResult > 0) {
return contains(x, t.right);
} else {
return true;
}
}
private BinaryNode<T> findMin(BinaryNode<T> t) {
if (t == null) {
return null;
} else if (t.left == null) {
return t;
}
return findMin(t.left);
}
private BinaryNode<T> findMax(BinaryNode<T> t) {
if (t != null) {
while (t.right != null) {
t = t.right;
}
}
return t;
}
// 插入函数中，也是比较。直到某个叶子节点，将新节点插入到其左子树或者右子树
private BinaryNode<T> insert(T x, BinaryNode<T> t) {
if (t == null) {
return new BinaryNode<T>(x, null, null);
}
int compareResult = x.compareTo(t.element);
if (compareResult < 0) {
t.left = insert(x, t.left);
} else if (compareResult > 0) {
t.right = insert(x, t.right);
}
return t;
}
// 删除函数中，如果一个节点是叶子节点则直接删除，如果只有一个子节点，则将节点删除后，其子节点向上移动
// 如果有两个子节点，一般的删除策略是用其右子树的最小数据代替该节点的数据并递归地删除那个节点（因为右子树中
// 最小的节点不可能有左儿子）
private BinaryNode<T> remove(T x, BinaryNode<T> t) {
if (t == null) {
return t;
}
int compareResult = x.compareTo(t.element);
if (compareResult < 0) {
t.left = remove(x, t.left);
} else if (compareResult > 0) {
t.right = remove(x, t.right);
} else if (t.left != null && t.right != null) {
t.element = findMin(t.right).element;
t.right = remove(t.element, t.right);
} else {
t = (t.left != null) ? t.left : t.right;
}
return t;
}
}
说明：相关代码说明在程序中已经注明。可能还有些方法没有，在以后继续添加。这里的层序遍历就是每次将一层的节点打印完之后再打印下一层节点，使用了队列这个数据结构。同时二叉查找树的平均深度是O(log N)。
二、平衡树（AVL树）
暂未实现
三、B树
暂未实现
未完待续。。。
