转载

二叉搜索树的Java实现

为了更加深入了解二叉搜索树,博主自己用Java写了个二叉搜索树,有兴趣的同学可以一起探讨探讨。

首先,二叉搜索树是啥?它有什么用呢?

二叉搜索树, 也称二叉排序树,它的每个节点的数据结构为1个父节点指针,1个左孩子指针,1个有孩子指针,还有就是自己的数据部分了,因为只有左右两孩子,所以才叫二叉树,在此基础上,该二叉树还满足另外一个条件:每个结点的左孩子都不大于该结点&&每个结点的右孩子都大于该结点。这样,我们队这棵树进行中序遍历,就能把key从小到大排序了……

那么问题来了,我都有线性表有链表了,我还要它干啥?两个字! 效率

相比线性表,你要搜索一个key,就要执行一次线性时间,算法复杂度为O(n);而用二叉搜索树,算法效率是O(lgn)!这是很诱人的数字。下面我用Java实现以下二叉搜索树,你自然就明白为什么算法复杂度是O(lgn)了。

其次,写一个数据结构,自然而然也要实现对这个数据结构的增、删、查、改了。

下面是我的思路:

  1. 创建树:我是通过一个一个结点的插入来建立一棵二叉搜索树。
  2. 搜索结点:从根节点开始,进行key的比较,小了就往左走,大了就往右走,最后到了叶子结点都还没有的话,那么该树就不存在要搜索的结点了。
  3. 修改结点:修改其实就是查询,在查询之后把结点的数据部分给改了而已,这里我就不重复去实现了。
  4. 删除结点:这个应该就是最难的了,所以我有必要详细讲,先上图(不好意思,懒得用软件画图了,将就将就下哈):

二叉搜索树的Java实现

当我们要删除一个结点时,分如下几种情况:

  • 此结点是叶子结点,这个最简单啦,直接把结点给释放掉就行了。(如图删除9)
  • 此结点只有左孩子,这个也简单啦,直接把左子树替换过来就行了。(如图删除3)
  • 此结点只有右孩子,同上。(如图删除8)
  • 此结点有左右孩子,当出现这种情况时(如图删除7),我们就要找出该结点的 后继结点 (因为右子树肯定存在,所以找肯定在右子树中),然后把这个后继结点替换到要删除的结点中,然后继续执行对这个后继结点的删除操作(递归删除操作就行了)。

发现没?现在我的解题思路是自顶向下去分析…… 自顶向下,逐级求精 是一个很伟大的思想!

现在问题来了! 后继结点 怎么求?我们来分析一下,当求一个结点的后继结点时,分为以下两种情况:

  • 当该结点有右孩子时,后继结点就在右子树中,就是该右子树的 最小结点
  • 当该结点没有右孩子时,那后继结点就满足这个条件:该后继结点是该结点的祖先&&该结点位于该结点的左子树中(如图中的9的后继结点是12)

哎呀呀!问题又来了! 最小结点 咋办!很简单!

当求一棵树的最小结点时,那么就要从这颗树的根节点开始,一直往左子树走,就能找到它的最小结点了!

好了,现在问题逐步解决了!删除结点的功能也就完成了!

最后, 没代码说个锤子 ,咱上代码!

首先,写个测试类:

