二叉查找树（二）

心已赠人 2021-11-22 05:48 348阅读 0赞

在上一篇中，我们说到了二叉树的性质，存储以及定义的结点，有了这些之后，我们便可以来创建一棵二叉查找树了。

首先，我们知道，按照我们定义的存储结构，如果我们知道了整棵树的根结点，那么我们就可以访问到整棵树的所有结点了，因此，将二叉树的类写成如下形式：

1 /**
     2  * 二叉查找树
     3  * @author Alfred
     4  */
     5 public class BSTree {
     6     //随机化的构造二叉查找树
     7     private Random rand = null;
     8     //根结点
     9     private TreeNode rootNode = null;
    10     
    11     /**
    12      * 以int数组A来创建二叉查找树
    13      * @param A int数组
    14      */
    15     public BSTree(int[] A){
    16         rand = new Random();
    17         createBSTree(A);
    18     }
    19     
    20     /**
    21      * 创建二叉查找树
    22      * @param A int数组
    23      */
    24     private void createBSTree(int[] A){}
    25 }

代码里边包含一个Random类的对象（这个对象时我自己加上去的，可以没有，原因之后解释）和一个根结点，我们假设用一个整数的数组来创建一棵二叉查找树。我们知道，二叉查找树是要满足二叉查找树的性质的，那么该如何构造一个满足二叉查找树性质的树呢。在这里，我们使用插入的方法，将整数数组里边的整数一个一个的插入到我们要构建的二叉查找树里面，在插入元素的时候，要保证满足二叉查找树的性质，因此我们要处理两个问题：

1.假如插入的元素已在数中存在，则该如何处理。

2.如何插入才能最大程度上避免出现最坏的情况。

对于第一个问题，在这里的处理是将相同的结点都存在一个位置上，即合并为树中的一个结点，看下上篇的结点定义便知，定义中的dataNum就是记录的是相同结点的个数。

对于第二个问题，首先来说一下最坏的情况是啥，想象一下，最坏的情况莫过于数组已排好序，构建的二叉查找树退化为一个直链。那该如何处理呢？如果我们在插入的时候随机的选择一个数，而不是按照既定的顺序来获取数组中的数，那么我们就可以做到尽可能的避免最坏情况的发生了。

好了，插入的代码如下：

1 /**
     2      * 插入一个整数
     3      * @param z 整数
     4      */
     5     public void TreeInsert(int z){
     6         TreeNode parentNode = null;
     7         TreeNode searchNode = rootNode;
     8         TreeNode insertNode = new TreeNode(z);
     9         //while循环找到要插入的点的父结点
    10         while(searchNode != null){
    11             parentNode = searchNode;
    12             if(insertNode.getKey() < searchNode.getKey()){
    13                 searchNode = searchNode.getLeft();
    14             }else if(insertNode.getKey() == searchNode.getKey()){
    15                 //如果是key值相同的话，直接插入，偷懒在这里...
    16                 searchNode.incNumByOne();
    17                 return;
    18             }else{
    19                 searchNode = searchNode.getRight();
    20             }
    21         }
    22         
    23         insertNode.setParent(parentNode);
    24         if(parentNode == null){
    25             rootNode = insertNode;
    26         }else if(insertNode.getKey() < parentNode.getKey()){
    27             //插入左结点
    28             parentNode.setLeft(insertNode);
    29         }else if(insertNode.getKey() == parentNode.getKey()){
    30             //因为上面插入了，所以这里就不会执行了。
    31             parentNode.incNumByOne();
    32             System.out.println("this is not supposed to be executed.");
    33         }else{
    34             //插入右结点
    35             parentNode.setRight(insertNode);
    36         }
    37     }

插入的代码很简单，第一个while循环找到，我们要插入的结点的父结点，然后接下来将其插入。在这里要注意的地方是，假如树中已有一个或多个元素与待插入的元素相同，那么这里的处理是将其放到相同的结点位置上，即只将这个重复结点的dataNum自加一下即可，在TreeNode里边定义的偷懒的方法，这里就派上用场了。

那么如何实现随机呢，我也没想到什么特别好的方法，可以参考我写的下一段代码：

1 /**
     2      * 创建二叉查找树
     3      * @param A int数组
     4      */
     5     private void createBSTree(int[] A){
     6         //先构建一个存储数组下标的List
     7         List<Integer> index = new LinkedList<Integer>();
     8         int i = 0;
     9         for(i = 0; i < A.length; i++){
    10             index.add(i);
    11         }
    12         //随机构造二叉树
    13         for(i = 0; i < A.length; i++){
    14             int j = 0;
    15             if(index.size() > 1){
    16                 //随机产生一个数组下标值
    17                 j = rand.nextInt(index.size() - 1);
    18             }
    19             //插入二叉树
    20             TreeInsert(A[index.get(j)]);
    21             //移除下标
    22             index.remove(j);
    23         }
    24     }

上面的代码中，先创建了一个存储数组下标的List，然后在插入的时候，随机的从这个List里面选择一个下标，取出该数组下标的数，插入到二叉查找树中，然后将次下标从List中移除，这样下一个循环就不会产生此次产生的下标了。这样就实现了随机化的构造二叉查找树。

好了，有了上面写的几个方法，BSTree这个类就完成了二叉查找树的插入操作和构建二叉查找树的任务了。

转载于:https://www.cnblogs.com/unpolishedgem/archive/2012/05/10/2494403.html