что не так с вставкой элемента дерева ниже - PullRequest
Новая
       7

что не так с вставкой элемента дерева ниже

1 голос
/ 13 июля 2011 
struct node* insert(struct node* node, int data)
{
    if(node == NULL)
    {
        // if tree is empty
        return NewNode( data ); 
    }
    else
    {
        if( node->data > data )
        {
            // data is less than node, add to left subtree
           return  node->left = insert(node->left, data);
        }
        else if( node->data <= data)
        {
            // data is more than node, add to right subtree
            return node->right = insert(node->right, data);
        }
            // else return node
            return node;
    }
}

вызывается с 

node *p = new node();
p->data = 2;
//printf("%d",lookup(p,2));

 insert( p, 3);
 insert( p, 4);
 insert( p, 5);
 PrintPreOrder(p);

, возвращается: 2,5 

void PrintPreOrder(node *node)
{
    if(node==NULL)
    {
        return;
    }
    else
    {
        printf("%d ", node->data);

        PrintPreOrder(node->left);
        PrintPreOrder(node->right);
    }
}

Ответы [ 2 ]

0 голосов
/ 13 июля 2011

Проблема в том, что функция insert в вашем случае всегда должна возвращать текущий узел. Примерно так: 

struct node* insert(struct node* node, int data)
{
    if(node == NULL)
    {
        // if tree is empty
        return NewNode( data ); 
    }
    else
    {
        if( node->data > data )
        {
            // data is less than node, add to left subtree
           node->left = insert(node->left, data);
            // <<<<<<<<<<< NO RETURN HERE
        }
        else if( node->data <= data)
        {
            // data is more than node, add to right subtree
            node->right = insert(node->right, data);
            // <<<<<<<<<<< NO RETURN HERE
        }
        // else return node
        //ALWAYS RETURN NODE
        return node;
    }
}

Оператор = возвращает значение, которое было установлено справа от него - в вашем случае это самый нижний созданный дочерний узел, который в конечном итоге перезаписывает один из верхних узлов.

0 голосов
/ 13 июля 2011

Вы назначаете значения в слишком многих местах. 

return node->left = insert(node->left, data);
// ...
return node->right = insert(node->right, data);

Эти строки возвращают значение и присваивают - на каждом уровне стека рекурсии.

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

При таком структурированном коде (с рекурсией влево / вправо + возврат) единственное место, где вы должны выполнить назначение, это: 

if(node == NULL)
{
    // assign here...
}

Однако, если вы сделаете это, вам придется взять указатель на указатель.

...