Функция для балансировки дерева поиска

Так что мне нужна помощь в этом, так как я читаю из файла и вставляю в список и дерево для поиска, эта функция не сохраняет все узлы, она теряет информацию, а Бег.Функция для балансировки дерева поиска

fe=left child 
fd=right child

NodeCount возвращает количество узлов в дереве и Rotate функции правильно

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 
    [email protected] 
    [email protected] 
    [email protected] 
    [email protected] 
    [email protected] 
    [email protected] lost 
    [email protected] lost 
    [email protected] lost 
    [email protected] lost 
    After Balances 
    [email protected] 
    [email protected] 
    [email protected] 
    [email protected] 
    [email protected] 
    Equi:1

источник

2015-12-21 euphz2011

«эта функция не сохраняет все узлы». На какую функцию вы ссылаетесь? Предоставьте [Минимальный полный и проверенный пример] (http://stackoverflow.com/help/mcve), включая ввод теста, ожидаемое поведение и фактическое поведение. – kaylum

баланс функции, функция не возвращает правильный корень дерева – euphz2011

Я читаю около 1000 писем из файла, а на дереве есть только несколько, но все письма прочитаны, что я знаю, потому что я добавив их в связанный список, а также они находятся в списке @kaylum – euphz2011

работает

Ваша проблема логична. Ваши if-утверждения не логически связаны друг с другом, и условия перекрываются. В результате aux перезаписывается всеми операциями второго if и затем возвращается как таковой.

Пример: сначала aux = [email protected]; затем aux = [email protected]; и [email protected] возвращается.

Если вы внимательно присмотритесь, вы увидите, что то, что отсутствует, является именно правильным частичным поддеревом (все элементы больше корня). По-видимому, это обход inorder, поэтому корень должен быть [email protected]. Отсюда вы можете легко увидеть это сами.

Кратчайший решение поставить один 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; 
     } 
}

источник

2015-12-21 18:19:59 user8

@ euphz2011 Добро пожаловать в SO! Поскольку вы (относительно) новы, вы можете проверить это [ссылка] (http://meta.stackexchange.com/questions/5234/how-does-accepting-an-answer-work/5235#5235) – user8

Функция для балансировки дерева поиска

ответ

Смежные вопросы