服务器之家

服务器之家 > 正文

java实现 二叉搜索树功能

时间:2021-05-14 10:31     来源/作者:不懂是非

一、概念

  二叉搜索树也成二叉排序树,它有这么一个特点,某个节点,若其有两个子节点,则一定满足,左子节点值一定小于该节点值,右子节点值一定大于该节点值,对于非基本类型的比较,可以实现comparator接口,在本文中为了方便,采用了int类型数据进行操作。

  要想实现一颗二叉树,肯定得从它的增加说起,只有把树构建出来了,才能使用其他操作。

二、二叉搜索树构建

   谈起二叉树的增加,肯定先得构建一个表示节点的类,该节点的类,有这么几个属性,节点的值,节点的父节点、左节点、右节点这四个属性,代码如下

java" id="highlighter_66631">
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static class node{
    node parent;
    node leftchild;
    node rightchild;
    int val;
    public node(node parent, node leftchild, node rightchild,int val) {
      super();
      this.parent = parent;
      this.leftchild = leftchild;
      this.rightchild = rightchild;
      this.val = val;
    }
    public node(int val){
      this(null,null,null,val);
    }
    public node(node node,int val){
      this(node,null,null,val);
    }
  }

        这里采用的是内部类的写法,构建完节点值后,再对整棵树去构建,一棵树,先得有根节点,再能延伸到余下子节点,那在这棵树里,也有一些属性,比如基本的根节点root,树中元素大小size,这两个属性,如果采用了泛型,可能还得增加comparator属性,或提供其一个默认实现。具体代码如下

?
1
2
3
4
5
6
7
public class searchbinarytree {
  private node root;
  private int size;
  public searchbinarytree() {
    super();
  }
}

三、增加

    当要进行添加元素的时候,得考虑根节点的初始化,一般情况有两种、当该类的构造函数一初始化就对根节点root进行初始化,第二种、在进行第一次添加元素的时候,对根节点进行添加。理论上两个都可以行得通,但通常采用的是第二种懒加载形式。

    在进行添加元素的时候,有这样几种情况需要考虑

       一、添加时判断root是否初始化,若没初始化,则初始化,将该值赋给根节点,size加一。

       二、因为二叉树搜索树满足根节点值大于左节点,小于右节点,需要将插入的值,先同根节点比较,若大,则往右子树中进行查找,若小,则往左子树中进行查找。直到某个子节点。

       这里的插入实现,可以采用两种,一、递归、二、迭代(即通过while循环模式)。

  3.1、递归版本插入

 

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public boolean add(int val){
    if(root == null){
      root = new node(val);
      size++;
      return true;
    }
    node node = getadapternode(root, val);
    node newnode = new node(val);
    if(node.val > val){
      node.leftchild = newnode;
      newnode.parent = node;
    }else if(node.val < val){
      node.rightchild = newnode;
      newnode.parent = node;
    }else{
      // 暂不做处理
    }
    size++;19     return true;
  }
  /**
   * 获取要插入的节点的父节点,该父节点满足以下几种状态之一
   * 1、父节点为子节点
   * 2、插入节点值比父节点小,但父节点没有左子节点
   * 3、插入节点值比父节点大,但父节点没有右子节点
   * 4、插入节点值和父节点相等。
   * 5、父节点为空
   * 如果满足以上5种情况之一,则递归停止。
   * @param node
   * @param val
   * @return
   */
  private node getadapternode(node node,int val){
    if(node == null){
      return node;
    }
    // 往左子树中插入,但没左子树,则返回
    if(node.val > val && node.leftchild == null){
      return node;
    }
    // 往右子树中插入,但没右子树,也返回
    if(node.val < val && node.rightchild == null){
      return node;
    }
    // 该节点是叶子节点,则返回
    if(node.leftchild == null && node.rightchild == null){
      return node;
    }
    if(node.val > val && node.leftchild != null){
      return getadaptarnode(node.leftchild, val);
    }else if(node.val < val && node.rightchild != null){
      return getadaptarnode(node.rightchild, val);
    }else{
      return node;
    }
  }

   使用递归,先找到递归的结束点,再去把整个问题化为子问题,在上述代码里,逻辑大致是这样的,先判断根节点有没有初始化,没初始化则初始化,完成后返回,之后通过一个函数去获取适配的节点。之后进行插入值。

