二叉排序树二叉搜索树

二叉排序树（Binary Search Tree, BST），也称为二叉搜索树，是一种特殊的二叉树，它满足以下性质：

每个节点的值大于或等于其左子树上所有节点的值。
每个节点的值小于或等于其右子树上所有节点的值。
左子树和右子树也分别是二叉排序树。

这些特性确保了二叉排序树可以被用来有效地执行查找、插入和删除操作。

使用指针实现二叉排序树

下面是使用指针实现二叉排序树的一个简单示例：

#include <iostream>

struct TreeNode {
    int value;
    TreeNode *left, *right;

    TreeNode(int val) : value(val), left(nullptr), right(nullptr) {}
};

// 插入节点
TreeNode* insert(TreeNode* root, int value) {
    if (root == nullptr) {
        return new TreeNode(value);
    }
    if (value < root->value) {
        root->left = insert(root->left, value);
    } else if (value > root->value) {
        root->right = insert(root->right, value);
    }
    // 如果value等于root->value，不插入重复的值
    return root;
}

// 中序遍历
void inOrder(TreeNode* root) {
    if (root != nullptr) {
        inOrder(root->left);
        std::cout << root->value << " ";
        inOrder(root->right);
    }
}

// 删除节点（简单示例，不处理所有情况）
TreeNode* deleteNode(TreeNode* root, int value) {
    if (root == nullptr) return root;

    if (value < root->value) {
        root->left = deleteNode(root->left, value);
    } else if (value > root->value) {
        root->right = deleteNode(root->right, value);
    } else {
        // 要删除的节点有两个子节点的情况需要更复杂的处理
        if (root->left == nullptr) {
            TreeNode* temp = root->right;
            delete root;
            return temp;
        } else if (root->right == nullptr) {
            TreeNode* temp = root->left;
            delete root;
            return temp;
        }

        // 找到右子树的最小值节点
        root->value = minValue(root->right);
        // 删除右子树的最小值节点
        root->right = deleteNode(root->right, root->value);
    }
    return root;
}

// 找到二叉排序树中的最小值
int minValue(TreeNode* node) {
    while (node && node->left != nullptr) {
        node = node->left;
    }
    return node->value;
}

// 释放二叉排序树占用的内存
void deleteTree(TreeNode* node) {
    if (node) {
        deleteTree(node->left);
        deleteTree(node->right);
        delete node;
    }
}

int main() {
    TreeNode* root = nullptr;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

    std::cout << "Inorder traversal of the binary search tree: ";
    inOrder(root);

    root = deleteNode(root, 20);

    std::cout << "\nInorder traversal after deletion: ";
    inOrder(root);

    deleteTree(root);
    return 0;
}

使用数组实现二叉排序树

使用数组实现二叉排序树通常是为了实现二叉堆，但对于完全二叉树，数组也可以通过计算每个节点的父节点和子节点的索引来实现。

#include <iostream>
#include <vector>

class BinarySearchTree {
private:
    std::vector<int> tree;

public:
    BinarySearchTree() {}

    // 插入节点
    void insert(int value) {
        tree.push_back(value);
        int index = tree.size() - 1;
        while (index > 0) {
            int parentIndex = (index - 1) / 2;
            if (tree[parentIndex] > tree[index]) {
                std::swap(tree[parentIndex], tree[index]);
                index = parentIndex;
            } else {
                break;
            }
        }
    }

    // 中序遍历
    void inOrder(int index) {
        if (index >= 0 && index < tree.size()) {
            inOrder(2 * index + 1); // 遍历左子树
            std::cout << tree[index] << " ";
            inOrder(2 * index + 2); // 遍历右子树
        }
    }

    // 释放数组占用的内存
    ~BinarySearchTree() {
        tree.clear();
    }
};

int main() {
    BinarySearchTree bst;
    bst.insert(50);
    bst.insert(30);
    bst.insert(20);
    bst.insert(40);
    bst.insert(70);
    bst.insert(60);
    bst.insert(80);

    std::cout << "Inorder traversal of the binary search tree: ";
    bst.inOrder(0); // 从根节点开始中序遍历

    return 0;
}

在数组实现中，我们使用2 * index + 1来获取左子节点的索引，使用2 * index + 2来获取右子节点的索引。插入操作后，可能需要通过"上浮"过程来保持二叉排序树的性质。数组实现通常在处理完全二叉树时更为常见，因为它们可以高效地利用内存。

二叉排序树（Binary Sort Tree）和二叉搜索树（Binary Search Tree，简称BST）实际上是同一个概念的两种不同叫法。

它们描述的是同一种数据结构，具有以下特性：

每个节点的值：对于树中的任意节点，其左子树上所有节点的值均小于该节点的值，其右子树上所有节点的值均大于该节点的值。
二叉树结构：它是一棵二叉树，即每个节点最多有两个子节点。
排序性质：树中所有节点的组织方式满足排序的性质，即中序遍历这棵树可以得到一个有序的节点值序列。

这种数据结构常用于实现动态集合，可以高效地支持以下操作：

查找（Search）：由于树的有序性，可以在对数时间复杂度内完成查找操作。
插入（Insert）：新插入的节点会根据已有节点的值被放置在正确的位置，以保持树的有序性。
删除（Delete）：删除操作需要找到待删除的节点，并进行适当的重新组织以保持树的有序性。

二叉搜索树是计算机科学中非常基础和重要的数据结构，广泛应用于数据库索引、搜索算法、操作系统的内存管理等领域。由于其高效的查找和更新操作，二叉搜索树是实现排序和索引的理想选择之一。

(责任编辑：admin)

热门: