Java中构建检索树

检索树是二叉检索树的简称，在检索树中任意一个值为a的节点的左子树的值都小于等于a，右子树的值都大于a，所以以中序遍历检索树的时候，其中序序列是有序的（左小右大），简称中序有序（最后会附上完整代码）

检索树的查找

依照检索树的定义，当我们查找x值在检索树里面的位置是，只需要从根节点开始，如果x小于根节点的数据的值就向根节点左子树进行查找，大于就向根节点的右子树查找，直到找到为止

检索树的递归查找算法

public TreeNode sort(int num,TreeNode s){
        if(s == null)return null; //如果s为空的花查找失败，返回null

        if(num < s.num)sort(num,s.Lson);   //如果num值小于节点的值，递归查找左子树
        else if(num > s.num)（sort(num,s.Rson);   //如果num值大于节点的值，递归查找右子树
        else return s;   //如果等于num值返回s
    }

检索树的非递归查找算法

public TreeNode sort(int num,TreeNode s){
        
        while(s != null){
            if(num < s.num)s = s.Lson;  // 如果num小于该节点的值，查找左子树
            else if(num > s.num)s = s.Rson;  // 如果num大于该节点的值，查找右子树
            else return s;   // 如果num等于该节点的值，返回该节点     

        }
        return null;  如果s为空，查找失败返回null
}

查找算法的时间复杂度：

查找检索树时候其时间复杂度取决于节点在树的层次，树的层次在n~之间 ，所以平均时间复杂度为：O（log n）

 检索树的插入

同理我们通过检索树定义，在插入之前需要寻找插入的位置，如果插入的数值小于等于节点值，就向该节点的左子树寻找插入位置，大于就向右子树寻找插入位置，直到节点为空（插入的位置一定是叶子节点）

检索树的插入递归算法

public void Insert(TreeNode s,int num){
        if(s == null) {
            s = new TreeNode(num);  //如果节点为空，就把数值插入这里
            return;
        }
        if(num <= s.num) Insert(s.Lson,num);  //如果num小于等于该节点的值，寻找左子树
        else Insert(s.Rson,num);  //如果num大于该节点的值，寻找右子树
    }

 检索树的插入非递归算法

public void Insert(TreeNode s,int num){
        TreeNode p;   //用来存放插入位置的双亲
        while(s1=null){
            p = s; 
            if(num <= s.num)s = s.Lson;  //num小于节点的值就查找左子树
            else s = s.Rson;   //num值大于节点值查找右子树
        }
        s = new TreeNode(num);  //创建新的节点值为num
        if(p.num >= num)p.Lson = s;  //如果num比双亲p值小，插入的节点就是p的左孩子
        else p.Rson = s;  //否则是右孩子
    }

插入算法的时间复杂度：

检索树插入算法的时间复杂度主要取决于：

1. 查找插入的位置
2. 插入节点 

因此检索树的平均时间复杂度为：O（log n）

检索树的删除

当我们要删除检索树里面某一个节点的时候，首先先要寻找到该节点的位置，然后判断该节点有没有左右孩子（检索树只删除一个节点，删除前后还要保持中序有序），如果没有左右孩子，直接删除该节点就行；如果有左孩子（右孩子）将左孩子值（右孩子）赋值各位该节点然后删除左孩子（右孩子）；如果左右孩子都有，就需要找到该节点的中序前驱节点，将中序前驱（中序遍历的时候排在该节点前面的节点）节点值赋值给该节点删除中序前驱就行

