BST(二叉搜索树)

问题描述

编写C++程序来实现执行以下操作：

1. 向二叉搜索树中插入一个元素

2. 从二叉搜索树中删除一个元素

3. 显示所有叶子节点

4. 遍历给定的二叉树

   • 深度优先算法
     • 中序遍历
     • 前序遍历

程序描述：

这个程序旨在通过各种操作来管理一个二叉搜索树（BST），如插入、删除、显示叶子节点和根据用户选择的方式遍历树。BST是一个基本的数据结构，它保持元素以排序的顺序存储，以便高效地进行搜索、插入和删除操作。每个节点包含一个键值和指向左右子节点的指针。节点的左子树仅包含键值小于该节点键值的节点，而右子树仅包含键值大于该节点键值的节点。

该程序实现的操作包括：

• 插入：提示用户依次输入元素到BST中。
• 删除：询问用户要从BST中删除的特定元素。
• 显示叶子节点：遍历BST并显示所有叶子节点（没有子节点的节点）。
• 树遍历：允许用户选择中序遍历和前序遍历方法来遍历和显示树。

实现代码

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
using namespace std;

// 定义树的节点
class Node {
public:
    int key; // 节点存储的值
    Node* left, * right; // 指向左子节点和右子节点的指针

    // 节点构造函数
    Node(int item) {
        key = item;
        left = right = nullptr; // 初始化时没有子节点
    }
};

// 二叉搜索树类
class BST {
private:
    // 插入新节点的辅助函数
    Node* insert(Node* node, int key) {
        if (node == nullptr) return new Node(key); // 如果当前节点为空，创建新节点

        // 根据二叉搜索树的性质进行递归插入
        if (key < node->key)
            node->left = insert(node->left, key); // 插入到左子树
        else if (key > node->key)
            node->right = insert(node->right, key); // 插入到右子树

        return node;
    }

    // 查找并返回具有最小键值的节点的辅助函数
    Node* minValueNode(Node* node) {
        Node* current = node;
        // 持续向左子节点移动，直到找到最左侧节点
        while (current && current->left != nullptr)
            current = current->left;
        return current;
    }

    // 删除节点的辅助函数
    Node* deleteNode(Node* root, int key) {
        if (root == nullptr) return root; // 如果根为空，直接返回

        // 根据键值进行递归删除
        if (key < root->key)
            root->left = deleteNode(root->left, key); // 从左子树删除
        else if (key > root->key)
            root->right = deleteNode(root->right, key); // 从右子树删除
        else {
            // 找到了要删除的节点
            if (root->left == nullptr) {
                Node* temp = root->right;
                delete root; // 删除当前节点
                return temp; // 返回右子树
            }
            else if (root->right == nullptr) {
                Node* temp = root->left;
                delete root; // 删除当前节点
                return temp; // 返回左子树
            }

            // 节点有两个子节点的情况
            Node* temp = minValueNode(root->right); // 找到右子树中的最小节点
            root->key = temp->key; // 替换当前节点的键值
            // 删除右子树中的最小节点
            root->right = deleteNode(root->right, temp->key);
        }
        return root;
    }

    // 中序遍历的辅助函数
    void inorderTraversal(Node* root) {
        if (root != nullptr) {
            inorderTraversal(root->left); // 先左子树
            cout << root->key << " "; // 再根节点
            inorderTraversal(root->right); // 最后右子树
        }
    }

    // 前序遍历的辅助函数
    void preorderTraversal(Node* root) {
        if (root != nullptr) {
            cout << root->key << " "; // 先根节点
            preorderTraversal(root->left); // 再左子树
            preorderTraversal(root->right); // 最后右子树
        }
    }

    // 显示所有叶子节点的辅助函数
    void displayLeafNodes(Node* root) {
        if (root != nullptr) {
            if (root->left == nullptr && root->right == nullptr) {
                cout << root->key << " "; // 如果是叶子节点，打印其键值
            }
            // 递归检查左右子树
            displayLeafNodes(root->left);
            displayLeafNodes(root->right);
        }
    }

public:
    Node* root; // 树的根节点

    // 构造函数
    BST() {
        root = nullptr; // 初始化时树为空
    }

    // 插入新节点
    void insert(int key) {
        root = insert(root, key);
    }

    // 删除节点
    void deleteNode(int key) {
        root = deleteNode(root, key);
    }

    // 中序遍历函数
    void inorderTraversal() {
        cout << "InOrder Traversal: ";
        inorderTraversal(root);
        cout << endl;
    }

    // 前序遍历函数
    void preorderTraversal() {
        cout << "PreOrder Traversal: ";
        preorderTraversal(root);
        cout << endl;
    }

    // 显示所有叶子节点的函数
    void displayLeafNodes() {
        cout << "Leaf nodes: ";
        displayLeafNodes(root);
        cout << endl;
    }
};

// 主函数
int main() {
    BST bst; // 创建一个二叉搜索树实例
    int n, x;
    bool f = 0; // 用于控制是否打印分隔线
    while (1) {
        if (f) {
            cout << "--------------------------------\n";
        }
        f = 1;
        printf("1. Insert Element into BST\n2. Delete Element from BST\n3. Display all leaf nodes\n4. Traverse the BST\n5. Exit\n");
        cout << "Enter your choice: "; cin >> n;
        switch (n)
        {
        case 1: // 插入元素
            cout << "Enter key to insert: ";
            cin >> x;
            bst.insert(x);
            break;
        case 2: // 删除元素
            cout << "Enter key to delete: ";
            cin >> x;
            bst.deleteNode(x);
            break;
        case 3: // 显示所有叶子节点
            bst.displayLeafNodes();
            break;
        case 4: // 选择遍历方法
            cout << "Choose traversal method (1 for InOrder, 2 for PreOrder): ";
            int m; cin >> m;
            if (m == 1) bst.inorderTraversal(); // 中序遍历
            else if (m == 2) bst.preorderTraversal(); // 前序遍历
            break;
        case 5: // 退出程序
            return 0;
        }
    }
}