#include<stdio.h>#include<iostream>#include<math.h>#include<stdlib.h>using namespace std;struct TreeNode{    TreeNode* p;    TreeNode* l;    TreeNode* r;    int key;    TreeNode()    {        p = 0;        l = 0;        r = 0;        key = -1;    }};const int RANDMOD = 300;const int MAX = 10;TreeNode* root = new TreeNode;int tIndex = 0;int a[MAX];int getRandom(){    return rand() % RANDMOD;}/** * 中序遍历 */void inOrder(TreeNode* root){    if(root == NULL)        return;    inOrder(root->l);    cout << root->key << " ";    inOrder(root->r);}/** * 插入一个结点,等于在左子树 */void insertNode(int key){    if(root->key == -1)    {        root->key = key;        return;    }    TreeNode* p = root;    TreeNode* pc = 0;    while (p != NULL)    {        pc = p;        if(key <= p->key)            p = p->l;        else            p = p->r;    }    TreeNode* newNode = new TreeNode;    newNode->key = key;    newNode->p = pc;    if(key <= pc->key)        pc->l = newNode;    else        pc->r = newNode;}/** * 查找root->key=key的结点 */TreeNode* findNode(TreeNode* root, int key){    if(root->key == key)        return root;    if(key <= root->key)        return findNode(root->l, key);    else        return findNode(root->r, key);    return 0;}/** * 查找以该结点为根的最小key的结点 */TreeNode* minNode(TreeNode* node){    while (node->l != NULL)        node = node->l;    return node;}/** * 查找以该结点为根的最大key的结点 */TreeNode* maxNode(TreeNode* node){    while (node->r != NULL)        node = node->r;    return node;}/** * z结点的后继结点 y * y.key > z.key && y2.key>y.key */TreeNode* afterNode(TreeNode* zNode){    if(zNode->r != NULL)        return minNode(zNode->r);    TreeNode* y = zNode->p;    while (y != NULL && zNode == y->r)    {        zNode = y;        y = y->p;    }    //不存在返回NULL    return y;}/** *用v为根的结点替换u为根的子树 */void transplant(TreeNode* u, TreeNode* v){    //树根    if(u->p == NULL)        root = v;    else if(u == u->p->l)    {        u->p->l = v;    }    else        u->p->r = v;    if(v != NULL)        v->p = u->p;}void deleteNode(TreeNode* zNode){    if(zNode->l == NULL)        transplant(zNode, zNode->r);    else if(zNode->r == NULL)        transplant(zNode, zNode->l);    else    {        TreeNode* y = minNode(zNode->r);        if(y->p != zNode)        {            transplant(y, y->r);            y->r = zNode->r;            y->r->p = y;        }        transplant(zNode, y);        y->l = zNode->l;        y->l->p = y;    }}int main(){    /**     * 二叉搜索树,左子树的所有结点小于等于根结点,右子树的所有结点大于根节点     */    for(int i = 0; i < MAX; i++)    {        int k = getRandom();        a[i] = k;        insertNode(k);    }    for(int i = 0; i < MAX; i++)        cout << a[i] << " ";    cout << endl;    inOrder(root);    cout << endl;    cout << "最大值" << maxNode(root)->key << endl;    cout << "最小值" << minNode(root)->key << endl;    TreeNode* zNode = findNode(root, a[tIndex]);    TreeNode* aNode = afterNode(zNode);    if(aNode != NULL)        cout << a[tIndex] << "的后继结点" << aNode->key << endl;    else        cout << a[tIndex] << "没有后继结点" << endl;    //TODO删除一个结点    cout << "删除结点" << a[tIndex] << endl;    deleteNode(zNode);    inOrder(root);    return 0;}