定义
二叉排序树又称二叉查找树或二叉搜索树，它或者是一棵空树，或者是具有如下性质的二叉树：1、若它是左子树非空，则左子树上所有节点的值均小于根节点的值2、若它的右子树非空，则右子树上所有节点的值均大于根节点的值3、左、右子树本身就是两根二叉排序树
查找
因为二叉排序中左子树上所有节点关键字均小于根节点的关键字；右子树上所有节点的关键字均大于根节点的关键字，所以在二叉排序树上进行查找，与折半查找过程类似。在二叉排序树上进行查找的过程为：若二叉排序树非空，将给定值与根节点的关键字值比较，若相等，则查找成功；若不等，则当根节点的关键字值大于给定值时，到根的左子树中进行查找；否则到根的右子树中进行查找。若找到，则查找过程是走了一条从树根到所找到节点的路径；否则，查找过程终止于一棵空树。
创建
每次插入的新节点都是二叉排序树上新的叶子节点，则在进行插入操作时，不必移动其他节点，仅需改动某个节点的指针。这就是相当于一个有序序列上插入一个记录而不需要移动其他记录。它表明，二叉排序树具有类似于折半查找的我，可采用链表存结构，因此是动态查找的一种适宜表示。另外，由于一棵二叉排序树的形态完全由输入序列决定，所以在输入充已经有序的情况下，所构造的二叉排序树是一棵单枝树，从二叉树的查打过程可知，这种情况下的查找效率和顺序查找的效率是相同的。
删除
在查找二叉树上删除一个节点时，要考虑三种情况：1、若待删除的节点P是叶子节点，则直接删除该节点；2、若待删除的节点P只有一个子节点，则将这个节点与删除节点的父节点直接连接，然后删除节点P；3、若待删除节点P有两个子节点时，应该使用中序遍历方式得到的直接前置节点S或直接后继节点S的值来代替点P的值，然后删除节点S，（注：节点S肯定属于上述1、2情况之一）。比如删除下50节点，可以使用直接前置节点45或直接后继节点65来替换它。注：这里到底是使用直接前置节点还是使用直接后继节点是有讲究的，因为迭代器的next与找替代元素可以使用一套共用的代码successor方法，而迭代当然是从前向后迭代（中序遍历顺序）是最自然的了，所以我们这里使用直接后继节点来替换。
对二叉搜索树的中序遍历将按照递增顺序访问树中的元素。二叉搜索树不允许树中的元素重复，所在要添加元素时要加以判断，如果已存在，则直接跳过并返回失败。插入到二叉搜索树中的节点总是会成为树中的叶子节点，所有在插入元素之后，没有必要重组树。但删除一个节点却比插入一个节点复杂得多，如果删除的不是叶子节点，则删除后必须重组树。
实现
1 package tree.search; 2 3 /** 4 * 树节点访问接口 5 * @author jzj 6 * @date 2010-1-3 7 * @param8 */ 9 public interface TreeOrder > {10 11 static interface Visitor > {12 void visit(E ele);13 }14 15 //前序遍历16 void preOrder(Visitor v);17 18 //中序遍历19 void inOrder(Visitor v);20 21 //后序遍历22 void postOrder(Visitor v);23 24 //层次遍历25 void levelOrder(Visitor v);26 }
1 package tree.search; 2 3 import java.util.AbstractSet; 4 import java.util.Iterator; 5 import java.util.LinkedList; 6 import java.util.NoSuchElementException; 7 import java.util.Random; 8 9 /** 10 * 二叉搜索树（也叫二叉排序树）实现 11 * 12 * @author jzj 13 * @data 2009-12-18 14 * @param15 */ 16 public class BinSearchTree > extends AbstractSet implements 17 TreeOrder { 18 private static class Entry { 19 /* 20 * 注，内部类的字段一般定义成默认访问修饰符要好一点，因为这样外部类可以直接字段 21 * ，而不必要使用get、set这样做只是为了更简洁，而该内部类又是私有的，所以外面 22 * 即使是同包也是不可能直接访问到的 23 */ 24 E elem;//数据域 25 Entry paraent;//父节点 26 Entry left;//左节点 27 Entry right;//右节点 28 29 //构造函数只有两个参数，左右节点是调用add方法时设置 30 public Entry(E elem, Entry parent) { 31 this.elem = elem; 32 this.paraent = parent; 33 } 34 } 35 36 private Entry root;//根节点 37 private int size;//树节点个数 38 39 public BinSearchTree() { 40 root = null; 41 } 42 43 //前序遍历 44 public void preOrder(Visitor v) { 45 preOrder(root, v); 46 } 47 48 private final void preOrder(Entry p, Visitor v) { 49 if (p != null) { 50 v.visit(p.elem); 51 preOrder(p.left, v); 52 preOrder(p.right, v); 53 } 54 } 55 56 //中序遍历 57 public void inOrder(Visitor v) { 58 inOrder(root, v); 59 } 60 61 private final void inOrder(Entry p, Visitor v) { 62 if (p == null) { 63 return; 64 } 65 inOrder(p.left, v); 66 v.visit(p.elem); 67 inOrder(p.right, v); 68 69 } 70 71 //后序遍历 72 public void postOrder(Visitor v) { 73 postOrder(root, v); 74 75 } 76 77 private final void postOrder(Entry p, Visitor v) { 78 if (p == null) { 79 return; 80 } 81 82 postOrder(p.left, v); 83 postOrder(p.right, v); 84 v.visit(p.elem); 85 86 } 87 88 //层次 89 public void levelOrder(Visitor v) { 90 if (root == null) { 91 return; 92 } 93 LinkedList > queue = new LinkedList >(); 94 queue.addLast(root); 95 while (!queue.isEmpty()) { 96 Entry p = queue.removeFirst(); 97 v.visit(p.elem); 98 if (p.left != null) { 99 queue.add(p.left);100 }101 if (p.right != null) {102 queue.add(p.right);103 }104 }105 }106 107 public int size() {108 return size;109 }110 111 /**112 * 是否含有某元素113 * @param e114 * @return boolean115 */116 public boolean contanins(E e) {117 Entry tmp = root;118 int comp;119 while (tmp != null) { //如果树不为空120 comp = e.compareTo(tmp.elem);121 //如果与tmp元素相等，则返回122 if (comp == 0) {123 return true;124 }//如果比tmp小，则在tmp的左子树中找125 else if (comp < 0) {126 tmp = tmp.left;127 }//如果比tmp大，则在tmp的右子树中找128 else {129 tmp = tmp.right;130 }131 }132 //树本身就为空或树不为空时没有找到时133 return false;134 }135 136 /**137 * 向二叉搜索树中添加节点138 * 被插入的元素总是变成树中的叶结点，所以在插入元素后，没有必要重新组织树，这与AVL树或139 * RED-BLACK树不太一样140 * @param e141 * @return boolean142 */143 public boolean add(E e) {144 //1、如果树为空，则直接加入145 if (root == null) {146 //根的父节点为null，也就是说只要是parent为null的节点就是根元素147 root = new Entry (e, null);148 size++;149 return true;150 }//如果树不为空151 else {152 Entry tmp = root;153 int comp;154 while (true) { //死循环，直到节点插入到正确位置或元素已存在155 comp = e.compareTo(tmp.elem);156 //2、如果添加的元素e与tmp相等，则表示元素存在，直接返回失败157 if (comp == 0) {158 return false;159 }//3、如果添加的元素e小于tmp节点，则要添加到tmp的左子树中的某个位置上160 else if (comp < 0) {161 //如果tmp的左子树为不为空，则还要继续找添加点162 if (tmp.left != null) {163 tmp = tmp.left;164 }//如果tmp没有左节点，则或把新增元素设置成tmp的左子节点165 else {166 tmp.left = new Entry (e, tmp);167 size++;168 return true;169 }170 }//4、否则在tmp的右子树中找添加位置171 else {172 //如果tmp的右子树为不为空，则还要继续找添加点173 if (tmp.right != null) {174 tmp = tmp.right;175 }//如果tmp没有右子节点，则或把新增元素设置成tmp的右子节点176 else {177 tmp.right = new Entry (e, tmp);178 size++;179 return true;180 }181 }182 }183 }184 }185 186 /**187 * 删除指定的数据域的元素188 * @param p189 * @return boolean190 */191 public boolean remove(E p) {192 //根据数据域查找待删除的元素193 Entry tmp = getEntry(p);194 if (tmp == null) { //如果元素没有找到，则删除失败195 return false;196 } else {197 //删除元素198 deleteEntry(tmp);199 return true;200 }201 }202 203 /**204 * 删除指定的节点实现205 * 206 * 算法思想：207 * 208 * 1、若待删除的节点p是叶子节点，则直接删除该节点；209 * 210 * 2、若待删除的节点p只有一个子节点，则将p的子节点与p的父节点直接连接，然后删除节点p；211 * 为什么只有一个子节点时可以直接接到删除节点的父节点下面呢?因为只有一个子节点，直接接上212 * 去不会影响排序子节点本身的排序，当然更不会影响另外一个子树（因为另一子树跟本不存在!）；213 * 214 * 3、若待删除节点p有两个子节点时，应该使用中序遍历方式得到的直接前置节点S或直接后继节点s215 * 的值来代替点s的值，然后删除节点s，（注：节点s肯定属于上述1、2情况之一）而不是直接删除216 * p，这样可以将该删除问题转换成上面1、2问题；217 * 218 * @param p 指向被删除的节点p219 */220 private void deleteEntry(Entry p) {221 //如果删除的节点p有左右子树时，将问题转换成删除叶子节点或只有一个子节点的节点问题222 if (p.left != null && p.right != null) {223 /*224 * 删除有两个子节点的节点示例图(转换成删除只有一个子节点的节点或叶子节点问题)：225 * 226 * p → 80 将直接后继元素s的elem替换p元素的 90 227 * /\ elem，然后将p指向s，这样将问题转换 /\ 228 * 15 110 成删除只有一个子节点的节点p问题了 15 110 229 * / / 230 * s → 90 → s、p → 90 231 * \ \232 * 105 105233 * 234 */235 /*236 * 查找待删除节点p的中序遍历节点的直接后继节点。注，该后继节点只可能是叶子节点237 * （该叶子节点只可能是以下两种：一种是就是右子节点本身，因为可能待删除节点p的238 * 右子节点没有左右子树了；第一种就是待删除节点p右子节点的左子树上最左边的叶子239 * 节点），或只有一个右子节点的节点（该节点只可能是在上述第二种叶子节点上上多了240 * 一个右子树罢了）241 */242 Entry s = successor(p);243 /*244 * 当待删除的节点p的左右子树都存在时，我们不正真真删除p这个节点，而是用后继节点s245 * 来替换p节点，具体作法就是什么后继节点的数据域elem替换待删除节点p的数据域elem，246 * 替换之后，我们让真真待删除的节点p变成后继节点s（即让p指向s），因为这样将问题转247 * 换成删除叶子节点或只有一个子节点（这个子节点有个特点就是左子树一定为空）的节点的248 * 问题了，这样也就能共用下面真正的删除叶子节点与删除只有一个子节点的节点边辑了249 */250 p.elem = s.elem;//使用后继节点s的数据替换p的数据域251 252 p = s;//让p指向直接后继节点s，这样删除p时实质上是删除的直接后节点253 }254 255 /*256 * !! 注，程序运行到这里时，如果待删除的节点p左右子树都存在时，已被上面程序逻辑转换成了257 * 删除叶子节点或只有一个子节点（一定是右子节点）的节点问题了，当然下面的删除逻辑还不只适258 * 用于删除只有一个右子节点的节点，还适用于删除只有一个左子节点的节点，总之能适用于删除只259 * 一个子节点的节点，而不管这个子节点是左还是有。 260 * 261 * 下面程序开始删除叶子节点或只有一个子节点的节点：262 */263 264 //若待删除的节点p是叶子节点，则直接删除该节点，无需用后继节点填补265 if (p.left == null && p.right == null) {266 /*267 * 删除叶子节点示例图：268 * 269 * 80 80270 * /\ /\271 * 20 110 → 20 110272 * \ / /273 * p → 50 90 90274 * \ \275 * 105 105276 * 277 * p指向要删除的节点50，要做的就是将50的父节点Entry对象（元素为20的Entry对象）的278 * 右子节点修改为null279 */280 //若待删除的节点p是根元素，且又没有子节点时，直接删除释放节点281 if (p.paraent == null) {282 root = null;283 }//如果被删除的节点p为左叶子节点，则把父节点的左指针置为null284 else if (p == p.paraent.left) {285 p.paraent.left = null;286 }//否则被删除的节点p为右叶子节点，则把父节点的右指针置为null287 else {288 p.paraent.right = null;289 }290 291 }//否则删除的是只有一个子节点（不管左还是右都可）的节点时，则需使用后继节点填补292 else {293 294 /*295 * !! 注，到此，p只有一个子节点，不可能即有左子节点同时又有右子节点，因为如果有，296 * 前面逻辑也会把p转换成了只具有一个右子节点的节点297 */298 299 /*300 * 删除只有一个子节点的元素示例图：301 * 302 * 80 80303 * /\ /\304 * p → 20 110 → 50 110305 * \ / /306 * rep → 50 90 90307 * \ \308 * 105 105309 * 310 * p指向要删除的节点20。不能在二叉搜索树中留下空洞，所以必须要用某个元素来取代20，311 * 那么选择哪个元素好?逻辑上选择被删除的子节点15。因此需把15连到20的父节点上。312 */313 Entry rep;// 指向用来替换被删除节点p的，只可能是左子节点或是右子节点314 315 if (p.left != null) {316 //如果只有左子节点时，则用左子节点替换要删除的节点p317 rep = p.left;318 } else { //否则只有右子树，则用右子节点替换要删除的节点p319 rep = p.right;320 }321 //--修改替换节点的父指针指向322 /*323 * 使替换节点的父指针指向删除节点p的父节点，注，如果删除的是根节点，则左右子节点324 * 的父指针都会指向null，则此时需将root指向左或右子节点，即左或右子节点将成为根325 * 节点326 */327 rep.paraent = p.paraent;//设置替换元素的父328 329 //--修改被删除元素p的父节点的左或右指针指向330 //如果删除的是根元素，则重置root331 if (p.paraent == null) {332 root = rep;333 }//如果删除的是某节点的左子节点334 else if (p == p.paraent.left) {335 p.paraent.left = rep;336 }//否则删除的是某节点的右子节点337 else {338 p.paraent.right = rep;339 }340 341 }342 //让删除节点成为孤立点343 p.paraent = null;344 p.left = null;345 p.right = null;346 347 size--;//删除节点后树节点个数减一348 }349 350 /**351 * 根据指定的数据域查找元素352 * @param e353 * @return Entry 354 */355 private Entry getEntry(E e) {356 Entry tmp = root;357 int c;358 while (tmp != null) { //如果树不为空359 c = e.compareTo(tmp.elem);360 //如果与tmp元素相等，则返回361 if (c == 0) {362 return tmp;363 }//如果比tmp小，则在tmp的左子树中找364 else if (c < 0) {365 tmp = tmp.left;366 }//如果比tmp大，则在tmp的右子树中找367 else {368 tmp = tmp.right;369 }370 }371 //树本身就为空或树不为空时没有找到时372 return null;373 }374 375 /**376 * 查找指定节点的中序遍历序列的直接后继节点377 * 378 * 注，无需在左子树上找，因为中序遍历时，左子树上的节点都会在该节点的前面遍历。379 * 380 * 1、如果待查找的节点有右子树，则后继节点一定在右子树上，此时右子树上的某个节点可能成为后381 * 继节点：一是如果待查节点的右子树没有左子树（有没有右子树无所谓）时，直接就返回该待查节点382 * 的右子节点；二是如果待点节点的右子节点有左子树，则查找右子节点的最左边的左子树节点（注，383 * 该节点一点是左叶子节点或只有一个右子节点的左节点，查找过程要一直向左，即遍历时只向左拐，384 * 不可向右）385 * 386 * 2、如果待查找的节点没有右子树，则需要从该节点向根的方向遍历（不可向左或右拐），后继节点只387 * 可能在祖宗节点中产生（包括父节点与根节点在内），此情况分两种：一种就是待查节点为某节点的左388 * 子树，则此时的后继为父节点；第二种就是当待查节点为某个节点的右子树时，则需沿根的方向向上找，389 * 一直找到第一个有左子树的祖宗节点即为后继节点，或到根为止还没有找到（则该节点只可能为中序遍390 * 历的最后节点）。391 * 392 * @param e 需要查找哪个节点的直接后继节点393 * @return Entry 直接后继节点394 */395 private Entry successor(Entry e) {396 if (e == null) {397 return null;398 }//如果待找的节点有右子树，则在右子树上查找399 else if (e.right != null) {400 /*401 * 查找50节点的直接后继，查找结果为55402 * 50403 * \404 * 75405 * /406 * 61407 * /\408 * 55 68409 * \410 * 59 411 */412 //默认后继节点为右子节点（如果右子节点没有左子树时即为该节点）413 Entry p = e.right;414 while (p.left != null) {415 //注，如果右子节点的左子树不为空，则在左子树中查找，且后面找时要一直向左拐416 p = p.left;417 }418 return p;419 }//如果待查节点没有右子树，则要在祖宗节点中查找后继节点 420 else {421 422 /*423 * 没有右子树的节点且为父节点的右子节点36的直接后继为37，同样节点68的直接后继为75424 * 没有右子树的节点且为父节点的左子节点37的直接后继为50，同样节点28的直接后继为30425 * 75为最后节点，所以直接后继为null426 * 427 * 50428 * /\429 * 37 75430 * / /431 * 25 61 432 * /\ /\433 * 15 30 55 68 434 * /\ \435 * 28 32 59436 * \437 * 36438 * /439 * 35440 */441 //默认后继节点为父节点（如果待查节点为父节点的左子树，则后继为父节点）442 Entry p = e.paraent;443 Entry c = e;//当前节点，如果其父不为后继，则下次指向父节点444 //如果待查节点为父节点的右节点时，继续向上找，一直要找到c为左子节点，则p才是后继445 while (p != null && c == p.right) {446 c = p;447 p = p.paraent;448 }449 return p;450 }451 }452 453 /**454 * 查找指定节点的中序遍历序列的直接前驱节点455 * 456 * 查找逻辑与找直接后继节点刚好相反或对称457 * @param e458 * @return459 */460 private Entry precursor(Entry e) {461 if (e == null) {462 return null;463 }//如果待找的节点有左子树，则在在子树上查找464 else if (e.left != null) {465 //默认直接前驱节点为左子节点（如果左子节点没有右子树时即为该节点）466 Entry p = e.left;467 while (p.right != null) {468 //注，如果左子节点的右子树不为空，则在右子树中查找，且后面找时要一直向右拐469 p = p.right;470 }471 return p;472 }//如果待查节点没有左子树，则要在祖宗节点中查找前驱节点 473 else {474 //默认前驱节点为父节点（如果待查节点为父节点的右子树，则前驱为父节点）475 Entry p = e.paraent;476 Entry current = e;//当前节点，如果其父不为前驱，则下次指向父节点477 //如果待查节点为父节点的左节点时，继续向上找，一直要找到current为p的右子节点，则s才是前驱478 while (p != null && current == p.left) {479 current = p;480 p = p.paraent;481 }482 return p;483 }484 }485 486 /**487 * 提供迭代器接口488 * @return489 */490 public Iterator iterator() {491 return new TreeItrator();492 }493 494 /**495 * 树的迭代器496 * @author jzj497 * @date 2009-12-19498 */499 500 public class TreeItrator implements Iterator {501 502 private Entry lastRet;//最近一次next操作返回的节点503 private Entry next;//下一个节点504 private Entry endNode;//树最后一个节点505 506 TreeItrator() {507 //初始化时，让next指根节点，如果根没有左子树时，则就为根508 next = root;509 if (next != null) {510 //如果next还有左子树时，则为左子节点，直到最左边节点为止511 while (next.left != null) {512 next = next.left;//从根节点开始，一直向左拐513 }514 }515 }516 517 //是否还有下一个节点518 public boolean hasNext() {519 return next != null;520 }521 522 //返回下一个节点，即next指向的节点523 public E next() {524 if (next == null) {525 throw new NoSuchElementException();526 }527 lastRet = next;528 next = successor(next);//下一个为直接后继节点529 530 //如果后继节点为null，表示该next指向的节点为树中的最后节点531 if (next == null) {532 /*533 * 使用endNode记录下最末节点，以便 previous 使用，因为next最终会指向null，534 * 即好比指向了最末节点的后面，此时previous是要返回最末节点的，所以需要标记535 * 与存储起来536 */537 endNode = lastRet;538 }539 return lastRet.elem;540 }541 542 //是否有前驱节点543 public boolean hasPrevious() {544 return (next != null && precursor(next) != null) || endNode != null;545 }546 547 //返回前驱节点548 public E previous() {549 if ((next != null && precursor(next) == null)) {550 throw new NoSuchElementException();551 }552 553 //如果已迭代到了最末节点554 if (endNode != null) {555 //使用lastReturned与next都指向最末节点556 lastRet = next = endNode;557 endNode = null;558 } else { //如果lastReturned指向的不是最末节点时559 lastRet = next = precursor(next);560 }561 562 return lastRet.elem;563 }564 565 //删除最后一次next或previous方法返回的节点566 public void remove() {567 if (lastRet == null) {568 throw new IllegalStateException();569 }570 571 /*572 * 注，如果删除的节点（lastRet指向的节点）具有左右子节点，则在调用573 * deleteEntry方法删除后，它会使用这个后继节点的数据域替换待删除的节点的数据574 * 域，next指向的节点会被移到lastRet位置，所以如果此时不使用next回退575 * 到lastRet的位置，则 next指向的节点（Entry）对象将是一个不在这棵树中576 * 的节点。如果删除的是一个叶子节点或只有一个节点的节点时不会有这种问题。577 * 578 * 删除有两个子节点的节点40，删除后next指向的节点已被移到lastRet，所以579 * next需后退580 * 581 * 先后退 后删除50582 * lastRet → 40 next、lastRet → 50 next → 50583 * /\ → /\ /\584 * 20 75 20 75 → 20 75585 * /\ /\ \586 * next → 50 80 50 80 50 80587 * 588 * 删除只有一个子节点的节点20，删除后next指向不需要改变，因为next指向的元素没有589 * 发生变化，删除前后还是指向原来的30590 * 50 50591 * /\ /\592 * lastRet → 20 75 → next → 30 75593 * \ /594 * next → 30 28595 * / 596 * 28 20597 */598 if (lastRet.left != null && lastRet.right != null) {599 next = lastRet;600 }601 602 deleteEntry(lastRet);//删除最后一次next方法返回的元素603 604 lastRet = null;//不能连续删除，只有在使用next后才能删除605 }606 }607 608 private static void fixText() {609 BinSearchTree bst = new BinSearchTree ();610 bst.add(50);611 bst.add(37);612 bst.add(75);613 bst.add(25);614 bst.add(61);615 bst.add(15);616 bst.add(30);617 bst.add(55);618 bst.add(68);619 bst.add(28);620 bst.add(32);621 bst.add(59);622 bst.add(36);623 bst.add(36);//添加一个重复，但不能添加进去624 625 //是否包含626 System.out.println(bst.contanins(36));//true627 System.out.println(bst.contanins(38));//false628 629 //大小630 System.out.println(bst.size());//13631 632 //遍历633 Iterator itr = bst.iterator();634 while (itr.hasNext()) {635 //15 25 28 30 32 36 37 50 55 59 61 68 75636 System.out.print(itr.next() + " ");637 }638 System.out.println();639 640 //从后往前遍历641 BinSearchTree .TreeItrator titr = (BinSearchTree .TreeItrator) itr;642 while (titr.hasPrevious()) {643 //75 68 61 59 55 50 37 36 32 30 28 25 15644 System.out.print(titr.previous() + " ");645 }646 System.out.println();647 648 //测试迭代器的 previous 649 titr = (BinSearchTree .TreeItrator) bst.iterator();650 System.out.println(titr.hasPrevious());//false651 System.out.println(titr.next());//15652 System.out.println(titr.previous());//15653 System.out.println(titr.next());//15654 System.out.println(titr.next());//25655 System.out.println(titr.next());//28656 System.out.println(titr.previous());//28657 658 //删除根叶子节点36659 bst.remove(36);660 System.out.println(bst.size());//12661 itr = bst.iterator();662 while (itr.hasNext()) {663 //15 25 28 30 32 37 50 55 59 61 68 75664 System.out.print(itr.next() + " ");665 }666 System.out.println();667 668 //删除只有一个左子节点的节点37669 bst.remove(37);670 System.out.println(bst.size());//11671 itr = bst.iterator();672 while (itr.hasNext()) {673 //15 25 28 30 32 50 55 59 61 68 75 674 System.out.print(itr.next() + " ");675 }676 System.out.println();677 678 //删除只有一个右子节点的节点55679 bst.remove(55);680 System.out.println(bst.size());//10681 itr = bst.iterator();682 while (itr.hasNext()) {683 //15 25 28 30 32 50 59 61 68 75 684 System.out.print(itr.next() + " ");685 }686 System.out.println();687 688 //删除有左右子节点的根节点50689 bst.remove(50);690 System.out.println(bst.size());//9691 itr = bst.iterator();692 while (itr.hasNext()) {693 //15 25 28 30 32 59 61 68 75 694 System.out.print(itr.next() + " ");695 }696 System.out.println();697 698 //下面通过迭代器删除节点根节点59699 itr = bst.iterator();700 while (itr.hasNext()) {701 if (itr.next() == 59) {702 itr.remove();//删除最近一次next返回的节点703 break;704 }705 }706 707 while (itr.hasNext()) {708 //61 68 75709 System.out.print(itr.next() + " ");710 itr.remove();711 }712 713 System.out.println();714 System.out.println(bst.size());//5715 }716 717 private static void randomTest() {718 BinSearchTree myTree = new BinSearchTree ();719 Random random = new Random();720 System.out.print("随机产生的节点为：");721 int num = 0;722 //直到树的节点数为n止723 while (myTree.size() < 21) {724 num = random.nextInt(100);725 myTree.add(num);726 System.out.print(num + " ");727 }728 System.out.println("");729 730 System.out.println("这棵平衡二叉树的总节点数：" + myTree.size());731 System.out.println("在树中查找 " + num + " 节点:" + myTree.contains(new Integer(num)));732 System.out.println("在树中查找 100 节点:" + myTree.contains(new Integer(100)));733 System.out.print("中序遍历(从前往后)：");734 BinSearchTree .TreeItrator itr = (BinSearchTree .TreeItrator) myTree735 .iterator();736 while (itr.hasNext()) {737 System.out.print(itr.next() + " ");738 }739 System.out.println("");740 741 System.out.print("中序遍历(从后往前)：");742 while (itr.hasPrevious()) {743 System.out.print(itr.previous() + " ");744 }745 System.out.println("");746 747 myTree.remove(num);748 System.out.print("删除节点 " + num + " 后遍历：");749 itr = (BinSearchTree .TreeItrator) myTree.iterator();750 while (itr.hasNext()) {751 System.out.print(itr.next() + " ");752 }753 System.out.println("");754 755 System.out.println("使用迭代器删除所有节点");756 itr = (BinSearchTree .TreeItrator) myTree.iterator();757 while (itr.hasNext()) {758 itr.next();759 itr.remove();760 }761 System.out.println("删除后树的总节点数：" + myTree.size());762 763 }764 765 private static void order() {766 BinSearchTree myTree = new BinSearchTree ();767 Random random = new Random();768 int num = 0;769 while (myTree.size() < 10) {770 num = random.nextInt(100);771 myTree.add(num);772 }773 774 System.out.print("前序遍历 - ");775 myTree.preOrder(new Visitor () {776 777 public void visit(Integer e) {778 System.out.print(e + " ");779 780 }781 });782 System.out.println();783 784 System.out.print("中序遍历 - ");785 myTree.inOrder(new Visitor () {786 787 public void visit(Integer e) {788 System.out.print(e + " ");789 790 }791 });792 System.out.println();793 794 System.out.print("后序遍历 - ");795 myTree.postOrder(new Visitor () {796 797 public void visit(Integer e) {798 System.out.print(e + " ");799 800 }801 });802 System.out.println();803 804 System.out.print("层次遍历 - ");805 myTree.levelOrder(new Visitor () {806 807 public void visit(Integer e) {808 System.out.print(e + " ");809 810 }811 });812 System.out.println();813 }814 815 //测试816 public static void main(String[] args) {817 fixText();//固定测试818 randomTest();//随机测试819 order();//遍历820 }821 }