基本概念：
从根结点开始比较，比该结点大放在右子结点；比该结点小放在左子结点
中序遍历：从小到大排序
代码：
//二叉排序树
class BinarySortTree {private Node root;public void add(Node node) {if (root == null)root = node;else root.add(node);}public void infixOrder() {if (root == null)System.out.println("tree is empty");elseroot.infixOrder();}public void delete(int value) {Node parent = root.searchParent(value);Node node = root.searchNode(value);if (node == null) {//没找到待删除的结点System.out.println("未找到该结点");return;}//待删除的是根节点else if (node == root) {if (root.left == null && root.right == null)//该树只有一个结点root = null;else if (root.left == null)//根节点只有右子树root.right = root;else if (root.right == null)//根节点只有左子树root.left = root;else {//找出待删除结点的右子树中值最小的结点Node node1 = node.right;while (node1.left != null) {node1 = node1.left;}node1.left = node.left;//待删除结点的左子树全挂靠过来root = node.right;//根节点的右子结点作为根节点}}//待删除的是非根节点else {if (node.left == null || node.right == null) {//待删除结点只有一颗子树或没有子树if (parent.left == node) {//剩下的结点挂靠在父节点左子树if (node.left != null)parent.left = node.left;else parent.left = node.right;}else {//剩下的结点挂靠在父节点右子树if (node.left != null)parent.right = node.left;else parent.right = node.right;}}else {//待删除有两个子结点//找出待删除结点的右子树中值最小的结点Node node1 = node.right;while (node1.left != null) {node1 = node1.left;}node1.left = node.left;//待删除结点的左子树全挂靠过来if (parent.left == node) {//剩下的结点挂靠在父节点左子树parent.left = node.right;}else { //剩下的结点挂靠在父节点右子树parent.right = node.right;}}}}
}class Node {int value;Node right;Node left;public Node(int value) {this.value = value;}@Overridepublic String toString() {return "Node{" +"value=" + value +'}';}//添加结点public void add(Node node) {if (node == null)return;if (this.value > node.value) {if (this.left == null)this.left = node;elsethis.left.add(node);} else {if (this.right == null)this.right = node;elsethis.right.add(node);}}//中序遍历public void infixOrder() {if (this.left != null)this.left.infixOrder();System.out.println(this);if (this.right != null)this.right.infixOrder();}//查找待删除结点的父节点public Node searchParent(int value) {if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value))return this;//若this.left==null,则不会再判断this.left.value==value，直接将整个语句判为falseif (this.left != null && value < this.value)return this.left.searchParent(value);else if (this.right != null && value >= this.value)return this.right.searchParent(value);else return null;//没找到或是待删除的结点是根节点}//查找结点public Node searchNode(int value) {if (this.value == value) {return this;}if (value < this.value) {//向左子树查找if (this.left != null)return this.left.searchNode(value);else return null;} else {//向右子树查找if (this.right != null)return this.right.searchNode(value);else return null;}}
}