AVL TREE в с ++ - PullRequest
Новая
       29

AVL TREE в с ++

5 голосов
/ 16 января 2010

У меня проблема с этим очень простым блоком кода. пожалуйста, дайте мне ваш совет. (Моя проблема решена, и в решении этой проблемы человек, имеющий идентификатор stakx, действительно помог мне, единственная проблема заключалась в том, что я использовал стек , когда я внимательно увидел метод push стека, есть процесс копирования, когда я пишу head-> object = number, так что, наконец, я создал стек указателей, как этот стек , и это действительно решило проблему, у меня сейчас нет проблем, я очень, очень благодарен человеку stakx.)

перед кодом необходимо добавить следующее дерево

альтернативный текст http://img44.imageshack.us/img44/7016/avlimage06.jpg
Как видно на рисунке, корень равен 8, а стек имеет два узла, то есть 6 и 4. Я передаю этот стек и корневой узел следующему коду 

void Avltree::attachwithtree(treeNode* tree, Stack<treeNode>&s)
{
if(!s.isempty())
{
treeNode *stacknode;
stacknode=s.pop();
cout<<"\ninside the attachwithtree function, stack node is "<<stacknode->data;
stacknode->right=tree;//attaching the passed node to the right of popped node
root=stacknode;//setting the root to stack node which is the private data member of class
updatebalance(root);//this function is ok, it does not create problem
while(!s.isempty())
{
cout<<"\nstack is still not empty";
stacknode=s.pop();
cout<<"\nright side of "<<root->data<<" is "<<(root->right)->data;
//the below three lines causing the problem i don't know why,
root=stacknode;
treeNode* temp;
temp=root->right;
cout<<"\n\n\nthe right side of "<<temp->data<<" is now "<<(temp->right)->data;
updatebalance(root);
}

выход этой функции дается
alt text


вот код метода pop стека, который я использую 

template <class t>
t * Stack<t>::pop()
{
if(topelement!=NULL)
{
t* num;
current=topelement;
num=&(current->object);
topelement=topelement->preptr;
current=topelement;
return(num);
}
else
{
head=NULL;
}
}


вот код метода push стека 

template <class t>
void Stack<t>::push(t &number)
{
Node<t>* newNode=new Node<t>;
if(head==NULL)
{
head=newNode;
topelement=newNode;
current=newNode;
head->object=number;
head->preptr=NULL;
}
else
{
topelement=newNode;
newNode->preptr=current;
current=topelement;
newNode->object=number;
}
}

Ответы [ 2 ]

4 голосов
/ 16 января 2010

Оригинальный ответ:

Может ли быть так, что узел 4 в стеке имеет другой узел 6 справа (тот, с узлом 7 справа), чем узел 6 (с узлом 8 справа) вы работаете над? Вы можете сравнить их адреса, чтобы убедиться, что у вас нет двух разных копий узла 6 вокруг.

Разработка приведенного выше аргумента:

Давайте посмотрим на подпись вашего метода: 

void Avltree::attachwithtree(treeNode* tree, Stack<treeNode>&s)

s определяется как ссылка на Stack<treeNode>.

Может быть, это Stack<treeNode*>?

В зависимости от вашего treeNode класса, возможно, что когда вы помещаете X в этот стек, вы на самом деле получаете копию X, а не X. Точно так же, когда вы вытаскиваете из стека, вы на самом деле можете получить не элемент, который вы нажали, а его копию идентичного вида!?

Это будет означать, что в то время, когда вы помещаете узел 6 в стек, его правый дочерний элемент - это узел 7. Но вы поместили новый, идентичный узел в стек. Даже если вы извлечете этот элемент из стека и измените его, вы только измените копию и оставите исходный узел дерева, как это было раньше.

Следовательно, вы будете работать с разными копиями узла 6. Сначала вы извлекаете копию из стека и добавляете дерево в качестве его правого потомка. Проверка этого даст правильный результат.

Затем вы извлекаете копию узла 4 из стека. Правильный дочерний элемент - это узел 6, как и ожидалось, НО не тот, который вы только что изменили, а оригинал! Поэтому вы получаете 7 на правой стороне узла 6.

Демонстрируя разницу между передачей по значению и передачей по ссылке:

Хорошо, вот что вам нужно понять при работе с указателями или ссылками. В основном это показывает разницу между передачей параметра по значению (будет создана копия) или передачей по ссылке (копия не будет создана).

Внимательно изучите его, а затем посмотрите, как оно подходит к вашей проблеме. 

#include <iostream>

class someObject
{
private:
    int _value;
public:
    someObject(int value) : _value(value) { }

    int getValue()
    {
        return _value;
    }
};

void someFunction(someObject objCopy, someObject* objPtr)
{
    std::cout << "objCopy.getValue() -> " << objCopy.getValue() << std::endl;
    std::cout << "objPtr->getValue() -> " << objPtr->getValue() << std::endl;
    if ( &objCopy != objPtr )
    {
        std::cout << "objCopy is not actually *objPtr but a copy of it." << std::endl;
    }
    else
    {
        std::cout << "objCopy and *objPtr are one and the same object." << std::endl;
    }
}


int main()
{
    someObject X(17);
    someFunction(X, &X);

    return 0;
}

Подсказка : Да, в вашем методе pop вы работаете с указателями, но, скорее всего, с указателем на копию объекта, первоначально помещенного в стек.

1 голос
/ 16 января 2010

Это ваш собственный класс стека? Беглый взгляд на STL говорит мне, что pop () имеет тип возврата void.

Может быть, что Stakx на что-то здесь. Если ваша функция pop () возвращает копию верхнего элемента, а не ссылку на него, сделанные вами изменения будут применяться только к копии. Вы явно добавляете копию обратно в дерево в любом месте после ее изменения?

...