二叉搜索树的概念：
二叉搜索树是一种特殊的二叉树，要么是一颗空树，要么满足以下几点：
1、 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
2、若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
3、它的左右子树也分别为二叉搜索树
下面就是一颗典型的二叉搜索树：
二叉搜索树的操作及其实现
二叉搜索树的查找效率是比较高的，类似与我们所熟知的二分查找。它的查找方式是这样的：如果我们要查找6这个数字，那么我们从根节点开始，遇到根节点的val是5,6>5,所以我们要往右搜寻，遇到7的时候，6<7,这时我们向右左找即可，这就找到了我们要找的数字。
我们可以看的出它的时间复杂度是O(logn)，也就是搜索树的高度，但是，如果这颗搜索树呈现线性的化，也就是一条线的情况：
这时我们在搜索的时候就类似于线性查找，时间复杂度就达到了O(n)了。
然后就是二叉搜索树的插入操作，我们怎么把数据插入到原来的二叉搜索树当中呢？插入的操作和查找有点类似，需要搜索到需要查找的位置。具体逻辑为：当树空的时候直接new一个结点即可，不空的情况下，当我们要插入一个元素的时候我们需要知道它的前一个元素，这样我们才能实现插入操作，插入的位置都是为空的，所以我们要查找到它适合的位置即可。
二叉搜索树的删除属于最重要的内容，因为它的删除操作可能比较复杂一点，我们在删除某一个结点的时候需要调整，你怎么知道调整后是什么样子的呢？删除前我们还是要进行搜索，找到待删除结点的位置。
这里先说一下删除的步骤：
设待删除结点为 cur, 待删除结点的双亲结点为 parent
一. cur.left == null （要删除结点的左边为空时）
1. cur 是 root，则 root = cur.right
2. cur 不是 root，cur 是 parent.left，则 parent.left = cur.right
3. cur 不是 root，cur 是 parent.right，则 parent.right = cur.right
二. cur.right == null （要删除结点的右边为空时）
1. cur 是 root，则 root = cur.left
2. cur 不是 root，cur 是 parent.left，则 parent.left = cur.left
3. cur 不是 root，cur 是 parent.right，则 parent.right = cur.left
三. cur.left != null && cur.right != null
1. 需要使用替换法进行删除，即在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被 删除节点中，再来处理该结点的删除问题
下面对二叉搜索树进行实现：
1. public class BinarySearchTree { 2. 3. static class TreeNode { 4. public int key; 5. public TreeNode left; 6. public TreeNode right; 7. 8. TreeNode(int key) { 9. this.key = key; 10. } 11. } 12. 13. public TreeNode root; 14. 15. /** 16. * 插入一个元素 17. * @param key 18. */ 19. public boolean insert(int key) { 20. //根结点 21. if(root==null){ 22. root=new TreeNode(key); 23. return true; 24. } 25. 26. //找到需要插入的位置 27. TreeNode cur=root;//找位置 28. TreeNode parent=cur;//插入位置的父节点 29. while(cur!=null){ 30. if(cur.key<key){ 31. parent=cur; 32. cur=cur.right; 33. } else if (cur.key>key) { 34. parent=cur; 35. cur=cur.left; 36. }else{ 37. //不可以插入相同的元素 38. return false; 39. } 40. } 41. //此时cur为空了，这个位置就是插入的位置 42. //这里需要讨论插入到parent的左边还是右边 43. if(key> parent.key){ 44. //插入右边 45. parent.right=new TreeNode(key); 46. }else{ 47. //插入左边 48. parent.left=new TreeNode(key); 49. } 50. return true; 51. } 52. 53. /** 54. * 查找key是否存在 55. * @param key 56. * @return 57. */ 58. public TreeNode search(int key) { 59. TreeNode cur=root; 60. 61. //我们搜索的最差情况为当前结点为空 62. while (cur!=null){ 63. 64. //先判断根结点 65. if(cur.key==key){ 66. return cur; 67. //如果key比结点的key大向右找 68. } else if (cur.key<key) { 69. cur=cur.right; 70. //如果key比结点的key小向左找 71. } else { 72. 73. cur=cur.left; 74. } 75. } 76. //如果cur为空则返回空 77. return null; 78. } 79. //中序遍历 80. public void inOrder(TreeNode root){ 81. 82. if(root==null){ 83. return; 84. } 85. inOrder(root.left); 86. System.out.print(root.key+" "); 87. inOrder(root.right); 88. 89. 90. } 91. 92. 93. /** 94. * 删除key的值 95. * @param key 96. * @return 97. */ 98. public void remove(int key) { 99. 100. TreeNode parent = null; 101. TreeNode cur = root; 102. while (cur != null) { 103. if(cur.key == key) { 104. removeNode(parent,cur); 105. return; 106. }else if(cur.key < key) { 107. parent = cur; 108. cur = cur.right; 109. }else { 110. parent = cur; 111. cur = cur.left; 112. } 113. } 114. } 115. 116. private void removeNode(TreeNode parent,TreeNode cur) { 117. if(cur.left == null) { 118. if(cur == root) { 119. root = cur.right; 120. }else if(cur == parent.left) { 121. parent.left = cur.right; 122. }else { 123. parent.right = cur.right; 124. } 125. }else if(cur.right == null) { 126. if(cur == root) { 127. root = cur.left; 128. } else if (cur == parent.left) { 129. parent.left = cur.left; 130. }else { 131. parent.right = cur.left; 132. } 133. }else { 134. TreeNode target = cur.right; 135. TreeNode targetParent = cur; 136. while (target.left != null) { 137. targetParent = target; 138. target = target.left; 139. } 140. cur.key = target.key; 141. if(target == targetParent.left) { 142. targetParent.left = target.right; 143. }else { 144. targetParent.right = target.right; 145. } 146. } 147. } 148. 149. 150. }
