1 package Tree;  2   3 import org.junit.Test;  4   5 class TreeNode {  6   7     int val = 0;  8     TreeNode left = null;  9     TreeNode right = null; 10  11     public TreeNode(int val) { 12         this.val = val; 13  14     } 15  16 } 17  18 public class BinarySearchTree { 19  20     /** 21      * @param T 22      *            二叉搜索树的根节点 23      * @param number 24      *            要查找的树 25      * @return 值域为number的节点 26      */ 27     public TreeNode treeSearch(TreeNode T, int number) { 28  29         if (T == null || T.val == number) 30             return T; 31         if (number < T.val) 32             return treeSearch(T.left, number); 33         else 34             return treeSearch(T.right, number); 35  36     } 37  38     // 通过迭代的方式进行搜索 39     public TreeNode iteratorTreeSearch(TreeNode T, int number) { 40  41         if (T == null || T.val == number) 42             return T; 43         TreeNode treeNode = T; 44         while (treeNode.val != number) { 45             if (number < treeNode.val) 46                 treeNode = treeNode.left; 47             else 48                 treeNode = treeNode.right; 49         } 50         return treeNode; 51     } 52  53     // 返回节点treeNode的父节点 54     public TreeNode treeSearchParent(TreeNode T, TreeNode treeNode) { 55  56         if (T == null || T == treeNode) 57             return null; 58         TreeNode treeNodeParent = null; 59         while (treeNode.val != T.val) { 60             treeNodeParent = T; 61             if (treeNode.val < T.val) 62                 T = T.left; 63             else 64                 T = T.right; 65         } 66         return treeNodeParent; 67     } 68  69     // 返回二叉搜索树中的最大值的节点 70     public TreeNode treeMaximum(TreeNode T) { 71  72         if (T == null) 73             return T; 74         TreeNode treeNode = T; 75         while (treeNode.right != null) 76             treeNode = treeNode.right; 77         return treeNode; 78     } 79  80     // 返回二叉搜索树中的最小值的节点 81     public TreeNode treeMinimum(TreeNode T) { 82  83         if (T == null) 84             return T; 85         TreeNode treeNode = T; 86         while (treeNode.left != null) 87             treeNode = treeNode.left; 88         return treeNode; 89     } 90  91     // 返回节点treeNode的后继,如果没有则返回null 92     // while循环中的判断条件为引用相等,也就是说传入的节点引用必须是二叉树中该节点的引用 93     // 也可以用treeNode.val == treeNodeParent.right.val替换,仅仅判断值是否相等 94     public TreeNode treeSuccessor(TreeNode T, TreeNode treeNode) { 95  96         if (treeNode == null) 97             return null; 98         if (treeNode.right != null) 99             return treeMinimum(treeNode.right);100         TreeNode treeNodeParent = treeSearchParent(T, treeNode);101         while (treeNodeParent != null && treeNode == treeNodeParent.right) {102             treeNode = treeNodeParent;103             treeNodeParent = treeSearchParent(T, treeNodeParent);104         }105         return treeNodeParent;106     }107 108     /**109      * 将节点z插入到二叉搜索树T中110      * 111      * @param T112      * @param z113      */114     public void treeInsert(TreeNode T, TreeNode z) {115 116         // 树为空的情况117         if (T == null) {118             T = z;119             return;120         }121         // 树非空的情况,假设所有节点都不相同,y始终记录x的父节点122         TreeNode y = null, x = T;123         while (x != null) {124             y = x;125             if (z.val < x.val)126                 x = x.left;127             else128                 x = x.right;129         }130         if (z.val < y.val)131             y.left = z;132         else133             y.right = z;134     }135 136     // 中序遍历二叉搜索树T137     public void treeInOrder(TreeNode T) {138 139         if (T == null)140             return;141         treeInOrder(T.left);142         System.out.print(T.val + ",");143         treeInOrder(T.right);144     }145 146     // 用一颗以v为根的子树来替代一颗以u为根的子树,使得u的双亲结点成为v的双亲结点147     // 注意,这里并没有修改结点v的左右指针,由调用者进行修改148     public void transplant(TreeNode T, TreeNode u, TreeNode v) {149         TreeNode uParent = treeSearchParent(T, u);150         // u是根结点的情况151         if (T == u)152             T = v;153         else if (uParent.left == u)154             uParent.left = v;155         else if (uParent.right == u)156             uParent.right = v;157     }158 159     // 二叉搜索树结点删除的真正算法要开始了160     public void treeDelete(TreeNode T, TreeNode z) {161         // 找到结点z的直接后继y162         TreeNode y = treeSuccessor(T, z);163         // 1,要删除的结点z没有左孩子,无论右孩子是否为空,直接替换164         if (z.left == null)165             transplant(T, z, z.right);166         // 2,要删除的结点z没有右孩子,无论左孩子是否为空,直接替换167         else if (z.right == null)168             transplant(T, z, z.left);169         // 3,要删除的结点z既有左孩子也有右孩子,结点z的直接后继y是结点z的右孩子170         // 代码还可以再优化一下,这里只是为了条理清晰方便理解171         else if (z.right == y) {172             transplant(T, z, y);173             y.left = z.left;174         }175         // 4,要删除的结点z既有左孩子也有右孩子,结点z的直接后继y不是结点z的右孩子176         else {177             // 此时y结点的左孩子一定为空178             transplant(T, y, y.right);179             transplant(T, z, y);180             y.right = z.right;181             y.left = z.left;182         }183     }184 185     @Test186     public void testInsert() {187         TreeNode T = new TreeNode(15);188         TreeNode treeNode = null;189         int[] array = { 6, 18, 3, 7, 17, 20, 2, 4, 13, 9 };190         for (int i = 0; i < array.length; ++i) {191             treeNode = new TreeNode(array[i]);192             treeInsert(T, treeNode);193         }194         treeInOrder(T);195         // 测试搜索功能196         System.out.println();197         System.out.println(treeSearch(T, 20).val);198         System.out.println(iteratorTreeSearch(T, 13).val);199         // 测试最大最小功能200         System.out.println("最大值为:" + treeMaximum(T).val);201         System.out.println("最小值为:" + treeMinimum(T).val);202         // 测试父节点功能203         System.out204                 .println("2的父节点为:" + treeSearchParent(T, new TreeNode(2)).val);205         // 测试前驱后继功能206         System.out.println("13的后继节点为:"207                 + treeSuccessor(T, treeSearch(T, 13)).val);208     }209 210     @Test211     public void testDelete() {212         // 该二叉搜索树的根节点的值为15213         TreeNode T = new TreeNode(15);214         TreeNode treeNode = null;215         int[] array = { 6, 18, 3, 7, 8, 17, 20, 2, 4, 13, 9, 22 };216         for (int i = 0; i < array.length; ++i) {217             treeNode = new TreeNode(array[i]);218             treeInsert(T, treeNode);219         }220         treeInOrder(T);221         System.out.println();222         // 测试二叉搜索树中删除结点的功能,删除的四种情况都需要测试223         treeDelete(T, treeSearch(T, 6));224         treeInOrder(T);225     }226 227 }