MyException - 我的异常网
当前位置:我的异常网» 数据结构与算法 » 二叉搜寻树的Java实现

二叉搜寻树的Java实现

www.MyException.Cn  网友分享于:2015-04-16  浏览:0次
二叉搜索树的Java实现

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

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

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

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

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

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

  下面是我的思路:

 

  1. 创建树:我是通过一个一个结点的插入来建立一棵二叉搜索树。
  2. 搜索结点:从根节点开始,进行key的比较,小了就往左走,大了就往右走,最后到了叶子结点都还没有的话,那么该树就不存在要搜索的结点了。
  3. 修改结点:修改其实就是查询,在查询之后把结点的数据部分给改了而已,这里我就不重复去实现了。
  4. 删除结点:这个应该就是最难的了,所以我有必要详细讲,先上图(不好意思,懒得用软件画图了,将就将就下哈):
当我们要删除一个结点时,分如下几种情况:
  • 此结点是叶子结点,这个最简单啦,直接把结点给释放掉就行了。(如图删除9)
  • 此结点只有左孩子,这个也简单啦,直接把左子树替换过来就行了。(如图删除3)
  • 此结点只有右孩子,同上。(如图删除8)
  • 此结点有左右孩子,当出现这种情况时(如图删除7),我们就要找出该结点的后继结点(因为右子树肯定存在,所以找肯定在右子树中),然后把这个后继结点替换到要删除的结点中,然后继续执行对这个后继结点的删除操作(递归删除操作就行了)。
 
  发现没?现在我的解题思路是自顶向下去分析……自顶向下,逐级求精是一个很伟大的思想!
 
  现在问题来了!后继结点怎么求?我们来分析一下,当求一个结点的后继结点时,分为以下两种情况:
  • 当该结点有右孩子时,后继结点就在右子树中,就是该右子树的最小结点
  • 当该结点没有右孩子时,那后继结点就满足这个条件:该后继结点是该结点的祖先&&该结点位于该结点的左子树中(如图中的9的后继结点是12)
  哎呀呀!问题又来了!最小结点咋办!很简单!
  当求一棵树的最小结点时,那么就要从这颗树的根节点开始,一直往左子树走,就能找到它的最小结点了!
  好了,现在问题逐步解决了!删除结点的功能也就完成了!
  最后,没代码说个锤子,咱上代码!
 
首先,写个测试类:
 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-
二叉树中不存在此结点!
 
1楼DM张朋飞
你可以考虑做个动画出来?可以这么说吧,看代码的人非常少,没啥价值

文章评论

 程序员的样子
程序员的样子
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
我的丈夫是个程序员
我的丈夫是个程序员
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
老程序员的下场
老程序员的下场
鲜为人知的编程真相
鲜为人知的编程真相
总结2014中国互联网十大段子
总结2014中国互联网十大段子
如何成为一名黑客
如何成为一名黑客
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
程序员和编码员之间的区别
程序员和编码员之间的区别
程序员的鄙视链
程序员的鄙视链
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
代码女神横空出世
代码女神横空出世
程序员应该关注的一些事儿
程序员应该关注的一些事儿
我是如何打败拖延症的
我是如何打败拖延症的
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
一个程序员的时间管理
一个程序员的时间管理
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
每天工作4小时的程序员
每天工作4小时的程序员
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
编程语言是女人
编程语言是女人
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
旅行,写作,编程
旅行,写作,编程
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
漫画:程序员的工作
漫画:程序员的工作
10个调试和排错的小建议
10个调试和排错的小建议
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
程序员必看的十大电影
程序员必看的十大电影
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
为什么程序员都是夜猫子
为什么程序员都是夜猫子
中美印日四国程序员比较
中美印日四国程序员比较
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有