做微信的微网站/怎么找百度客服

二叉排序树

二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree）或二叉搜索树。二叉排序树为满足以下条件的树：
◎ 若左子树不空，则左子树上所有节点的值均小于它的根节点的值；
◎ 若右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值；
◎ 左、右子树也分别为二叉排序树。如图4-10所示便是一个二叉排序树。

插入操作

在二叉排序树中进行插入操作时只需找到待插入的父节点，将数据插入即可，具体流程如下。
（1）将待插入的新节点与当前节点进行比较，如果两个节点的值相同，则表示新节点已经存在于二叉排序树中，直接返回false。
（2）将待插入的新节点与当前节点进行比较，如果待插入的新节点的值小于当前节点的值，则在当前节点的左子树中寻找，直到左子树为空，则当前节点为要找的父节点，将新节点插入当前节点的左子树即可。

（3）将待插入的新节点与当前节点进行比较，如果待插入的新节点的值大于当前节点的值，则在当前节点的右子树中寻找，直到右子树为空，则当前节点为要找的父节点，将新节点插入当前节点的右子树即可。具体的插入流程如图4-11所示。

删除操作

二叉排序树的删除操作?要分为三种情况：待删除的节点没有子节点；待删除的节点只有一个子节点；待删除的节点有两个子节点。
具体情况如下。
（1）在待删除的节点没有子节点时，直接删除该节点，即在其父节点中将其对应的子节点置空即可。如图 4-12所示，要删除的节点14没有子节点，则直接将其删除即可。

（2）在待删除的节点只有一个子节点时，使用子节点替换当前节点，然后删除该节点即可。如图 4-13所示，要删除的节点 5有一个子节点 8，则使用子节点 8替换需要删除的节点5，然后删除节点5的数据即可。

（3）在待删除的节点有两个子节点时，首先查找该节点的替换节点（替换节点为左子树中的最大节点或者右子树中的最小节点），然后替换待删除的节点为替换节点，最后删除替换节点。如图 4-14所示，要删除的节点 4有两个子节点，其左子树最小的节点为2，其右子树最小的节点为5，因此有两种结果。

查找操作
二叉排序树的查找方式和效率接近二分查找法，因此可以很容易获取最大（最右最深子节点）值和最小（最左最深子节点）值，具体的查找流程为：将要查找的数据与根节点的值进行比较，如果相等就返回，如果小于就到左子树中递归查找，如果大于就到右子树中递归查找。

代码实现：

首先定义二叉树的数据结构

public class Node {private int value;private Node left;private Node right;public Node(){}public Node(Node left,Node right,int value){this.left=left;this.right=right;this.value=value;}public Node(int value){this(null,null,value);}public int getValue() {return this.value;}public void setValue(int value) {this.value = value;}public Node getLeft() {return this.left;}public void setLeft(Node left) {this.left = left;}public Node getRight() {return this.right;}public void setRight(Node right) {this.right = right;}
}

如上代码定义了二叉排序树的数据结构Node，在Node中包含的value、left、right分别表示二叉排序树的值、左子节点、右子节点。

并有相应的get set方法

（2）定义二叉树的插入方法：

   public void insertBST(int key){//设置一个父节点Node p =root;//prev 是待插入节点的父节点Node prev=null;while (p!=null){prev=p;if (key<p.getValue()){p=p.getLeft();}else if(key>p.getValue()){p=p.getRight();}else {return;}}//最终决定插入哪里if (root==null){root=new Node(key);}else if(key< prev.getValue()){prev.setLeft(new Node(key));}else {prev.setRight(new Node(key));}}

如上代码定义了insertBST()来向二叉排序树中插入节点，具体操作分 4步：①循环查找需要插入的节点prev；②如果二叉树的根节点为null，则说明二叉树是空树，直接将该节点设置为根节点；③如果待插入的数据小于该节点的值，则将其插入该节点的左节点；④如果待插入的数据大于该节点的值，则将其插入该节点的右节点。

（3）定义二叉排序树的删除方法：

   /*** 删除二叉树中的节点* 分为三种情况：（删除节点为*p,其父节点为*f）* （1）要删除的*p节点是叶子节点，只需要修改它的双亲节点的指针为空* （2）若*p只有左子树或者只有右子树，则直接让左子树或者右子树代替*p* （3）若*p又有左子树，又有右子树*         则用p左子树中的最大的值（即最右端S）代替P,删除S,重接其左子树*/public void deleteBST(int key){deleteBST(root,key);}private boolean deleteBST(Node node,int key){if (node==null){return false;}else {if(key==node.getValue()){delete(node);}else if(key<node.getValue()){return deleteBST(node.getLeft(),key);}else {return deleteBST(node.getRight(),key);}}}private boolean delete(Node node){Node temp =null;/*** 右子树为空，那么就重接他的左子树* 如果是叶子节点，那么就删除了*/if(node.getRight()==null){temp=node;node=node.getLeft();}//左子树空，重接他的右子树else if (node.getLeft()==null){temp=node;node=node.getRight();}//左右都不空else{temp=node;Node s =node;//转向左子树，让其向右走到尽头s=s.getLeft();while(s.getRight()!=null){temp=s;s=s.getRight();}node.setValue(s.getValue());if (temp!=node){temp.setRight(s.getLeft());}else {temp.setLeft(s.getLeft());}}return true;}

以上代码通过三种方法实现了二叉树的删除，deleteBST(int key)是提供给用户的删除方法，会调deleteBST(Node node, int key)，其中Node参数为根节点，表示从根节点开始递归查找和删除；deleteBST(Node node, int key)通过递归查找找到要删除的节点。查找要删除的节点的具体做法如下。
◎ 如果key和当前节点的值相等，则说明找到了需要删除的节点。
◎ 如果key小于当前节点的值，则在左子树中查找。
◎ 如果key大于当前节点的值，则在右子树中查找。
在找到要删除的节点后，调用delete(Node node)删除该节点，这里的删除分3种情况。
◎ 如果右子树为空，则只需将它的左子树接到该节点。
◎ 如果右子树为空，则只需将它的右子树接到该节点。
◎ 如果左右子树均不为空，则需要在左子树中寻找最小的节点，并将左子树中最小的节点接到当前节点。
（4）定义二叉排序树的查询方法：

  /*** * 查找二叉排序树是否有key值*/public boolean searchBST(int key){Node current =root;while(current !=null){//等于当前值则查找成功if(key==current.getValue()){return true;}//若小于 左子树查找else if(key<current.getValue()){current=current.getLeft();}else {   //反之，右子树查找current=current.getRight();}}return false;}

以上代码定义了searchBST()用于查询二叉排序树，具体做法如下。
◎ 如果key和当前节点的值相等，则说明找到了该节点。
◎ 如果key小于当前节点的值，则在左子树中查找。
◎ 如果key大于当前节点的值，则在右子树中查找。