定义

排序二叉树的定义也是递归定义的，需要满足：

（1）若它的左子树不为空，则左子树上所有节点的值要均小于根节点的值；

（2）若它的右子树不为空，则右子树上所有节点的值要均大于根节点的值；

（3）左、右子树也分别是排序二叉树

如下图，对于排序二叉树，若按中序遍历就可以得到由小到大的有序序列。

创建

创建排序二叉树的步骤就是不断像排序二叉树中添加新节点（p）的过程：

（1）以根节点（root）为当前节点（current）开始搜索；

（2）用新节点p的值和current的值进行比较；

（3）如果p.data>current.data，则current=current.right；若p.data<current.data，则current=current.left；

（4）重复（2）（3），直到找到合适的叶子节点位置；

（5）将p添加到上面找到的合适位置，若新节点更大，则添加为右子节点；否则，加为左子节点

删除节点

当从排序二叉树中删除节点后，要保持它依然是二叉树，必须对它进行维护：

待删除节点p，p的父节点q，p的左子树pL，p的右子树pR

（1·）p是叶子节点，直接将它从其父节点中删除；

（2）p只有左（右）子树，将pL（pR）添加成p的父节点q的左（右）子树即可；

（3）p左右子树均非空，有两种处理方法：

• 将pL设为q的左或右子节点（取决于p是其父节点q的左、右子节点），将pR设为p的中序前驱结点s的右子节点（s是pL最右下的节点，也就是pL中最大的节点）
• 以p的中序前驱或后继替代p所指节点，然后再从原排序二叉树中删去中序前驱或后继节点（也就是用大于p的最小节点或小于p的最大节点代替p节点）

Java实现代码：

package com.liuhao.DataStructures;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;


public class SortedBinTree <T extends Comparable>{

	static class Node{
		Object data;
		Node parent;
		Node left;
		Node right;
		
		public Node(Object data, Node parent, Node left, Node right) {
			this.data = http://www.mamicode.com/data;>