📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 5995| 回复: 30
跳转到指定楼层
上一主题 下一主题
收起左侧

Berkeley CS 61B Data Structures(in Java) Lab10 讨论帖

全局:
公开课
学校名称: UC Berkeley
Unit号: 10
开课时间: 2006(2014.12.8)
课程全名: CS 61B Data Structures(in Java)
平台: 其他

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
LAB10,完成BinaryTree,比较简单,但问题在于Lecture中没有提到root的处理,和一般的internal node有略微不同,大家可以注意一下。

LAB10.png (135.71 KB, 下载次数: 3)

LAB10

LAB10

上一篇:计算机组成 Week7-9
下一篇:Berkeley CS 61B Data Structures(in Java) Lab12 讨论帖
推荐
caominki 2016-4-13 14:43:43 | 只看该作者
全局:
本帖最后由 caominki 于 2016-4-13 14:45 编辑

谁能看到?帮个忙指点一下,有没有更简洁的方法????

问题是这样,我的remove()方法写了很多行(120多行),我是不是实现的太low了啊,有没有更简洁的方式实现remove() 呢???
关于remove我的思路是:
>--- 是rootNode,单独处理;
>---不是rootNode {
>>---------------------是其父节点的左孩子 {
>>>-----------------------------------------------没有孩子
>>>----------------------------------------------只有左孩子
>>>----------------------------------------------只有右孩子
>>>----------------------------------------------左右孩子都有 {
>>>>---------------------------------------------------------------其右孩子有左孩子 {
>>>>>--------------------------------------------------------------------------------------其右孩子的左孩子有右孩子{}
>>>>>--------------------------------------------------------------------------------------其右孩子的左孩子无右孩子{}
>>>>---------------------------------------------------------------其右孩子有左孩子}
>>>>---------------------------------------------------------------其右孩子无左孩子{}
>>>----------------------------------------------左右孩子都有}
>>---------------------是其父节点的左孩子}
>>---------------------是其父节点的右孩子{重复绿字部分的分类讨论}
>---不是rootNode  }


public Entry remove(Object key) {
        // Replace the following line with your solution.
        BinaryTreeNode node=findHelper((Comparable)key, root);
        if(node!=null){
            if(node.parent!=null){// No rootNode
                if(node.parent.leftChild==node){//belongs to its parents leftChild
                    if(node.leftChild==null&&node.rightChild==null){//has no child
                        node.parent.leftChild=null;
                    }else if(node.leftChild!=null&&node.rightChild==null){//has leftchild
                        node.leftChild.parent=node.parent;
                        node.parent.leftChild=node.leftChild;
                    }else if(node.rightChild!=null&&node.leftChild==null){//has rightchild
                        node.rightChild.parent=node.parent;
                        node.parent.leftChild=node.rightChild;
                    }else{//has both leftchild and rightchild
                        BinaryTreeNode rightChildNode=node.rightChild;
                        if(rightChildNode.leftChild!=null){//rightchild has a leftchild
                            BinaryTreeNode curLeftNode=rightChildNode.leftChild;
                            while(curLeftNode.leftChild!=null){//find the farthermost leftchild
                                curLeftNode=curLeftNode.leftChild;
                            }
                            if(curLeftNode.rightChild!=null){//the farthermost leftchild has rightchild
                                curLeftNode.parent.leftChild=curLeftNode.rightChild;
                                curLeftNode.rightChild.parent=curLeftNode.parent;
                            }else{//the farthermost leftchild has no rightchild
                                curLeftNode.parent.leftChild=null;
                            }
                            curLeftNode.leftChild=node.leftChild;
                            curLeftNode.rightChild=node.rightChild;
                            curLeftNode.parent=node.parent;
                            node.leftChild.parent=curLeftNode;
                            node.rightChild.parent=curLeftNode;
                            node.parent.leftChild=curLeftNode;
                        }else{//rightchild has no leftchild
                            rightChildNode.leftChild=node.leftChild;
                            rightChildNode.parent=node.parent;
                            node.leftChild.parent=rightChildNode;
                            node.parent.leftChild=rightChildNode;
                        }
                    }
                }else{//belongs to its parents rightChild
                    if(node.leftChild==null&&node.rightChild==null){//has no child
                        node.parent.rightChild=null;
                    }else if(node.leftChild!=null&&node.rightChild==null){//has leftchild
                        node.leftChild.parent=node.parent;
                        node.parent.rightChild=node.leftChild;
                    }else if(node.rightChild!=null&&node.leftChild==null){//has rightchild
                        node.rightChild.parent=node.parent;
                        node.parent.rightChild=node.rightChild;
                    }else{//has both leftchild and rightchild
                        BinaryTreeNode rightChildNode=node.rightChild;
                        if(rightChildNode.leftChild!=null){//rightchild has a leftchild
                            BinaryTreeNode curLeftNode=rightChildNode.leftChild;
                            while(curLeftNode.leftChild!=null){//find the farthermost leftchild
                                curLeftNode=curLeftNode.leftChild;
                            }
                            if(curLeftNode.rightChild!=null){//the farthermost leftchild has rightchild
                                curLeftNode.parent.leftChild=curLeftNode.rightChild;
                                curLeftNode.rightChild.parent=curLeftNode.parent;
                            }else{//the farthermost leftchild has no rightchild
                                curLeftNode.parent.leftChild=null;
                            }
                            curLeftNode.leftChild=node.leftChild;
                            curLeftNode.rightChild=node.rightChild;
                            curLeftNode.parent=node.parent;
                            node.leftChild.parent=curLeftNode;
                            node.rightChild.parent=curLeftNode;
                            node.parent.rightChild=curLeftNode;
                        }else{//rightchild has no leftchild
                            rightChildNode.leftChild=node.leftChild;
                            rightChildNode.parent=node.parent;
                            node.leftChild.parent=rightChildNode;
                            node.parent.rightChild=rightChildNode;
                        }
                    }
                }
                node.parent=null;// not a rootNode should set its parent to null
            }else{//rootNode
                if(node.leftChild==null&&node.rightChild==null){//has no child
                    //do nothing because the last has handled already.
                }else if(node.leftChild!=null&&node.rightChild==null){//has leftchild
                    node.leftChild.parent=null;
                    root=node.leftChild;
                }else if(node.rightChild!=null&&node.leftChild==null){//has rightchild
                    node.rightChild.parent=null;
                    root=node.rightChild;
                }else{//has both leftchild and rightchild
                    BinaryTreeNode rightChildNode=node.rightChild;
                    if(rightChildNode.leftChild!=null){//rightchild has a leftchild
                        BinaryTreeNode curLeftNode=rightChildNode.leftChild;
                        while(curLeftNode.leftChild!=null){//find the farthermost leftchild
                            curLeftNode=curLeftNode.leftChild;
                        }
                        if(curLeftNode.rightChild!=null){//the farthermost leftchild has rightchild
                            curLeftNode.parent.leftChild=curLeftNode.rightChild;
                            curLeftNode.rightChild.parent=curLeftNode.parent;
                        }else{//the farthermost leftchild has no rightchild
                            curLeftNode.parent.leftChild=null;
                        }
                        curLeftNode.leftChild=node.leftChild;
                        curLeftNode.rightChild=node.rightChild;
                        node.leftChild.parent=curLeftNode;
                        node.rightChild.parent=curLeftNode;
                        curLeftNode.parent=null;
                        root=curLeftNode;
                    }else{//rightchild has no leftchild
                        rightChildNode.leftChild=node.leftChild;
                        rightChildNode.parent=null;
                        node.leftChild.parent=rightChildNode;
                        node.parent.leftChild=rightChildNode;
                        root=rightChildNode;
                    }
                }
            }
            node.rightChild=null;
            node.leftChild=null;
            node.entry=null;
            size--;
            return node.entry;
        }else{
            return null;
        }
    }




