fork download

copy

 
// This function does inorder traversal to find out the two swapped nodes. 
// It sets three pointers, first, middle and last.  If the swapped nodes are 
// adjacent to each other, then first and middle contain the resultant nodes 
// Else, first and last contain the resultant nodes 
void correctBSTUtil( struct node* root, struct node** first, 
                     struct node** middle, struct node** last, 
                     struct node** prev ) 
{ 
    if( root ) 
    { 
        // Recur for the left subtree 
        correctBSTUtil( root->left, first, middle, last, prev ); 
 
        // If this node is smaller than the previous node, it's violating 
        // the BST rule. 
        if (*prev && root->data < (*prev)->data) 
        { 
            // If this is first violation, mark these two nodes as 
            // 'first' and 'middle' 
            if ( !*first ) 
            { 
                *first = *prev; 
                *middle = root; 
            } 
 
            // If this is second violation, mark this node as last 
            else
                *last = root; 
        } 
 
        // Mark this node as previous 
        *prev = root; 
 
        // Recur for the right subtree 
        correctBSTUtil( root->right, first, middle, last, prev ); 
    } 
} 
 
// A function to fix a given BST where two nodes are swapped.  This 
// function uses correctBSTUtil() to find out two nodes and swaps the 
// nodes to fix the BST 
void correctBST( struct node* root ) 
{ 
    // Initialize pointers needed for correctBSTUtil() 
    struct node *first, *middle, *last, *prev; 
    first = middle = last = prev = NULL; 
 
    // Set the poiters to find out two nodes 
    correctBSTUtil( root, &first, &middle, &last, &prev ); 
 
    // Fix (or correct) the tree 
    if( first && last ) 
        swap( &(first->data), &(last->data) ); 
    else if( first && middle ) // Adjacent nodes swapped 
        swap( &(first->data), &(middle->data) ); 
 
    // else nodes have not been swapped, passed tree is really BST. 
} 

prog.cpp: In function ‘void correctBSTUtil(node*, node**, node**, node**, node**)’:
prog.cpp:13:29: error: invalid use of incomplete type ‘struct node’
         correctBSTUtil( root->left, first, middle, last, prev );
                             ^~
prog.cpp:6:29: note: forward declaration of ‘struct node’
 void correctBSTUtil( struct node* root, struct node** first,
                             ^~~~
prog.cpp:17:26: error: invalid use of incomplete type ‘struct node’
         if (*prev && root->data < (*prev)->data)
                          ^~
prog.cpp:6:29: note: forward declaration of ‘struct node’
 void correctBSTUtil( struct node* root, struct node** first,
                             ^~~~
prog.cpp:17:42: error: invalid use of incomplete type ‘struct node’
         if (*prev && root->data < (*prev)->data)
                                          ^~
prog.cpp:6:29: note: forward declaration of ‘struct node’
 void correctBSTUtil( struct node* root, struct node** first,
                             ^~~~
prog.cpp:36:29: error: invalid use of incomplete type ‘struct node’
         correctBSTUtil( root->right, first, middle, last, prev );
                             ^~
prog.cpp:6:29: note: forward declaration of ‘struct node’
 void correctBSTUtil( struct node* root, struct node** first,
                             ^~~~
prog.cpp: In function ‘void correctBST(node*)’:
prog.cpp:47:36: error: ‘NULL’ was not declared in this scope
     first = middle = last = prev = NULL;
                                    ^~~~
prog.cpp:47:36: note: ‘NULL’ is defined in header ‘<cstddef>’; did you forget to ‘#include <cstddef>’?
prog.cpp:1:1:
+#include <cstddef>
 
prog.cpp:47:36:
     first = middle = last = prev = NULL;
                                    ^~~~
prog.cpp:54:22: error: invalid use of incomplete type ‘struct node’
         swap( &(first->data), &(last->data) );
                      ^~
prog.cpp:6:29: note: forward declaration of ‘struct node’
 void correctBSTUtil( struct node* root, struct node** first,
                             ^~~~
prog.cpp:54:37: error: invalid use of incomplete type ‘struct node’
         swap( &(first->data), &(last->data) );
                                     ^~
prog.cpp:6:29: note: forward declaration of ‘struct node’
 void correctBSTUtil( struct node* root, struct node** first,
                             ^~~~
prog.cpp:54:9: error: ‘swap’ was not declared in this scope
         swap( &(first->data), &(last->data) );
         ^~~~
prog.cpp:56:22: error: invalid use of incomplete type ‘struct node’
         swap( &(first->data), &(middle->data) );
                      ^~
prog.cpp:6:29: note: forward declaration of ‘struct node’
 void correctBSTUtil( struct node* root, struct node** first,
                             ^~~~
prog.cpp:56:39: error: invalid use of incomplete type ‘struct node’
         swap( &(first->data), &(middle->data) );
                                       ^~
prog.cpp:6:29: note: forward declaration of ‘struct node’
 void correctBSTUtil( struct node* root, struct node** first,
                             ^~~~
prog.cpp:56:9: error: ‘swap’ was not declared in this scope
         swap( &(first->data), &(middle->data) );
         ^~~~

Standard output is empty