#include <bits/stdc++.h>
#define pb push_back
#define fs first
#define sc second
#define INF (1e9+7)
#define forn(i,z,n) for( auto (i) = (z); (i) < (n); ++i)

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

struct node {
    int key;
    node *left, *right, *parent;
    node(int q, node *x, node *y, node *p)  {
        key = q;
        left = x;
        right = y; parent = p;
    }
};
node *tree  = NULL, *f = NULL;
void add_n( node *j, node *&z)  {
    if( z == NULL)  {
        z = new node(j->key,NULL,NULL,NULL);
        return ;
    }
    if( z->key >= j->key)  {
        if( z->left)  {
            add_n(j, z->left);
        }
        else  {
            z->left = j;
            j->parent = z;
        }
    }
    else  {
        if( z->right)  {
            add_n(j,z->right);
        }
        else  {
            j->parent = z;
            z->right = j;
        }
    }
}
void show( node *x)  {
    if( x != NULL)  {
        show(x->left);
        cout << x->key << ' ';
        show(x->right);
    }
    else return ;
}
node *find_min( node *root)  {
    if( root->left != NULL)  {
        return find_min(root->left);
    }
    else  {
        return root;
    }

}
void delete_n(node *root, int val )  {
    if( root == NULL)  return ;
    else if( val < root->key)  delete_n( root->left, val);
    else if( val > root->key) delete_n(root->right, val);
    else  {
        if( root->left == NULL && root->right ==NULL)  {
            //delete root;
            root = NULL;
        }
        else if( root->left == NULL)  {
            root->right->parent = root->parent;
            root = root->right;
            //delete root->right;
            root->right = NULL;
        }
        else if( root->right == NULL)  {
            root->left->parent = root->parent;
            root = root->left;
            //delete root->left;
            root->left = NULL;
        }
        else  {
            node *temp = find_min( root->right);
            temp->parent = root->parent;
            root = temp;
            delete_n( root->right, temp->key);
        }
    }
    return ;
}
void post( node *x)  {
    if( x != NULL)  {
        post(x->right);
        post(x->left);
        cout << x->key << ' ';
    }
}
void show_parents( node *z)  {
    if(z != NULL)  {
        show_parents(z->left);
        show_parents(z->right);
        if( z->parent != NULL)
            cout << z->key << ' ' <<  (z->parent->key) << endl;
    }
}
int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n; cin >> n;
    vector <int> v;
    forn(i,0, n)  {
        int x;
        cin >> x;
        v.pb(x);
    }
    for(int i = 0; i <n; ++i)  {
        node *help = new node(v[i], NULL, NULL,NULL);
        add_n( help, tree);
    }
    show(tree);                              // в невозрастающем порядке
    delete_n(tree, 3);
    cout << endl;
    show(tree);
    return 0;
}

I have found one mistake and then stopped reading.
If val==root key,  you are assigning root=NULL.
root is a not root of your tree,  root is just a copy.  So you are assigning NULL to a copy of a node to your tree,  not a real node.

http://ideone.com/Bu2Udh

I am talking about this

Ну короче функция которая удаляет,  как минимум,  должна получать **root вместо *root.  Может быть,  еще что-то есть,  я не дошел.  Я как компилятор короче,  дооел до первой строки в которой что-то не так и остановился