二叉查找树

二叉查找树的查找遍历插入删除

/*
 * @Author: Mr.Sen
 * @LastEditTime: 2020-12-26 15:55:44
 * @Description: 二叉树查找
 * @Website: https://grimoire.cn
 * @Copyright (c) Mr.Sen All rights reserved.
 */
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
const int M = 1e9 + 10;

typedef struct node
{
    int data;
    node *l, *r;
} node, *tNode;

tNode search(tNode cur, int key)
{
    if (cur == NULL || cur->data == key)
        return cur;
    else if (cur->data > key)
        return search(cur->l, key);
    else
        return search(cur->r, key);
}

void insert(tNode &cur, int key)
{
    if (cur == NULL)
    {
        tNode s = new node;
        s->data = key;
        s->l = NULL;
        s->r = NULL;
        cur = s;
    }
    else if (cur->data > key)
        insert(cur->l, key);
    else
        insert(cur->r, key);
}

bool deleteNode(tNode &s, int key)
{
    tNode p = s;
    tNode f = NULL;
    while (p->data != key && p != NULL)
    {
        f = p;
        if (p->data < key)
            p = p->r;
        else
            p = p->l;
    }
    if (p == NULL)
        return false;

    if (p->l == NULL && p->r == NULL)
    {
        // * 叶子节点
        cout << "CUR:" << p->data << endl;
        if (f->l == p)
        {
            f->l = NULL;
            delete p;
        }
        else
        {
            f->r = NULL;
            delete p;
        }
        return true;
    }

    if (p->l != NULL && p->r != NULL)
    {
        // * 有两个子节点
        tNode minP = p->r;
        tNode minF = p;
        while (minP->l)
        {
            minF = minP;
            minP = minP->l;
        }
        if (minF == p)
        {
            p->data = p->l->data;
            delete p->l;
            p->l = NULL;
        }
        else
        {
            p->data = minP->data;
            minF->l = NULL;
            delete minP;
        }

        return true;
    }

    if (p->l != NULL || p->r != NULL)
    {
        // * 只有一个子节点
        if (f->l == p)
        {
            if (p->l)
                f->l = p->l;
            else
                f->l = p->r;
        }
        else
        {
            if (p->l)
                f->r = p->l;
            else
                f->r = p->r;
        }
        cout << "!!:" << endl;
        return true;
    }
}

void forEach(tNode s)
{
    if (s != NULL)
    {
        cout << s->data << " ";
        forEach(s->l);

        forEach(s->r);
    }
}
int main()
{
    // freopen("1.in", "r", stdin);
    // freopen("output.out","w", stdout);
    tNode head = NULL;
    int x;
    while (cin >> x && x != 0)
    {
        insert(head, x);
    }
    forEach(head);
    cout << endl;

    cout << deleteNode(head, 6) << endl;
    search(head, 6) == NULL ? cout << "deleted!" << endl : cout << "Exist!" << endl;
    forEach(head);
    cout << endl;
    return 0;
}

/*
* sample input:
1 2 6 3 8 5 7 9 0
*/