c - 平衡搜索树的函数

Question

所以我需要一些帮助，因为我正在从文件中读取并插入到列表和树中以进行搜索，此函数不会保存所有节点，它会在运行时丢失信息。

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

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