我正在尝试实现一个Red Black Tree,它的每个节点都由另一个RBTree组成。这样我才能得到很好的歌曲。第一棵树是乐队,每个节点(乐队)都有它的RBTree歌曲。
因此,我尝试在乐队树中的乐队节点的内部歌曲树中插入新歌曲,而内部树无法识别其头部指向nilNode的静态变量。不知道为什么。
RBTree的两个类中的插入方法都相同。每次插入都要考虑静态变量“ nilNode”,并根据它进行工作。当我将节点插入到外部树(带状树)时,该方法会识别出它。但是,当我从某个波段节点使用吸气剂进入内部树,并使用内部树的insert方法时,在该方法中它无法识别出它是nilNode。
插入方法如下:
1 .带状树称为插入。
2.该方法首先在bandsTree中找到频带的节点。
3.然后,该节点使用吸气剂获取其内在歌曲Tree。
4. innerTree调用相同的insert方法(他的insert方法与bands Tree的insert方法相同)。
现在,插入方法使用搜索方法来查看是否已经存在或需要创建节点(乐队或歌曲)。如果存在,则返回节点,如果不存在,则返回连接到节点的每个“松散端”的静态“ nilNode”。搜索方法从树的头部开始。
并且在第一次插入时,(当前乐队节点的)歌曲树为空,这意味着头指向静态“ nilNode”。因此搜索方法应该在循环的第一次检查时停止。但它无法识别出head等于nilNode,所以它继续,并且当它获取nilNode的左节点(为null)并尝试使用它时,会出现错误。
这些是我创建的4个类:BandNode,BandsRBTree,SongNode,SongsRBTree
1. BandNode:
import java.io.Serializable;
public class BandNode implements Serializable{
private Band band;
private BandNode left;
private BandNode right;
private BandNode parent;
private SongsRBTree innerTreeOfSongNames = new SongsRBTree(); **// another RBTree**
...
public BandNode(String bandName) **// I got 4 constructors and each looks like this one**
{
Band band = new Band(bandName);
this.band = band;
left = null;
right = null;
parent = null;
innerTreeOfSongNames = new SongsRBTree();
}
...
}//end of class BandNode
2. SongNode://没有像BandNode这样的内部树
public class SongNode implements Serializable{
private Song song;
private SongNode left;
private SongNode right;
private SongNode parent;
...
public SongNode(String songName) // same here 4 constructors
{
Song _song = new Song(songName);
this.song = _song;
left=null;
right=null;
parent=null;
}
...
}//end of SongNode class
3. BandsRBTree
import java.io.Serializable;
public class BandsRBTree implements Serializable{
private BandNode head; // head of the tree
static BandNode nilNodeBand; // Nil node to be connected to every 2 (left and right) null ends of a node
...
public BandsRBTree()
{
nilNodeBand = new BandNode("Nill)");
head = nilNodeBand;
}
//******************************************************
// methods for inner tree:
public BandNode insert(BandNode z , SongNode songNde)
{
BandNode b = search(z.getBand().getBandName()); // searches for the band node
if(b.equals(nilNodeBand)) // meaning the band node doesn't exists
{
//nothing to show here since it doesn't go in this part.
because the band node already exsits and the condition is false
...
}
else // the band is already in the tree.
now update it's inner tree of songs
{
//checking if the song node is good
if(songNde != null && songNde.getSong() != null)
{
if(songNde.getSong().getSongName().length()>0 ) // name of the song is good
{
b.getInnerTreeOfSongNames().insert(songNde); // using the inner tree of songs
return b; // return the band node
}
else
//print error
}
return null; // something was null
}
}//insert
//search in the band tree:
public BandNode search(String bandNameToSearch)
{
BandNode temp = head;
while( !temp.equals( nilNodeBand))
{
if( temp.getBand().getBandName().compareTo(bandNameToSearch) == 0 )
return temp;
else if(bandNameToSearch.compareTo(temp.getBand().getBandName()) < 0 )
temp = temp.getLeft();
else
temp = temp.getRight();
}
return nilNodeBand;
}
}// class BandsRBTree end
4. SongsRBTree
import java.io.Serializable;
public class SongsRBTree implements Serializable{
private SongNode head; // head of the tree
static SongNode nilNodeSong; // Nil node to be connected as every null child
...
//constructor
public SongsRBTree()
{
nilNodeSong = new SongNode(new Song("Nill"));
head = nilNodeSong; // the head is nilNode at the start
}
public SongNode insert(SongNode z )
{
// first search:
SongNode b = search(z.getSong().getSongName());
...
//the method get here because of the error in the search method
}//insert
public SongNode search(String songNameToSearch)
{
SongNode temp = head; // here the head is nilNode. see in the constructor
while( !temp.equals( nilNodeSong) ) // it enters the loop. ALTOUGH IT SHOULDN'T
{ // because temp = head. and the head suppose to be nilNodeSong
// since the tree is empty at the beginning
// see constructor
if( temp.getSong().getSongName().compareTo(songNameToSearch) == 0 )
return temp;
else if(songNameToSearch.compareTo(temp.getSong().getSongName()) < 0 )
temp = temp.getLeft();
else
temp = temp.getRight();
}
return nilNodeSong;
}
} // end of BandsRBTree class
无论如何,情况是这样的:
1.我有一个由10个band节点设置的band树
。2.每个bandnode的构造函数都有一个空的内部树。
3.我尝试使用内树木的插入方法的一个插入一首歌给它的第一次。
4.搜索方法无法识别树的头部指向nilNode。
为什么不认识这一点?(头部在开始时是nilNode,因为它是空的)
该问题是在BandsRBTree类的搜索方法中的while循环条件下发生的。该条件假设阻止该方法进入循环主体,因为在第一次插入时,构造方法的头为nilNode,但条件无法识别该情况。为什么??
请帮忙。
每次构造时,SongsRBTree
您都要清除静态变量的先前内容,并SongNode
在其位置创建一个新变量。快速循序渐进:创建SongsRBTree tree1
。现在nilNodeSong
是SongNode
我们称之为的nill1
。的head
的tree1
是nill1
。
现在创建SongsRBTree tree2
。现在nilNodeSong
是SongNode
我们称之为的nill2
。该head
的tree2
是nill2
但head
的tree1
仍然是nill1
。当您插入时tree1
,它当然不会识别nill1 == nill2
。
解决方案:静态初始值设定项或重写中的equals
方法,SongNode
而不必理会special static SongNode nillNodeSong
。我可能会优先考虑,equals
但是任何一个都可以解决问题。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句