回复

使用道具 举报

推荐
Susan1013 2017-1-6 09:11:22 | 只看该作者
全局:
我什么新的代码都没敲,compile后出现Note: dict/BinaryTree.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.这两行。
之后我又recompile with-Xlint,  出来warning: [rawtypes] found raw type: Comparable
  private void insertHelper(Entry entry, Comparable key, BinaryTreeNode node) {
                                         ^
  missing type arguments for generic class Comparable<T>
  where T is a type-variable:
    T extends Object declared in interface Comparable

谁能告诉我怎么回事啊?万分感谢!
回复

使用道具 举报

推荐
codergoose 2016-12-13 21:37:02 | 只看该作者
全局:
2014 lab10



2014 lab11,没有什么是一行if else解决不了的,如果不行,那就再加十行,,直接写了接近100行if else
后面看了下http://algs4.cs.princeton.edu/32bst/BST.java.html,自己的代码果然惨不忍睹。


回复

使用道具 举报

🔗
ryanli 2015-3-27 05:29:23 | 只看该作者
本楼:
全局:
交个作业

lab10.JPG (56.57 KB, 下载次数: 2)

lab10.JPG
回复

使用道具 举报

🔗
whdawn 2015-5-5 18:11:37 | 只看该作者
全局:

看似比较简单,但是在remove里面还是些陷阱



回复

使用道具 举报

🔗
 楼主| dreamingrobot 2015-5-5 22:10:10 | 只看该作者
全局:
whdawn 发表于 2015-5-5 18:11
看似比较简单,但是在remove里面还是些陷阱

男神来到了lab10~
回复

使用道具 举报

🔗
whdawn 2015-5-5 22:22:07 | 只看该作者
全局:

鶸被公开课之神嘲笑了            
回复

使用道具 举报

🔗
 楼主| dreamingrobot 2015-5-5 23:19:00 | 只看该作者
全局:
whdawn 发表于 2015-5-5 22:22
鶸被公开课之神嘲笑了

只能上上公开课,男神能去CMU上神课
回复

使用道具 举报

🔗
whdawn 2015-5-6 02:16:28 | 只看该作者
全局:
18258170717 发表于 2015-5-5 23:19
只能上上公开课,男神能去CMU上神课

坐等大神拿遍FLAG然后给我个内推
回复

使用道具 举报

🔗
wynnforce 2015-6-6 22:27:39 | 只看该作者
全局:
先贴作业:



找了半天找不到lab11.。。。原来在06年的lab10里面
请版主标注一下啊,06年的lab10 就是 14年的lab11 ~
回复

使用道具 举报

🔗
阿童木 2016-3-5 11:39:38 | 只看该作者
全局:
比hw7简单,但也写了一个多小时……捂脸



回复

使用道具 举报

🔗
zhengyino1 2016-3-8 13:52:55 | 只看该作者
全局:
找不到2014Spring的Lab10啊。。。我就贴这儿吧。。。。。谁能抛给我个2014 Spring的链接
哪里有Spring2014 lab10的链接[b][/b]

Capture.JPG (45.97 KB, 下载次数: 0)

Capture.JPG
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表