为什么要用树？
在有序数组中用二分查找法查找数据项很快，查找数据的时间为O（logN），但是插入数据项很慢，平均来讲要移动数组中一半的数据项。而在链表中插入和删除操作很快，但是查找必须从头开始，平均需要访问N/2个数据项。就这样，树产生了，既能像链表那样快速的插入和删除，又能像有序数组那样快速查找。
介绍树的一些术语：
路径：顺着连接节点的边从一个节点到另一个节点，所经过的节点的顺序排列成为路径。
根：顶端的节点。一棵树只有一个根。从根到其它任何一个节点都必须有一条（而且只有一条）路径。
父节点：每个节点（除了根）都恰好有一条边向上连接到另一个节点，上面的节点就称为下面节点的父节点。除了根节点，树的任何节点都有且只有一个父节点。
子节点：每个节点都可能有一条或多条边想下连接其他节点，下面的这些节点就称为它的“子节点”。
叶子结点：没有子节点的节点称为“叶子结点”或简称“叶节点”。
访问：当程序控制流程到达某个节点时，就称为“访问”这个节点。
遍历：遍历意味着要遵循某种特定的顺序访问书中所有节点。
层：一个节点的层数是指从根开始到这个节点有多少“代”。假设根是第0层，它的子节点就是第一层。
二叉树：如果树中每个节点最多只有两个子节点，这样的树就称为“二叉树”。二叉树每个节点的两个子节点称为“左子节点”和“右子节点”。
下面重点介绍二叉搜索树。
二叉搜索树是一个节点的左子节点的关键字小于这个节点，右子节点的关键字大于这个节点。
节点类：
public class TreeNode {
//节点值
int value;
//左子节点
TreeNode left;
//右子节点
TreeNode right;
public TreeNode(int value){
this.value = value;
this.left = null;
this.right = null;
}
public TreeNode(){
this.value = 0;
this.left = null;
this.right = null;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public TreeNode getLeft() {
return left;
}
public void setLeft(TreeNode left) {
this.left = left;
}
public TreeNode getRight() {
return right;
}
public void setRight(TreeNode right) {
this.right = right;
}
}
二叉搜索树类：（插入相同数据无效）
public class BinarySearchTree {
//根节点
private TreeNode root;
/**
*无参构造函数
*/
public BinarySearchTree() {
this.root = null;
}
/**
* 构造函数
* @param value
*/
public BinarySearchTree(int value) {
root = new TreeNode(value);
}
/**
* 插入一条数据
* @param value
*/
public void insertNode(int value) {
//新增节点
TreeNode newNode = new TreeNode(value);
//判断二叉树是否为空
if (this.root == null) {
root = newNode;
return;
}
//父节点
TreeNode parent = null;
//当前节点从root开始比较
TreeNode current = root;
while (true) {
//如果节点中已经有此元素，返回
if (value == current.value)
return;
//插入的元素比根节点元素小，向左子节点走
else if (value < current.value) {
parent = current;
current = current.left;
//左子节点为空就插入
if (current == null ) {
parent.left = newNode;
return;
}
} else {//插入的元素比根节点元素大，向右子节点走
parent = current;
current = current.right;
//右子节点为空就插入
if (current == null ) {
parent.right = newNode;
return ;
}
}
}
}
//分析二叉搜索树，删除某一节点后，补充的节点为其右子节点序列中最小的（即右子孙节点中最小的）。
public void deleteNode(int value) {
if(this.root == null){
return;
}
if(search(value)){
TreeNode deleteNode = this.root;
TreeNode parentNode = null;
while(true){//得到要删除节点和此节点的父节点
if(value == deleteNode.getValue()){
break;
} else if(value < deleteNode.getValue()){
parentNode = deleteNode;
deleteNode = deleteNode.getLeft();
} else{
parentNode = deleteNode;
deleteNode = deleteNode.getRight();
}
}
if(deleteNode.left == null && deleteNode.right == null){//删除节点无子节点
//若删除的节点是根节点
if(deleteNode == this.root){
this.root = null;
}else{
if(parentNode.getValue()>deleteNode.getValue()){
parentNode.left = null;
} else{
parentNode.right = null;
}
}
} else if(deleteNode.right == null && deleteNode.left != null){//删除节点只有左子节点
//若删除的节点是根节点
if(deleteNode == this.root){
this.root = deleteNode.left;
}else{
if(parentNode.getValue()>deleteNode.getValue()){
parentNode.left = deleteNode.left;
} else{
parentNode.right = deleteNode.left;
}
}
} else if(deleteNode.left == null && deleteNode.right != null){//删除节点只有右子节点
//若删除的节点是根节点
if(deleteNode == this.root){
this.root = deleteNode.right;
}else{
if(parentNode.getValue()>deleteNode.getValue()){
parentNode.left = deleteNode.right;
} else{
parentNode.right = deleteNode.right;
}
}
} else{//删除节点的左右子节点均存在
TreeNode rightMinNode = getRightMinTreeNode(deleteNode);//得到右子节点里面最小的节点（后继节点）
rightMinNode.left = deleteNode.left;
rightMinNode.right = deleteNode.right;//将后继节点替换成要删除的节点（另一种方法是直接将里面的int数据替换，这样就不需要节点替换）
//若删除的节点是根节点
if(deleteNode == this.root){
this.root = rightMinNode;
}else{
if(parentNode.getValue()>deleteNode.getValue()){
parentNode.left = rightMinNode;
} else{
parentNode.right = rightMinNode;
}
}
}
deleteNode.left = null;
deleteNode.right = null;
deleteNode = null;//这个删除节点无用了
}
}
/**
*返回右子节点里面最小的节点（即后继节点，并且将此节点剥离出来）
* 这里不进行非空判断了，假设查找的节点及其右子节点均存在
*/
public TreeNode getRightMinTreeNode(TreeNode rootNode){
TreeNode parentNode = rootNode;
TreeNode currentNode = rootNode.right;
if(currentNode.left == null){
parentNode.right = currentNode.right;
currentNode.right = null;
}else{
while(currentNode.left != null){
parentNode = currentNode;
currentNode = currentNode.left;
}
parentNode.left = currentNode.right;
currentNode.right = null;
}
return currentNode;
}
/**
* 查找节点
* @param value
* @return
*/
public boolean search(int value) {
if (this.root == null ) {
return false;
}
TreeNode current =this.root;
boolean tag = false;
while (true) {
if (value == current.value) {
tag=true;
break;
} else if (value < current.value) {
current = current.left;
if (current == null ) {
tag = false;
break;
}
} else {
current = current.right;
if (current == null ) {
tag = false;
break;
}
}
}
return tag;
}
/**
* 查找节点
* @param value
* @return
*/
public TreeNode searchNode(TreeNode rootNode,int value){
if (rootNode == null ) {
return null;
}
if (value == rootNode.value) {
return rootNode;
} else if (value < rootNode.value) {
return searchNode(rootNode.left,value);
} else {
return searchNode(rootNode.right,value);
}
}
/**
* 遍历二叉树打印（左根右）（中序遍历）
*/
public void Traversal() {
Traversal(this.root);
}
private void Traversal(TreeNode treeNode) {
//若为空，返回
if ( treeNode == null ) {
return;
}
//递归打印左节点
Traversal(treeNode.left);
//打印此节点
System.out.print(treeNode.value+" ");
//打印右节点
Traversal(treeNode.right);
}
}
测试类：
public class Test {
public static void main(String[] args) {
BinarySearchTree bs = new BinarySearchTree();
bs.insertNode(11);
bs.insertNode(9);
bs.insertNode(8);
bs.insertNode(6);
bs.insertNode(10);
bs.insertNode(15);
bs.insertNode(13);
bs.insertNode(12);
bs.insertNode(17);
bs.insertNode(16);
bs.insertNode(19);
System.out.print("删除前：");
bs.Traversal();
bs.deleteNode(9);
bs.deleteNode(15);
bs.deleteNode(11);
System.out.print("
删除后：");
bs.Traversal();
}
}
结果：
节点的查找与插入都比较简单，删除节点有点复杂。本程序是根据三种情况处理的：
1，删除节点无子节点；
2，删除节点只有一个子节点(分左右的情况)；
3，删除节点的左右子节点均存在。
这三种情况都需要考虑到删除节点是否根节点，前两种很好理解也很好处理，对于第三种，将待删除的节点删除后，取而代之的是后继节点（即右子节点中值最小的）。