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

Zawołał

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

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

Zwroty : 2,5


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

        PrintPreOrder(node->left);
        PrintPreOrder(node->right);
    }
} 
1
atul 13 lipiec 2011, 11:08

2 odpowiedzi

Najlepsza odpowiedź

Problem polega na tym, że funkcja insert w Twoim przypadku powinna zawsze zwracać bieżący węzeł. Coś takiego:

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

Operator = zwraca wartość ustawioną po prawej stronie - w twoim przypadku jest to najniższy utworzony węzeł potomny, który ostatecznie nadpisuje jeden z najwyższych węzłów.

0
bezmax 13 lipiec 2011, 11:14

Przypisujesz wartości w zbyt wielu miejscach.

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

Te wiersze zwracają wartość i przypisują - na każdym poziomie stosu rekurencji.

Nie należy przypisywać wielokrotnie podczas rekurencji. W przeciwnym razie zniszczysz drzewo, przez które przechodzisz, zastępując każdy węzeł w przemierzaniu końcowym węzłem wyniku.

W przypadku kodu o takiej strukturze (z rekurencją lewą/prawą + powrót) jedynym miejscem, w którym należy wykonać przypisanie, jest:

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

Jeśli jednak to zrobisz, będziesz musiał wziąć wskaźnik do wskaźnika.

0
Merlyn Morgan-Graham 13 lipiec 2011, 11:13