二叉搜索树的节点删除算法
删除节点是二叉搜索树操作中最复杂的，但对有些应用又非常重要，有必要好好研究一下。
?
一个取巧的办法：在树节点中加入一个boolean字段，比如isDeleted。需要删除一个节点时就把这个字段置为true，其他操作比如find()在查找之前先判断这个节点是否已经标记为删除了，这样删除的节点将不会改变树的结构，当然这样做还会继续保留这种已经删除的节点。对某些应用场景，这种做法是有优势的，比如已经离职的员工档案要保留在员工记录中。
?
下面来实现这个删除节点的算法。首先列出树节点的数据结构：
?
??
?
删除节点首先从查找要删除的节点入手：
?
import java.util.Random;/** * @author Sun Kui */public class Main { public static void main(String... args) { BinarySearchTree theTree = new BinarySearchTree(); if (args.length < 1) { System.out.println("Usage: java Main number"); return; } int count = Integer.parseInt(args[0]); Random rand = new Random(); for (int i = 0; i < count; i++) { theTree.insert(rand.nextInt(count * count), rand.nextDouble() + 1); } theTree.insert(35, 1.8); Node found = theTree.find(35); System.out.println(found); theTree.inOrder(theTree.getRootNode()); }}??end.
?
