活跃农民
- 积分
- 624
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2015-4-10
- 最后登录
- 1970-1-1
|
本帖最后由 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;
}
}
|
|