BST

发布于 3 天前  16 次阅读


参考地址
参考代码中的第125行左右的逻辑有误,进行了修改

#include <iostream>
#include <stdio.h>
using namespace std;
struct Node
{
    int data;
    Node* left;
    Node* right;
};
void bsearsh(Node* root)
{
    if (root == 0)
        return;
    bsearsh(root->left);
    bsearsh(root->right);
    printf("%d ", root->data);
}
void fsearsh(Node* root)
{
    if (root == 0)
        return;
    printf("%d ", root->data);
    fsearsh(root->left);
    fsearsh(root->right);
}
void insert(Node*& root, int x)
{
    if (root == 0)
    {
        root = new Node;
        root->left = 0;
        root->right = 0;
        root->data = x;
        return;
    }
    if (x > root->data) insert(root->right, x);
    else if (x == root->data) return;
    else if (x < root->data) insert(root->left, x);
}
void search(Node*& root, int x, Node**& ans)
{
    if (root == 0)
    {
        ans = 0;
        return;
    }
    if (x < root->data) search(root->left, x, ans);
    else if (x == root->data)
    {
        ans = &root;
        return;
    }
    else if (x > root->data) search(root->right, x, ans);
}
bool myDelete(Node*& root, int x)
{
    Node** node;
    search(root, x, node);
    if (node == 0)
        return false;
    Node* temp = *node;
    if ((*node)->left == 0 && (*node)->right == 0)
    {
        *node = 0;
        delete temp;
    }
    else if ((*node)->left == 0)
    {
        *node = (*node)->right;
        delete temp;
    }
    else if ((*node)->right == 0)
    {
        *node = (*node)->left;
        delete temp;
    }
    else
    {
        Node* s = (*node)->right;
        Node* father = *node;
        while (s->left != 0)
        {
            father = s;
            s = s->left;
        }
        temp->data = s->data;
        if (s->right != 0)
        {
            if (father == *node) father->right = s->right;
            else father->left = s->right;
        }
        else father->right = 0;
        delete s;   
    }
    return true;
}
int main()
{
    Node* root = new Node;
    root->left = 0;
    root->right = 0;
    root->data = 0;
    int x;
    while (scanf("%d", &x) != EOF)
    {
        if (root->data == 0)
            root->data = x;
        else
            insert(root, x);
        if (cin.get() == '\n')
            break;
    }
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        insert(root, x);
        fsearsh(root);
        printf("\n");
    }
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &x);
        if (myDelete(root, x))
        {
            bsearsh(root);
            printf("\n");
        }
        else printf("Delete Error\n");
    }
}

「雪霁融雾月,冰消凝夜雨」