【无标题】

二叉搜索树的相关代码

#include
#include
using namespace std;
/*
    1.每一个数据都具有唯一的一个关键字
    2.比根节点关键字大的放右，比关键字小的放左
    3.二叉搜索树的任何一个字数都是二叉搜索树
    采用中序遍历
*/

//创建每一个节点的数据
struct dataPair {
    int first;                //关键字
    char second[20];    //数据
};

//创建二叉树结构体
struct TreeNode {
    dataPair data;
    TreeNode* LchildNode;
    TreeNode* RchildNode;
};

//封装一个二叉搜索树
typedef struct Binary_Search_Tree {
    TreeNode* root;            //根节点
    int Treesize;            //根中节点数
}BST, * LPBST;

//创建树
LPBST createBST() {
    LPBST tree = new BST;
    tree->root = NULL;
    tree->Treesize = 0;
    return tree;
}

//创建节点
TreeNode* createNode(dataPair data) {
    TreeNode* newNode = new TreeNode;
    newNode->data = data;
    newNode->LchildNode = NULL;
    newNode->RchildNode = NULL;
    return newNode;
}

//万金油函数
int size(LPBST tree) {
    return tree->Treesize;
}

int empty(LPBST tree) {
    return tree->Treesize == 0;
}

//遍历
void printNode(TreeNode* curNode) {
    printf("%d %s\t", curNode->data.first, curNode->data.second);
}

void middle_order(TreeNode* root) {
    if (root != NULL) {
        middle_order(root->LchildNode);
        printNode(root);
        middle_order(root->RchildNode);
    }
}

//插入节点
void insertNode(LPBST tree, dataPair data) {
    TreeNode* newNode = createNode(data);
    //找到合适的位置
    TreeNode* pmove = tree->root;
    TreeNode* pmove_Parent = NULL;        //记录NULL上一个节点
    while (pmove)
    {
        pmove_Parent = pmove;            //记录移动结点的父节点
        if (data.first < pmove->data.first) {
            pmove = pmove->LchildNode;
        }
        else if (data.first > pmove->data.first) {
            pmove = pmove->RchildNode;
        }
        else {        //关键词相同的处理方式有多种要视情况而定
            strcpy(pmove->data.second, data.second);    //修改相同关键词节点的数据
            return;
        }
    }
    if (tree->root == NULL) {
        tree->root = newNode;
    }
    else {
        if (data.first < pmove_Parent->data.first) {
            pmove_Parent->LchildNode = newNode;
        }
        else {
            pmove_Parent->RchildNode = newNode;
        }
    }
    tree->Treesize++;
}

//查找
TreeNode* research(LPBST tree, int first) {
    TreeNode* pmove = tree->root;
    if (pmove == NULL) {
        return pmove;
    }
    else {
        while (pmove->data.first != first)
        {
            if (first < pmove->data.first) {
                pmove = pmove->LchildNode;
            }
            else {
                pmove = pmove->RchildNode;
            }
            if (pmove == NULL) {
                return pmove;
            }
        }
        return pmove;
    }
}

/*
    删除:
    1.从删除的节点中的左子树去找最右边
    2.从删除的节点中的右子树去找最左边
    若没有则直接删除
*/
void erase(LPBST tree, int first) {
    TreeNode* pmove = tree->root;
    TreeNode* pmove_parent = NULL;
    while (pmove != NULL && pmove->data.first != first) {
        pmove_parent = pmove;
        if (first < pmove->data.first) {
            pmove = pmove->LchildNode;
        }
        else if (first > pmove->data.first) {
            pmove = pmove->RchildNode;
        }
        else {
            break;
        }
    }
    if (pmove == NULL) {
        puts("没有找到指定位置，无法删除！");
        return;
    }
    //左右子树都存在的情况
    if (pmove->LchildNode != NULL && pmove->RchildNode != NULL) {
        TreeNode* move_Node = pmove->LchildNode;
        TreeNode* moveNode_parent = pmove;
        //找到右边放上去
        while (move_Node->RchildNode != NULL) {
            moveNode_parent = move_Node;
            move_Node = move_Node->RchildNode;
        }
        TreeNode* newNode = createNode(move_Node->data);
        newNode->LchildNode = pmove->LchildNode;
        newNode->RchildNode = pmove->RchildNode;
        //分类讨论删除的节点
        if (pmove_parent == NULL) {
            tree->root = newNode;            //删除的节点是根节点
        }
        else if (pmove == pmove_parent->LchildNode) {
            pmove_parent->LchildNode = newNode;
        }
        else if (pmove == pmove_parent->RchildNode) {
            pmove_parent->RchildNode = newNode;
        }
        //调整二叉树
        //调整删除的指针
        //调整指针，指向要调整的节点        //只是为了方便查找可以选择不用调整指针
        if (moveNode_parent == pmove) {
            pmove_parent = newNode;
        }
        else {
            pmove_parent = moveNode_parent;
        }
        free(pmove);
        pmove = move_Node;
    }
    TreeNode* preserve_Node = NULL;
    //若删除的节点左右存在节点，则保存删除节点的下一个节点
    if (pmove->LchildNode != NULL) {
        preserve_Node = pmove->LchildNode;
    }
    else if (pmove->RchildNode != NULL) {
        preserve_Node = pmove->RchildNode;
    }
    if (pmove == tree->root) {
        tree->root = preserve_Node;
    }
    else {
        if (pmove == pmove_parent->LchildNode) {
            pmove_parent->LchildNode = preserve_Node;
        }
        else if (pmove == pmove_parent->RchildNode) {
            pmove_parent->RchildNode = preserve_Node;
        }
    }
    free(pmove);
    tree->Treesize--;
}

int main()
{
    LPBST tree = createBST();
    dataPair data[] = { 5,"蒂兰圣雪",7,"Xtreme",6,"白井黑子",2,"Altroia" };
    for (int i = 0; i < sizeof(data) / sizeof(data[0]); i++) {
        insertNode(tree, data[i]);
    }
    puts("中序遍历：");
    middle_order(tree->root);
    puts("\n查找：7");                
    printNode(research(tree, 7));
    puts("");
    erase(tree, 7);
    middle_order(tree->root);
    return 0;
}