3.2、迭代版本

 

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public boolean put(int val){
    return putval(root,val);
  }
  private boolean putval(node node,int val){
    if(node == null){// 初始化根节点
      node = new node(val);
      root = node;
      size++;
      return true;
    }
    node temp = node;
    node p;
    int t;
    /**
     * 通过do while循环迭代获取最佳节点,
     */
    do{
      p = temp;
      t = temp.val-val;
      if(t > 0){
        temp = temp.leftchild;
      }else if(t < 0){
        temp = temp.rightchild;
      }else{
        temp.val = val;
        return false;
      }
    }while(temp != null);
    node newnode = new node(p, val);
    if(t > 0){
      p.leftchild = newnode;
    }else if(t < 0){
      p.rightchild = newnode;
    }
    size++;
    return true;
  }

原理其实和递归一样,都是获取最佳节点,在该节点上进行操作。

论起性能,肯定迭代版本最佳,所以一般情况下,都是选择迭代版本进行操作数据。

四、删除

    可以说在二叉搜索树的操作中,删除是最复杂的,要考虑的情况也相对多,在常规思路中,删除二叉搜索树的某一个节点,肯定会想到以下四种情况,

 java实现 二叉搜索树功能

   1、要删除的节点没有左右子节点,如上图的d、e、g节点

   2、要删除的节点只有左子节点,如b节点

   3、要删除的节点只有右子节点,如f节点

   4、要删除的节点既有左子节点,又有右子节点,如 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节点。那采用哪一种呢,如果删除节点为根节点,又该怎么删除?

 对于第四种情况,可以这样想,找到c或者a节点的后继节点,删除后继节点,且将后继节点的值设置为c或a节点的值。先来补充下后继节点的概念。

一个节点在整棵树中的后继节点必满足,大于该节点值得所有节点集合中值最小的那个节点,即为后继节点,当然,也有可能不存在后继节点。

但是对于第四种情况,后继节点一定存在,且一定在其右子树中,而且还满足,只有一个子节点或者没有子节点两者情况之一。具体原因可以这样想,因为后继节点要比c节点大,又因为c节点左右子节一定存在,所以一定存在右子树中的左子节点中。就比如c的后继节点是f,a的后继节点是e。

有了以上分析,那么实现也比较简单了,代码如下

 

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
public boolean delete(int val){
    node node = getnode(val);
    if(node == null){
      return false;
    }
    node parent = node.parent;
    node leftchild = node.leftchild;
    node rightchild = node.rightchild;
    //以下所有父节点为空的情况,则表明删除的节点是根节点
    if(leftchild == null && rightchild == null){//没有子节点
      if(parent != null){
        if(parent.leftchild == node){
          parent.leftchild = null;
        }else if(parent.rightchild == node){
          parent.rightchild = null;
        }
      }else{//不存在父节点,则表明删除节点为根节点
        root = null;
      }
      node = null;
      return true;
    }else if(leftchild == null && rightchild != null){// 只有右节点
      if(parent != null && parent.val > val){// 存在父节点,且node位置为父节点的左边
        parent.leftchild = rightchild;
      }else if(parent != null && parent.val < val){// 存在父节点,且node位置为父节点的右边
        parent.rightchild = rightchild;
      }else{
        root = rightchild;
      }
      node = null;
      return true;
    }else if(leftchild != null && rightchild == null){// 只有左节点
      if(parent != null && parent.val > val){// 存在父节点,且node位置为父节点的左边
        parent.leftchild = leftchild;
      }else if(parent != null && parent.val < val){// 存在父节点,且node位置为父节点的右边
        parent.rightchild = leftchild;
      }else{
        root = leftchild;
      }
      return true;
    }else if(leftchild != null && rightchild != null){// 两个子节点都存在
      node successor = getsuccessor(node);// 这种情况,一定存在后继节点
      int temp = successor.val;
      boolean delete = delete(temp);
      if(delete){
        node.val = temp;
      }
      successor = null;
      return true;
    }
    return false;
  }
  
  /**
   * 找到node节点的后继节点
   * 1、先判断该节点有没有右子树,如果有,则从右节点的左子树中寻找后继节点,没有则进行下一步
   * 2、查找该节点的父节点,若该父节点的右节点等于该节点,则继续寻找父节点,
   *  直至父节点为null或找到不等于该节点的右节点。
   * 理由,后继节点一定比该节点大,若存在右子树,则后继节点一定存在右子树中,这是第一步的理由
   *   若不存在右子树,则也可能存在该节点的某个祖父节点(即该节点的父节点,或更上层父节点)的右子树中,
   *   对其迭代查找,若有,则返回该节点,没有则返回null
   * @param node
   * @return
   */
  private node getsuccessor(node node){
    if(node.rightchild != null){
      node rightchild = node.rightchild;
      while(rightchild.leftchild != null){
        rightchild = rightchild.leftchild;
      }
      return rightchild;
    }
    node parent = node.parent;
    while(parent != null && (node == parent.rightchild)){
      node = parent;
      parent = parent.parent;
    }
    return parent;
  }

