java实现二叉搜索树的功能。二叉搜索树的概念也是二叉排序树。它有这样一个特点，如果一个节点有两个子节点，则必须满足。左子节点的值必须小于节点的值，右子节点的值必须大于节点的值。对于非基本类型的比较，可以实现Comparator接口。为了方便，本文使用int类型数据进行操作。如果要完成一棵二叉树，就必须从它的生长开始。树建好后才能使用其他操作。二叉搜索树的构建说到二叉树的添加，首先要构建一个表示节点的类。节点的类有几个属性，节点的值，节点的父节点，左节点，右节点四个属性，代码如下staticclassNode{Nodeparent;节点左孩子；节点rightChild；整数值；publicNode(Nodeparent,NodeleftChild,NoderightChild,intval){super();this.parent=parent;this.leftChild=leftChild;this.rightChild=rightChild;这个.val=val;}publicNode(intval){this(null,null,null,val);}publicNode(Nodenode,intval){this(node,null,null),val);}}复制这里的代码是写在内部类中的。节点值构造完成后，整个树就构造完成了。一棵树必须首先有一个根节点，然后扩展到其余的子节点。在这棵树中，还有一些属性，比如基本的根节点root，树中元素的大小，这两个属性，如果使用泛型，可能要加上Comparator属性，或者提供一个默认的实现.具体代码如下publicclassSearchBinaryTree{privateNoderoot;privateintsize;publicSearchBinaryTree(){super();}}复制代码添加添加元素时，要考虑根节点的初始化。一般有两个，初始化这个类的结构函数时，初始化根节点root。第二种是第一次添加元素时添加根节点。理论上两者都可以，但通常使用第二种懒加载方式。在添加元素的时候，有几种情况需要考虑：1.添加的时候判断根是否初始化。如果不是，则初始化，将值赋给根节点，并将大小加一。2、由于二叉树搜索树满足根节点的值大于左节点小于右节点，所以需要先将插入的值与根节点进行比较。如果它很大，它将在右子树中搜索。如果它很小，它会去左子树。别找了。直到一个子节点。这里的插入可以通过两种方式完成，一是递归，二是迭代（即通过while循环）。递归版本insertpublicbooleanadd(intval){if(root==null){root=newNode(val);尺码++；返回真；}节点node=getAdapterNode(root,val);节点newNode=newNode(val);如果（node.val>val）{node.leftChild=newNode;newNode.parent=节点；}elseif(node.valval&&node.leftChild==null){returnnode;}//插入右子树，但没有右子树，同样返回if(node.valval&&node.leftChild!=null){returngetAdaptarNode(node.leftChild,val);}elseif(node.val0）{temp=temp.leftChild;}elseif(t<0){temp=temp.rightChild;}else{temp.val=val;返回假；}}while(temp!=null);节点newNode=newNode(p,val);if(t>0){p.leftChild=newNode;}elseif(t<0){p.rightChild=newNode;}大小++；返回真；}原理其实和递归是一样的，就是获取最好的结点，停止对这个结点的操作。从性能上来说，确定迭代版本最好，所以一般情况下都会选择迭代版本来操作数据。可以说，在二叉查找树的运算中，删除是最复杂的，需要考虑的情况也比较多。在常规思维中，删除二叉搜索树的一个节点时，肯定会想到以下四种情况。1.待删除的节点没有左右子节点，如上图中的D、E、G节点。2、要删除的节点只需要左子节点，比如B节点。被删除的节点既有左子节点也有右子节点，比如A、C节点。对于前三种情况，可以说比较简单，第四种比较复杂。我们先分析第一种情况。比如删除了D节点，可以将B节点的左子节点设置为null。如果删除G节点，可以将F节点的右子节点置为null。具体设置哪一边，看被删除的节点在哪一边。第二种方式是删除节点B，只需要将节点A的左节点设置为节点D，将节点D的父节点设置为A即可。具体设置哪一边取决于父节点的哪一边删除的节点位于。第三种与第二种相同。第四种，前面说的有点复杂，比如删除C节点，将F节点的父节点设置为A节点，将F节点的左节点设置为E节点，并设置A的右节点到F，E的父节点设置F节点（即F节点交换C节点），还有一种E节点直接交换C节点。那么使用哪一个呢？如果被删除的节点是根节点，应该如何删除呢？关于第4种情况，可以这样想，找到C或A节点的后继节点，删除后继节点，将后继节点的值设置为C或A节点的值。我们先添加后继节点的概念。整棵树中某个节点的后继节点必须满足，其值大于所有节点中值最小的节点的节点为后继节点。当然也可以没有后继节点。但是对于第四个条件，后继节点必须存在，并且必须在它的右子树中，也满足，只要只有一个子节点或者没有子节点即可。具体原因可以这样想，因为后继节点比C节点大，又因为C节点的左右子节点一定存在，所以它一定存在于右子树的左子节点中。例如C的后继节点是F，A的后继节点是E。有了上面的分析，实现就比较简单了，代码如下publicbooleandelete(intval){Nodenode=getNode(val);if(node==null){返回false;}节点父节点=node.parent;节点leftChild=node.leftChild;节点rightChild=node.rightChild;//如果后面的父节点都为空，则删除的节点被标记为根节点if(leftChild==null&&rightChild==null){//没有子节点if(parent!=null){if(parent.leftChild==node){parent.leftChild=null;}elseif(parent.rightChild==node){parent.rightChild=null;}}else{//父节点不存在，表示删除的节点为根节点root=null;}节点=空；返回真；}elseif(leftChild==null&&rightChild!=null){//只要是右节点if(parent!=null&&parent.val>val){//有父节点，节点位置为左侧父节点parent.leftChild=rightChild;}elseif(parent!=null&&parent.valval){//有父节点，且节点位置就可以是父节点的左边parent.leftChild=leftChild;}elseif(parent!=null&&parent.val0）{temp=temp.leftChild;}elseif(t<0){temp=temp.rightChild;}else{返回温度；}}while(temp!=null);返回空值；}复制代码二叉查找树遍历了解了二叉查找树的本质后，就清楚了其中序遍历是按照从小到大的顺序排列的，这里是中序遍历代码publicvoidprint(){print（根）;}privatevoidprint(Noderoot){if(root!=null){print(root.leftChild);System.out.println(root.val);//如果位置在中间则为有序，如果在前面则为有序，否则为后续print(root.rightChild);}}
