创建排序二叉树的步骤：
1、以根节点为当前节点开始搜索
2、拿新节点的值和当前节点的值比较
3、如果新节点的值更大，则以当前结点的右子节点作为新的当前节点；如果新节点的值更小，则以当前节点的左子节点作为新的当前节点
4、重复2、3两个步骤，直到搜索到合适的叶子节点
5、将新节点添加为第4步找到的叶子节点的子节点，如果新节点更大，则添加为右子节点；否则添加为左子节点。
删除排序二叉树的一个节点可分为以下几种情况：
1、被删除的节点是叶子节点，只需将它从父节点中删除。
2、被删除节点P只有左子树，将P的左子树PL添加成P的父节点的左子树即可；被删除节点P只有右子树，将P的右子树PR添加成P的父节点的右子树即可；
3、如被删除节点P的左右子树均不为空，则有以下两种做法：
】将PL设为P的父节点Q的左或右子节点（取决于P是其父节点Q的左或右子节点），将PR设为P节点的中序前驱节点S的右子节点（S是PL最右下的节点，也就是PL子树中最大的节点）。
】以P节点的中序前驱或后继代替P所指节点，然后再从原排序二叉树中删去中序前驱或后继节点。（也就是，用大于P的最小节点或小于P的最大节点代替P节点）。
示例代码如下：
import java.util.ArrayList;
import java.util.List;
/**
* 排序2叉树
*
* @author LYYL
*
* @param
*/
public class SortedBinTree{
public static class Node{
Object data;
Node parent;
Node left;
Node right;
public Node(Object data, Node parent, Node left, Node right){
this.data = data;
this.parent = parent;
this.left = left;
this.right = right;
}
public String toString(){
return "[data = " + data + " ]";
}
public boolean equals(Object object){
if(this == object){
return true;
}
if(object instanceof Node){
Node target = (Node)object;
return data.equals(target.data)&&left==target.left
&&right == target.right&&parent == target.parent;
}
return false;
}
}
private Node root;
public SortedBinTree(){
root = null;
}
public SortedBinTree(T o){
root = new Node(o, null, null, null);
}
//添加节点
public void add(T element){
//如果根节点为空
if(root == null){
root = new Node(element, null, null, null);
}else{
Node current = root;
Node parent = null;
int cmp = 0;
do{
parent = current;
cmp = element.compareTo(parent.data);
if(cmp > 0){
//以右子节点作为当前节点
current = current.right;
}else{
current = current.left;
}
}while(current != null);
Node newNode = new Node(element, parent, null, null);
if(cmp > 0){
parent.right = newNode;
}else{
parent.left = newNode;
}
}
}
//删除节点
public void remove(T element){
//获取要删除的节点：
Node target = getNode(element);
if(target == null){
return;
}
//被删除节点既没有左节点又没有右节点
if(target.left == null && target.right == null){
//如果被删除的节点就是根节点
if(target == root){
root = null;
}else{
//被删除节点是父节点的左节点
if(target == target.parent.left){
target.parent.left = null;
}else{
//被删除节点是父节点的右节点
target.parent.right = null;
}
target.parent = null;
}
}
//被删除节点左子树为空，右子树不为空
else if(target.left == null && target.right != null){
if(target == root){
root = target.right;
}else{
//被删除节点是父节点的左节点
if(target == target.parent.left){
target.parent.left = target.right;
}else{
//被删除节点是父节点的右节点
target.parent.right = target.right;
}
}
target.right.parent = target.parent;
//很多书上没有下面两条语句，但我认为如果不加这两句将会造成内存泄露
target.right = null;
target.parent = null;
}
//被删除节点左子树不为空，右子树为空
else if(target.left != null && target.right == null){
if(target == root){
root = target.left;
}else{
//被删除节点是父节点的左节点
if(target == target.parent.left){
target.parent.left = target.left;
}else{
//被删除节点是父节点的右节点
target.parent.right = target.left;
}
}
target.left.parent = target.parent;
//很多书上没有下面两条语句，但我认为如果不加这两句将会造成内存泄露
target.left = null;
target.parent = null;
}
else{
//左右子树均不为空，采用中序遍历的前驱节点替代目标节点
Node maxLeftNode = target.left;
//找到目标节点的前驱节点
while(maxLeftNode.right != null){
maxLeftNode = maxLeftNode.right;
}
//从原来的子树中删除maxLeftNode节点
maxLeftNode.parent.right = null;
//让maxLeftNode的父节点指向target的父节点
maxLeftNode.parent = target.parent;
if(target == target.parent.left){
//如果target的为父节点的左节点
target.parent.left = maxLeftNode;
}else{
target.parent.right = maxLeftNode;
}
maxLeftNode.left = target.left;
maxLeftNode.right = target.right;
//置空删除节点的引用，防止内存泄露
target.parent = target.right = target.left = null;
}
}
//根据指定元素找到该节点
public Node getNode(T element){
Node current = root;
int cmp = 0;
do{
cmp = element.compareTo(current.data);
if(cmp > 0){
current = current.right;
}else if(cmp < 0){
current = current.left;
}else{
break;
}
}while(current != null);
return current;
}
//采用中序遍历二叉树，得到该2叉树的有序排列
public ListinIterator(){
return inIterator(root);
}
public ListinIterator(Node node){
Listlist = new ArrayList ();
if(node.left != null){
list.addAll(inIterator(node.left));
}
list.add(node);
if(node.right != null){
list.addAll(inIterator(node.right));
}
return list;
}
//获得排序二叉树的深度
public int getTreeDeep(){
return getTreeDeep(root);
}
public int getTreeDeep(Node node){
if(node == null){
return 0;
}
if(node.left == null && node.right == null){
return 1;
}
else{
int leftDeep = getTreeDeep(node.left);
int rightDeep = getTreeDeep(node.right);
int max = leftDeep>rightDeep ? leftDeep : rightDeep;
return max+1;
}
}
public static void main(String[] args) {
SortedBinTreetree = new SortedBinTree ();
tree.add(5);
tree.add(20);
tree.add(10);
tree.add(3);
tree.add(8);
tree.add(15);
tree.add(30);
tree.add(32);
tree.add(27);
tree.add(18);
System.out.println(tree.inIterator());
System.out.println("树的深度为： " + tree.getTreeDeep());
tree.remove(20);
System.out.println(tree.inIterator());
System.out.println("树的深度为： " + tree.getTreeDeep());
}
}
结果如下：
