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

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

🔗
zhengyino1 2016-3-17 05:45:46 | 只看该作者
全局:
看起来简单,debug还是花了不少时间呢嘿

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

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 (154.7 KB, 下载次数: 0)

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 (181.81 KB, 下载次数: 0)

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 (187.79 KB, 下载次数: 1)

Lab 11.png
回复

使用道具 举报

🔗
Eloise 2016-5-18 09:51:10 | 只看该作者
全局:
remove 分情况分的好繁琐...

QQ截图20160518093618.png (30.5 KB, 下载次数: 0)

QQ截图20160518093618.png
回复

使用道具 举报

🔗
zzdsg 2016-8-21 10:03:06 | 只看该作者
全局:
在经过hw7的洗礼之后,觉得lab比起来简单不少~

lab11.png (78.17 KB, 下载次数: 0)

lab11.png
回复

使用道具 举报

🔗
codergoose 2016-12-11 21:07:00 | 只看该作者
全局:
思路还是要先想清楚,不然时间都调bug去了

回复

使用道具 举报

🔗
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,自己的代码果然惨不忍睹。


回复

使用道具 举报

🔗
Susan1013 2017-1-5 08:47:24 | 只看该作者
本楼:
全局:
2014 lab10

Screen Shot 2017-01-04 at 16.45.40.png (46.85 KB, 下载次数: 0)

Screen Shot 2017-01-04 at 16.45.40.png
回复

使用道具 举报

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

本版积分规则

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