二叉排序树（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 (keyp.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）定义二叉排序树的删除方法：
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
以上代码通过三种方法实现了二叉树的删除，deleteBST(int key)是提供给用户的删除方法，会调deleteBST(Node node, int key)，其中Node参数为根节点，表示从根节点开始递归查找和删除；deleteBST(Node node, int key)通过递归查找找到要删除的节点。查找要删除的节点的具体做法如下。
◎ 如果key和当前节点的值相等，则说明找到了需要删除的节点。
◎ 如果key小于当前节点的值，则在左子树中查找。
◎ 如果key大于当前节点的值，则在右子树中查找。
在找到要删除的节点后，调用delete(Node node)删除该节点，这里的删除分3种情况。
◎ 如果右子树为空，则只需将它的左子树接到该节点。
◎ 如果右子树为空，则只需将它的右子树接到该节点。
◎ 如果左右子树均不为空，则需要在左子树中寻找最小的节点，并将左子树中最小的节点接到当前节点。
（4）定义二叉排序树的查询方法：
public boolean searchBST(int key){
Node current =root;
while(current !=null){
//等于当前值则查找成功
if(key==current.getValue()){
return true;
}
//若小于 左子树查找
else if(key
以上代码定义了searchBST()用于查询二叉排序树，具体做法如下。
◎ 如果key和当前节点的值相等，则说明找到了该节点。
◎ 如果key小于当前节点的值，则在左子树中查找。
◎ 如果key大于当前节点的值，则在右子树中查找。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）