具体逻辑,看上面分析,这里不作文字叙述了,

除了这种实现,在算法导论书中,提供了另外一种实现。

 

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public boolean remove(int val){
    node node = getnode(val);
    if(node == null){
      return false;
    }
    if(node.leftchild == null){// 1、左节点不存在,右节点可能存在,包含两种情况 ,两个节点都不存在和只存在右节点
      transplant(node, node.rightchild);
    }else if(node.rightchild == null){//2、左孩子存在,右节点不存在
      transplant(node, node.leftchild);
    }else{// 3、两个节点都存在
      node successor = getsuccessor(node);// 得到node后继节点
      if(successor.parent != node){// 后继节点存在node的右子树中。
        transplant(successor, successor.rightchild);// 用后继节点的右子节点替换该后继节点
        successor.rightchild = node.rightchild;// 将node节点的右子树赋给后继节点的右节点,即类似后继与node节点调换位置
        successor.rightchild.parent = successor;// 接着上一步 给接过来的右节点的父引用复制
      }
      transplant(node, successor);
      successor.leftchild = node.leftchild;
      successor.leftchild.parent = successor;
    }
    return true;
  }
  /**
   * 将child节点替换node节点
   * @param root  根节点
   * @param node  要删除的节点
   * @param child  node节点的子节点
   */
  private void transplant(node node,node child){
    /**
     * 1、先判断 node是否存在父节点
     *  1、不存在,则child替换为根节点
     *  2、存在,则继续下一步
     * 2、判断node节点是父节点的那个孩子(即判断出 node是右节点还是左节点),
     *  得出结果后,将child节点替换node节点 ,即若node节点是左节点 则child替换后 也为左节点,否则为右节点
     * 3、将node节点的父节点置为child节点的父节点
     */
    
    if(node.parent == null){
      this.root = child;
    }else if(node.parent.leftchild == node){
      node.parent.leftchild = child;
    }else if(node.parent.rightchild == node){
      node.parent.rightchild = child;
    }
    if(child != null){
      child.parent = node.parent;
    }
  }

五、查找

  查找也比较简单,其实在增加的时候,已经实现了。实际情况中,这部分可以抽出来单独方法。代码如下

 

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public node getnode(int val){
    node temp = root;
    int t;
    do{
      t = temp.val-val;
      if(t > 0){
        temp = temp.leftchild;
      }else if(t < 0){
        temp = temp.rightchild;
      }else{
        return temp;
      }
    }while(temp != null);
    return null;
  }

六、二叉搜索树遍历

  在了解二叉搜索树的性质后,很清楚的知道,它的中序遍历是从小到大依次排列的,这里提供中序遍历代码

?
1
2
3
4
5
6
7
8
9
10
public void print(){
    print(root);
  }
  private void print(node root){
    if(root != null){
      print(root.leftchild);
      system.out.println(root.val);// 位置在中间,则中序,若在前面,则为先序,否则为后续
      print(root.rightchild);
    }
  }

总结

以上所述是小编给大家介绍的java实现 二叉搜索树功能,希望对大家有所帮助,如果大家有任何疑问欢迎给我留言,小编会及时回复大家的!

原文链接:https://www.cnblogs.com/qm-article/p/9279655.html

标签:

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
2021德云社封箱演出完整版 2021年德云社封箱演出在线看
2021德云社封箱演出完整版 2021年德云社封箱演出在线看 2021-03-15
返回顶部