所以我需要一些帮助,因为我正在从文件中读取并插入到列表和树中以进行搜索,此函数不会保存所有节点,它会在运行时丢失信息。
fe=left child
fd=right child
NodeCount 返回树中有多少个节点并且旋转函数正常工作
TREE *rotate left(TREE *A) //right just replace fe for fd:
{
ARVORE *aux;
aux=A->fd;
A->fd=aux->fe;
aux->fe=A;
return A;
}
如果树是平衡的,则平衡函数返回 1,否则返回 0
TREE *balances (TREE *A)
{
TREE *aux = A;
if(aux == NULL)
return A;
while(!balance(aux))
{
if((NodeCount(aux->fe) - NodeCount(aux->fd)) > 1)
aux=rotateright(aux);
if((NodeCount(aux->fd) - NodeCount(aux->fe)) > 1)
aux=rotateleft(aux);
return aux;
}
return A;
}
output :
before balances :0
01gwztbs0d@yahoo.com
2v7t5k72fb@clix.pt
2v7t5k72fb@clix.pt
3ahf@sapo.pt
bysws@clix.pt
cop8m5@clix.pt lost
ibnor@yahoo.com lost
lglkge@clix.pt lost
sck0z@yahoo.com lost
After Balances
01gwztbs0d@yahoo.com
2v7t5k72fb@clix.pt
2v7t5k72fb@clix.pt
3ahf@sapo.pt
bysws@clix.pt
Equi:1
最佳答案
你的问题是合乎逻辑的。您的 if 语句在逻辑上没有相互关联,并且条件重叠。结果,aux
被第二个 if
的所有语句覆盖,然后按原样返回。
示例:首先 aux = cop8m5@clix.pt;
然后 aux = 01gwztbs0d@yahoo.com;
和 01gwztbs0d@返回 yahoo.com
。
如果仔细观察,您会发现缺少的正是右侧的部分子树(所有大于根的元素)。看起来这是一个中序
遍历,因此根必须是bysws@clix.pt
。从这里您可以轻松地亲自看到它。
最快的解决方案是在每个 if 语句的正文中放置一个 return aux;
:
while(!balance(aux)) {
if ((NodeCount(aux->fe) - NodeCount(aux->fd)) > 1) {
aux=rotateright(aux);
return aux;
}
if ((NodeCount(aux->fd) - NodeCount(aux->fe)) > 1) {
aux=rotateleft(aux);
return aux;
}
}
关于c - 平衡搜索树的函数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34392804/