本篇内容介绍了“Java怎么实现二叉搜索树”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

它是一颗二叉树

任一节点的左子树上的所有节点的值一定小于该节点的值

任一节点的右子树上的所有节点的值一定大于该节点的值

特点： 二叉搜索树的中序遍历结果是有序的（升序）！

实现二叉搜索树，将实现插入，删除，查找三个方面

二叉搜索树的节点是不可以进行修改的，如果修改，则可能会导致搜索树的错误

二叉搜索树的节点类 —— class Node

二叉搜索树的属性：要找到一颗二叉搜索树只需要知道这颗树的根节点。

publicclassBST{staticclassNode{privateintkey;privateNodeleft;privateNoderight;publicNode(intkey){this.key=key;}}privateNoderoot;//BST的根节点}二叉搜索树的查找

二叉搜索树的查找思路：

①如果要查找的值等于当前节点的值，那么，就找到了

②如果要查找的值小于当前节点的值，那么，就往当前节点的左子树走

③如果要查找的值大于当前节点的值，那么，就往当前节点的右子树走

最终，如果走到空了还没有找到，就说明不存在这个key

/***查找是否存在节点**思路：根据二叉排序树的特点：*①如果要查找的值小于当前节点的值，那么，就往当前节点的左子树走*②如果要查找的值大于当前节点的值，那么，就往当前节点的右子树走**@paramkey带查找的key*@returnboolean是否存在*/publicbooleanfind(intkey){Nodecur=root;while(cur!=null){if(key<root.key){cur=cur.left;}elseif(key>root.key){cur=cur.right;}else{returntrue;}}returnfalse;}二叉搜索树的插入

二叉搜索树的插入思路：

思路和查找一样的，只是我们这次要进行的是插入操作，那么我们还需要一个parent节点，来时刻记录当前节点的双亲节点即：

①如果要插入的值等于当前节点的值，那么，无法插入（不可出现重复的key）

②如果要插入的值小于当前节点的值，那么，就往当前节点的左子树走

③如果要插入的值大于当前节点的值，那么，就往当前节点的右子树走

最终，如果走到空了，就说明不存在重复的key，只要往双亲节点的后面插就好了，就是合适的位置，具体往左边还是右边插入，需要比较待插入节点的key和parent的key

/***往二叉树中插入节点**思路如下：**@paramkey待插入的节点*/publicvoidinsert(intkey){if(root==null){//如果是空树，那么，直接插入root=newNode(key);return;}Nodecur=root;Nodeparent=null;//parent为cur的父节点while(true){if(cur==null){//在遍历过程中，找到了合适是位置，就指针插入（没有重复节点）if(parent.key<key){parent.right=newNode(key);}else{parent.left=newNode(key);}return;}if(key<cur.key){parent=cur;cur=cur.left;}elseif(key>cur.key){parent=cur;cur=cur.right;}else{thrownewRuntimeException("插入失败，已经存在key");}}}二叉搜索树的删除

二叉搜索树的删除思路：（详细的思路看注释）

首先，需要先找到是否存在key节点，如果存在，则删除，如果不存在则删除错误

对于，如果存在，则分为三种情况：

①要删除的节点，没有左孩子

Ⅰ：要删除的节点为根节点：root = delete.right;
Ⅱ：要删除的节点为其双亲节点的左孩子：parent.left = delete.right;
Ⅲ：要删除的节点为其双亲节点的右孩子：parent.right = delete.right;

②要删除的节点，没有右孩子

Ⅰ：要删除的节点为根节点：root = delete.left;
Ⅱ：要删除的节点为其双亲节点的左孩子：parent.left = delete.left;
Ⅲ：要删除的节点为其双亲节点的右孩子：parent.right = delete.left;

③要删除的节点，既有左孩子又有右孩子：

此时我们需要找到整颗二叉树中第一个大于待删除节点的节点，然后替换他俩的值，最后，把找到的节点删除
Ⅰ：找到的节点的双亲节点为待删除的节点：delete.key = find.key; findParent.right = find.right;
Ⅱ：找到的节点的双亲节点不是待删除的节点：delete.key = find.key; findParent.left = find.right;

/***删除树中节点**思路如下：**@paramkey待删除的节点*/publicvoidremove(intkey){if(root==null){thrownewRuntimeException("为空树，删除错误！");}Nodecur=root;Nodeparent=null;//查找是否key节点的位置while(cur!=null){if(key<cur.key){parent=cur;cur=cur.left;}elseif(key>cur.key){parent=cur;cur=cur.right;}else{break;}}if(cur==null){thrownewRuntimeException("找不到key，输入key不合法");}//cur为待删除的节点//parent为待删除的节点的父节点/**情况1：如果待删除的节点没有左孩子*其中*①待删除的节点有右孩子*②待删除的节点没有右孩子*两种情况可以合并*/if(cur.left==null){if(cur==root){//①如果要删除的是根节点root=cur.right;}elseif(cur==parent.left){//②如果要删除的是其父节点的左孩子parent.left=cur.right;}else{//③如果要删除的节点为其父节点的右孩子parent.right=cur.right;}}/**情况2:如果待删除的节点没有右孩子**其中:待删除的节点必定存在左孩子*/elseif(cur.right==null){//①如果要删除的是根节点if(cur==root){root=cur.left;}elseif(cur==parent.left){//②如果要删除的是其父节点的左孩子parent.left=cur.left;}else{//③如果要删除的节点为其父节点的右孩子parent.right=cur.left;}}/**情况3:如果待删除的节点既有左孩子又有右孩子**思路:*因为是排序二叉树,要找到整颗二叉树第一个大于该节点的节点,只需要,先向右走一步,然后一路往最左走就可以找到了*因此:*①先向右走一步*②不断向左走*③找到第一个大于待删除的节点的节点,将该节点的值,替换到待删除的节点*④删除找到的这个节点*⑤完成删除**/else{NodenextParent=cur;//定义父节点,初始化就是待删除的节点Nodenext=cur.right;//定义next为当前走到的节点,最终目的是找到第一个大于待删除的节点while(next.left!=null){nextParent=next;next=next.left;}cur.key=next.key;//找到之后,完成值的替换if(nextParent==cur){//此时的父节点就是待删除的节点,那么说明找到的节点为父节点的右孩子(因为此时next只走了一步)nextParent.right=next.right;}else{//此时父节点不是待删除的节点,即next确实往左走了,且走到了头.nextParent.left=next.right;}}}

“Java怎么实现二叉搜索树”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站，小编将为大家输出更多高质量的实用文章！