一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 872|回复: 16
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
18258170717 发表于 2014-12-8 18:47:22 | 显示全部楼层 |阅读模式

[其他]CS 61B Data Structures(in Java) #10 - 2006(2014.12.8)@UC Berkeley

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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

LAB10

LAB10
whdawn 发表于 2015-5-5 18:11:37 | 显示全部楼层

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

QQ20150505-1@2x.png

回复 支持 反对

使用道具 举报

 楼主| 18258170717 发表于 2015-5-5 22:10:10 | 显示全部楼层
whdawn 发表于 2015-5-5 18:11
看似比较简单,但是在remove里面还是些陷阱

男神来到了lab10~
回复 支持 反对

使用道具 举报

whdawn 发表于 2015-5-5 22:22:07 | 显示全部楼层

鶸被公开课之神嘲笑了            
回复 支持 反对

使用道具 举报

 楼主| 18258170717 发表于 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然后给我个内推
回复 支持 反对

使用道具 举报

enirinth 发表于 2015-6-6 22:27:39 | 显示全部楼层
先贴作业:
111.png


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

使用道具 举报

阿童木 发表于 2016-3-5 11:39:38 | 显示全部楼层
比hw7简单,但也写了一个多小时……捂脸
QQ截图20160305113817.png


回复 支持 反对

使用道具 举报

zhengyino1 发表于 2016-3-8 13:52:55 | 显示全部楼层
找不到2014Spring的Lab10啊。。。我就贴这儿吧。。。。。谁能抛给我个2014 Spring的链接
哪里有Spring2014 lab10的链接
Capture.JPG
回复 支持 反对

使用道具 举报

zhengyino1 发表于 2016-3-17 05:45:46 | 显示全部楼层
看起来简单,debug还是花了不少时间呢嘿
Capture.JPG
回复 支持 反对

使用道具 举报

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;
        }
    }




回复 支持 反对

使用道具 举报

pirateshadow 发表于 2016-4-25 15:11:26 | 显示全部楼层
不难,但总是需要改动几遍。。
Screen Shot 2016-04-25 at 3.04.01 PM.png
回复 支持 反对

使用道具 举报

Chris1993 发表于 2016-4-25 16:36:15 | 显示全部楼层
全是改bug 改了一个多小时
Screen Shot 2016-04-25 at 4.35.51 PM.png
回复 支持 反对

使用道具 举报

irene000000 发表于 2016-4-30 10:49:50 | 显示全部楼层
算是做的比较快的lab啦~parent跟child的关系一开始没写对,dubug了一下
Lab 11.png
回复 支持 反对

使用道具 举报

Eloise 发表于 2016-5-18 09:51:10 | 显示全部楼层
remove 分情况分的好繁琐...
QQ截图20160518093618.png
回复 支持 反对

使用道具 举报

zzdsg 发表于 2016-8-21 10:03:06 | 显示全部楼层
在经过hw7的洗礼之后,觉得lab比起来简单不少~
lab11.png
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 23:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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