用二叉排序树写通讯录管理系统

二叉排序树是一种基于二叉树的数据结构，它的每个节点都有一个关键字，而且左子树上的所有节点的关键字都小于父节点的关键字，右子树上的所有节点的关键字都大于父节点的关键字。这样，我们可以通过比较节点的关键字来快速查找、插入和删除数据。在通讯录管理系统中，我们可以使用二叉排序树来实现联系人的添加、查找和删除操作。

首先，我们需要定义二叉排序树的节点结构体：

typedef struct TreeNode {
    string name; // 联系人姓名
    string tel; // 联系人电话
    struct TreeNode *left; // 左子树
    struct TreeNode *right; // 右子树
} TreeNode, *Tree;

然后，我们可以定义一些辅助函数，比如创建节点、插入节点、查找节点等：

// 创建节点
Tree createNode(string name, string tel) {
    Tree node = new TreeNode;
    node->name = name;
    node->tel = tel;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 插入节点
Tree insertNode(Tree root, string name, string tel) {
    if (root == NULL) {
        return createNode(name, tel);
    }
    if (name < root->name) {
        root->left = insertNode(root->left, name, tel);
    } else if (name > root->name) {
        root->right = insertNode(root->right, name, tel);
    } else {
        // 如果姓名已经存在，则更新电话号码
        root->tel = tel;
    }
    return root;
}

// 查找节点
Tree searchNode(Tree root, string name) {
    if (root == NULL || root->name == name) {
        return root;
    }
    if (name < root->name) {
        return searchNode(root->left, name);
    } else {
        return searchNode(root->right, name);
    }
}

接下来，我们可以定义一些用户界面函数，比如添加联系人、查找联系人、删除联系人等：

// 添加联系人
void addContact(Tree &root) {
    string name, tel;
    cout << "请输入联系人姓名：";
    cin >> name;
    cout << "请输入联系人电话：";
    cin >> tel;
    root = insertNode(root, name, tel);
    cout << "添加成功！" << endl;
}

// 查找联系人
void searchContact(Tree root) {
    string name;
    cout << "请输入要查找的联系人姓名：";
    cin >> name;
    Tree node = searchNode(root, name);
    if (node == NULL) {
        cout << "未找到联系人！" << endl;
    } else {
        cout << "联系人姓名：" << node->name << endl;
        cout << "联系人电话：" << node->tel << endl;
    }
}

// 删除联系人
Tree deleteNode(Tree root, string name) {
    if (root == NULL) {
        return root;
    }
    if (name < root->name) {
        root->left = deleteNode(root->left, name);
    } else if (name > root->name) {
        root->right = deleteNode(root->right, name);
    } else {
        // 找到要删除的节点
        if (root->left == NULL) {
            Tree temp = root->right;
            delete root;
            return temp;
        } else if (root->right == NULL) {
            Tree temp = root->left;
            delete root;
            return temp;
        }
        Tree temp = root->right;
        while (temp->left != NULL) {
            temp = temp->left;
        }
        root->name = temp->name;
        root->tel = temp->tel;
        root->right = deleteNode(root->right, temp->name);
    }
    return root;
}

void removeContact(Tree &root) {
    string name;
    cout << "请输入要删除的联系人姓名：";
    cin >> name;
    Tree node = searchNode(root, name);
    if (node == NULL) {
        cout << "未找到联系人！" << endl;
    } else {
        root = deleteNode(root, name);
        cout << "删除成功！" << endl;
    }
}

最后，我们可以定义一个主函数，来实现整个程序的逻辑：

int main() {
    Tree root = NULL;
    int choice;
    while (true) {
        cout << "通讯录管理系统" << endl;
        cout << "1. 添加联系人" << endl;
        cout << "2. 查找联系人" << endl;
        cout << "3. 删除联系人" << endl;
        cout << "4. 退出系统" << endl;
        cout << "请选择操作：";
        cin >> choice;
        switch (choice) {
            case 1:
                addContact(root);
                break;
            case 2:
                searchContact(root);
                break;
            case 3:
                removeContact(root);
                break;
            case 4:
                exit(0);
                break;
            default:
                cout << "无效操作！" << endl;
                break;
        }
    }
    return 0;
}

这样，我们就完成了一个基于二叉排序树的通讯录管理系统。用户可以通过菜单来进行添加、查找和删除联系人等操作。