二叉搜索树的Java实现
 1 public class Test {  2     public static void main(String[] args) {  3         int[] datas={12,4,5,7,4,8,3,2,6,9};  4         BinTree tree=new BinTree(datas);  5         tree.preOrderTraverse();//先序遍历  6         tree.midOrderTraverse();//中序遍历  7         tree.postOrderTraverse();//后序遍历  8         tree.insert(15);    //插入结点  9         tree.search(7);        //查询结点 10         tree.search(100);    //查询一个不存在的结点 11         tree.getMax();        //获取最大值 12         tree.getMin();        //获取最小值 13         tree.getPre(7);        //前驱结点 14         tree.getPre(2);        //最前的前驱结点 15         tree.getPost(7);    //后继结点 16         tree.getPost(15);    //最后的后继结点 17         tree.delete(5);        //删除结点 18         tree.delete(0);        //删除一个不存在的结点 19     } 20 }
View Code

然后,二叉搜索树:

  1 public class BinTree {   2     Node root=null;   3     private class Node{   4         Node parent=null;   5         Node leftChild=null;   6         Node rightChild=null;   7         int key;   8         public Node(int data) {   9             this.key=data;  10         }  11     }  12     public BinTree(int[] datas) {  13         buildTree(datas);  14     }  15     private void buildTree(int[] datas) {  16         for (int i = 0; i < datas.length; i++) {  17             Node node=new Node(datas[i]);  18             insertNode(node);  19         }  20     }  21     private void insertNode(Node node) {    //插入结点  22         Node next=this.root;      23         Node cur=null;    //用来保存当前结点  24         while(next!=null){    //当到达叶子结点时,确认位置!  25             cur=next;  26             if(node.key>=cur.key){  27                 next=next.rightChild;  28             }else{  29                 next=next.leftChild;  30             }  31         }  32         node.parent=cur;    //插入该结点!  33         if(cur==null){  34             this.root=node;  //该树为空树,所以这个是根节点  35         }else if(node.key>=cur.key){  36             cur.rightChild=node;  37         }else{  38             cur.leftChild=node;  39         }  40     }  41     /*  42      * 插入一个数  43      */  44     public void insert(int data){      45         Node node=new Node(data);  46         System.out.println("插入结点:"+data);  47         insertNode(node);  48         this.midOrderTraverse();  49     }  50       51     /*  52      * 先序遍历  53      */  54     public void preOrderTraverse(){      55         System.out.println("先序遍历:");  56         preOrderTraverse(root);  57         System.out.println();  58     }  59     private void preOrderTraverse(Node node){    //先序遍历  60         if(node!=null){  61             System.out.print("-"+node.key+"-");  62             preOrderTraverse(node.leftChild);  63             preOrderTraverse(node.rightChild);  64         }  65     }  66     /*  67      * 中序遍历  68      */  69     public void midOrderTraverse(){      70         System.out.println("中序遍历:");  71         midOrderTraverse(root);  72         System.out.println();  73     }  74     private void midOrderTraverse(Node node){    //中序遍历  75         if(node!=null){  76             midOrderTraverse(node.leftChild);  77             System.out.print("-"+node.key+"-");  78             midOrderTraverse(node.rightChild);  79         }  80           81     }  82       83     /*  84      * 后序遍历  85      */  86     public void postOrderTraverse(){  87         System.out.println("后序遍历:");  88         postOrderTraverse(root);  89         System.out.println();  90     }  91     private void postOrderTraverse(Node node){     //后序遍历  92         if(node!=null){  93             System.out.print("-"+node.key+"-");  94             postOrderTraverse(node.leftChild);  95             postOrderTraverse(node.rightChild);  96         }  97     }  98       99     /* 100      * 搜索结点 101      */ 102     public void search(int data){     103         System.out.println("您要查找的是:"+data); 104         Node node; 105         if((node=searchNode(new Node(data)))==null){ 106             System.out.println("树中没有该结点!"); 107         }else{ 108             System.out.println("查找"+node.key+"成功!"); 109         } 110     } 111      112     private Node searchNode(Node node){    //private供内部调用,搜索结点 113         if(node==null){ 114             System.out.println("输入为空,查找失败!"); 115         }else{ 116             if(root==null){ 117                 System.out.println("该树为空树!"); 118             }else{                        //开始查找 119                 boolean isFound=false;     120                 Node x=root; 121                 Node y=null; 122                 while(!isFound&&x!=null){    //当查到或者到了叶子节点还没查到时,终结! 123                     y=x; 124                     if(node.key==x.key){     125                         isFound=true; 126                     }else{                    //通过比较大小往下面查找 127                         if(node.key>x.key){     128                             x=x.rightChild; 129                         }else{ 130                             x=x.leftChild; 131                         } 132                     } 133                 } 134                 if(isFound){    //没找到的话,在最后返回null 135                     return y; 136                 } 137             } 138         } 139         return null; 140     } 141      142     /* 143      * 获取最大值 144      */ 145     public void  getMax(){     146         Node node; 147         if((node=getMaxNode(root))==null){ 148             System.out.println("该树为空!"); 149         }else{ 150             System.out.println("最大的结点是:"+node.key); 151         } 152          153     } 154      155     private Node getMaxNode(Node node){    //获取最大值 156         if(node!=null){ 157             Node x=node; 158             Node y=null; 159             while(x!=null){    //一直往右遍历直到底就是最大值了! 160                 y=x; 161                 x=x.rightChild; 162             } 163             return y; 164         } 165         return null; 166     } 167      168     /* 169      * 获取最小值 170      */ 171     public void getMin(){     172         Node node; 173         if((node=getMinNode(root))==null){ 174             System.out.println("该树为空!"); 175         }else{ 176             System.out.println("最小的结点是:"+node.key); 177         } 178     } 179     private Node getMinNode(Node node){    //获取最小值 180         if(node!=null){ 181             Node x=node; 182             Node y=null; 183             while(x!=null){    //一直往左遍历直到底就是最小值了! 184                 y=x; 185                 x=x.leftChild; 186             } 187             return y; 188         } 189         return null; 190     } 191      192     /* 193      * 获取前驱结点 194      */ 195     public void getPre(int data){     196         Node node=null; 197         System.out.println(data+"的前驱结点:"); 198         if((node=getPreNode(searchNode(new Node(data))))==null){ 199             System.out.println("该结点不存在或无前驱结点!"); 200         }else{ 201             System.out.println(data+"的前驱结点为:"+node.key); 202         } 203     } 204      205     private Node getPreNode(Node node){    //获取前驱结点 206         if(node==null){ 207             return null; 208         } 209         if(node.leftChild!=null){    //当有左孩子时,前驱结点就是左子树的最大值 210             return getMaxNode(node.leftChild); 211         }else{//当不存在左孩子时,前驱结点就是——它的祖先,而且,它在这个祖先的右子树中。这句话自己画图就能理解了 212             Node x=node; 213             Node y=node.parent; 214             while(y!=null&&x==y.leftChild){ 215                 x=y; 216                 y=y.parent; 217             } 218             return y; 219         } 220     } 221      222     /* 223      * 获取后继结点 224      */ 225     public void getPost(int data){     226         Node node=null; 227         System.out.println(data+"的后继结点:"); 228         if((node=getPostNode(searchNode(new Node(data))))==null){ 229             System.out.println("该结点不存在或无后继结点!"); 230         }else{ 231             System.out.println(data+"的后继结点为:"+node.key); 232         } 233     } 234      235     private Node getPostNode(Node node){    //获取后继结点 236         if(node==null){ 237             return null; 238         } 239         if(node.rightChild!=null){    //当有右孩子时,前驱结点就是右子树的最小值 240             return getMinNode(node.rightChild); 241         }else{//当不存在右孩子时,后继结点就是——它的祖先,而且,它在这个祖先的左子树中。这句话自己画图就能理解了 242             Node x=node; 243             Node y=node.parent; 244             while(y!=null&&x==y.rightChild){ 245                 x=y; 246                 y=y.parent; 247             } 248             return y; 249         } 250     } 251      252      253     /* 254      * 删除结点 255      */ 256     public void delete(int data){     257         Node node; 258         if((node=searchNode(new Node(data)))==null){//注意!这里不能new结点!你必须从树中找该结点!new就是初始化了 259             System.out.println("二叉树中不存在此结点!"); 260             return; 261         } 262         deleteNode(node); 263         System.out.println("删除结点"+data+"后:"); 264         this.midOrderTraverse(); 265     } 266      267      268     private void deleteNode(Node node){ 269         if(node==null){ 270             System.out.println("删除结点不能为空!"); 271             return; 272         } 273         replacedNode(node); 274     } 275      276     private void replacedNode(Node node) {    //替换结点 277         if(node.leftChild!=null 278                 &&node.rightChild!=null){    //当有左右孩子时,用后继结点替换 279             replacedNodeOfPost(node); 280         } 281         else 282         { 283             if(node.leftChild!=null){    //当只有左孩子时,直接用左子树替换 284                 node=node.leftChild; 285             }else if(node.rightChild!=null){    //只有右孩子时,直接有子树替换 286                 node=node.rightChild; 287             }else{            //当没有左右孩子时,就直接释放了这个结点 288                 freeNode(node); 289             } 290         } 291     } 292      293      294     private void freeNode(Node node) {    //释放该结点,断掉其与父结点的链接 295         if(node==node.parent.leftChild){ 296             node.parent.leftChild=null; 297         }else{ 298             node.parent.rightChild=null; 299         } 300     } 301      302     private void replacedNodeOfPost(Node node) {     303         Node y=this.getPostNode(node);    //找后继结点 304         node.key=y.key; 305         replacedNode(y);    //替换了key之后,再一次递归把现在这个结点给替换了! 306     } 307      308 }
最后是测试结果:

------------------分割线-------------------------

先序遍历:

-12--4--3--2--5--4--7--6--8--9-

中序遍历:

-2--3--4--4--5--6--7--8--9--12-

后序遍历:

-12--4--3--2--5--4--7--6--8--9-

插入结点:15

中序遍历:

-2--3--4--4--5--6--7--8--9--12--15-

您要查找的是:7

查找7成功!

您要查找的是:100

树中没有该结点!

最大的结点是:15

最小的结点是:2

7的前驱结点:

7的前驱结点为:6

2的前驱结点:

该结点不存在或无前驱结点!

7的后继结点:

7的后继结点为:8

15的后继结点:

该结点不存在或无后继结点!

删除结点5后:

中序遍历:

-2--3--4--4--6--7--8--9--12--15-

二叉树中不存在此结点!

正文到此结束
Loading...