public void deleteNode(int num){
        TreeNode p,q,s,f;
        TreeNode root = new TreeNode();  //root 是虚根，值无穷小
        root.Rson = this;
        p = this;  //p是搜索节点
        f = root; //f指向寻找到的节点的双亲。
        q = null; //q指向搜索到的节点
        while(p != null){    //寻找节点
            
            if(p.num < num){f = p;p = p.Rson;}
            else if(p.num>num){f = p;p = p.Lson;}
            else q= p;
        }
        if(q == null)return;  //如果q == null，就没找到，失败返回
        if(q.Rson == null){   //如果q的右孩子为空，就把q双亲的孩子改成q的左孩子
            if(q == f.Rson) {
                f.Rson = q.Lson;
            }
            else f.Lson = q.Lson;
        }
        else if(q.Lson == null){ //如果q的左孩子为空，就把q双亲的孩子改成q的右孩子
            if(q == f.Rson) {
                f.Rson = q.Rson;
            }
            else f.Lson = q.Rson;
        }
        else {  //如果q的左右孩子都有，就寻找以该节点为根节点的中序前驱节点，然后将q的数据和前驱节点交换一下，删除前驱节点
            s = q.Lson;
            if(s.Rson == null){   //如果s没有右孩子，那么要删除节点的中序前驱节点就是左孩子
                q.num = s.num;
                q.Lson = s.Lson;
                s = null;
            }
            else{  //否则就在右子树里面寻找
                TreeNode m = s;  //m存放前驱节点的双亲
                while(s.Rson!= null){  如果s的右子树为null，说明该节点是前驱节点
                    m = s;
                    s = s.Rson;
                }
                q.num = s.num;  //将前驱节点的值赋值给要删除的节点
                m.Rson = s.Lson; //将前驱节点双亲的右孩子地址赋值为双亲节点的左孩子
                s = null;  //删除前驱节点

            }
        }

    }

root虚根的作用：避免删除根节点

例如如果我们要删除的节点刚好是根节点，那么没有虚根的情况下，根节点删除后就没有引用变量指向根节点的孩子，导致地址丢失

 最后附上完整代码

import java.util.Scanner;
public class TreeNode {
    int num;   //数据域
    TreeNode Lson,Rson;  //类似c语言指针域
    public TreeNode(){}
    public TreeNode(int num){
        this.num = num;
    }
    public void BuildTreeNode(){   //构建检索树
        int num;
        Scanner sc = new Scanner(System.in);
        this.num = sc.nextInt();
        while(true){
            if(num == 0)break;  //当输入的数值为0时退出构建
            num = sc.nextInt();
            Insert(this,num);
            
        }
    }
    public void Insert(TreeNode s,int num){  //插入
        if(s == null) {
            s = new TreeNode(num);
            return;
        }
        if(num <= s.num) Insert(s.Lson,num);
        else Insert(s.Rson,num);
    }
    public TreeNode sort(int num,TreeNode s){  //搜索
        if(s == null)return null;

        if(num < s.num)sort(num,s.Lson);
        else sort(num,s.Rson);
        return s;
    }
    public void deleteNode(int num){   //删除
        TreeNode p,q,s,f;
        TreeNode root = new TreeNode();  //root 是虚根，值无穷小
        root.Rson = this;
        p = this;f = root; //f指向寻找到的节点的双亲。p是搜索节点
        q = null; //q指向搜索到的节点
        while(p != null){    //寻找节点
            f = p;
            if(p.num < num){p = p.Rson;}
            else if(p.num>num){p = p.Lson;}
            else q= p;
        }
        if(q == null)return;  //如果q == null，就没找到，失败返回
        if(q.Rson == null){   //如果q的右孩子为空，就把q双亲的孩子改成q的左孩子
            if(q == f.Rson) {
                f.Rson = q.Lson;
            }
            else f.Lson = q.Lson;
        }
        else if(q.Lson == null){ //如果q的左孩子为空，就把q双亲的孩子改成q的右孩子
            if(q == f.Rson) {
                f.Rson = q.Rson;
            }
            else f.Lson = q.Rson;
        }
        else {  //如果q的左右孩子都有，就寻找以该节点为根节点的中序前驱节点，然后将q的数据和前驱节点交换一下，删除前驱节点
            s = q.Lson;
            if(s.Rson == null){
                q.num = s.num;
                q.Lson = s.Lson;
                s = null;
            }
            else{
                TreeNode m = s;
                while(s.Rson!= null){
                    m = s;
                    s = s.Rson;
                }
                q.num = s.num;
                m.Rson = s.Lson;
                s = null;

            }
        }

    }

    
}

---

删除算法时间复杂度分析：

在检索树删除的时候算法的复杂度主要取决于两个步骤：

1. 查找要删除节点的位置
2. 查找要删除节点的中序前驱节点

所以时间复杂度平均值为O（log n）