二叉查找树

#include <iostream>

using namespace std;

typedef struct Node_ {
    int key;
    struct Node_* left, *right, *parent;
}Node, *BST;

Node *BSTsearch(BST T, int key) {
    if (T == NULL) {
        return NULL;
    }
    else if(key == T->key) {
        return T;
    }
    else {
        if (key < T->key) {
            return BSTsearch(T->left, key);
        }
        else {
            return BSTsearch(T->right, key);
        }
    }
}

Node *BSTsuccessor(BST T) {
    if (T->right == NULL ) {
        return T->parent;
    }
    else {
        Node *p = T->right;
        while (p->left != NULL) {
            p = p->left;
        }
        return p;
    }
}

Node *BSTinsert(BST &T, int key) {
    Node *p = T;
    Node *q = T;
    while (q != NULL) {
        p = q;
        if (key <= p->key) {
            q = p->left;
        }
        else {
            q = p->right;
        }
    }
    Node *tmp = new Node;
    tmp->left = tmp->right = tmp->parent = NULL;
    tmp->key = key;
    if (p == NULL) {
        T = tmp;
    }
    else {
        tmp->parent = p;
        if (key <= p->key) {
            p->left = tmp;
        }
        else {
            p->right = tmp;
        }
    }
    return T;
}

int BSTdelete(BST &T, int key) {
    Node *q = BSTsearch(T, key);
    if (q == NULL) {
        cout<<key<<" is not found"<<endl;
        return false;
    }
    Node *y = NULL;
    Node *x = NULL;
    if (q->left == NULL || q->right == NULL) {
        y = q;
    }
    else {
        y = BSTsuccessor(q);
    }
    if (y->left != NULL) {
        x = y->left;
    }
    else {
        x = y->right;
    }
    if (x != NULL) {
        x->parent = y->parent;
    }
    if (y->parent == NULL) {
        T = x;
    }
    else if (y == y->parent->left) {
        y->parent->left = x;
    }
    else {
        y->parent->right = x;
    }
    if (y != q) {
        q->key = y->key;
    }
    delete y;
    return true;
}

void inorder(BST T) {
    if (T != NULL) {
        inorder(T->left);
        cout<<T->key<<" ";
        inorder(T->right);
    }
}

int main(int argc, char **argv) {

    BST T = NULL;
    int n = 2;
    while (n != 0) {
        BSTinsert(T, n);
        cout<<“中序遍历： ”;
        inorder(T);
        cout<<endl;
        cin>>n;
    }
    n = 2;
    cout<<endl;
    inorder(T);
    cout<<endl;
    cout<<endl;
    while (n != 0) {
        BSTdelete(T, n);
        cout<<"删除节点 "<;
        inorder(T);
        cout<<endl;
        cin>>n;
    }

    return 0;
}