binary search tree c++

二叉搜索树（Binary Search Tree）是一种常用的数据结构之一，是一种有序的树形结构。它的每个节点都有一个键值，且每个节点的键值大于其左子树的所有节点的键值，小于其右子树的所有节点的键值。它可以用来实现集合、映射等抽象数据类型。

对于二叉搜索树，最常见的操作是插入和查找。插入操作比较简单，首先将新节点插入到树的叶子节点上，然后利用上述的键值大小关系进行调整。查找操作也很方便，只需要从树的根节点开始，递归地与左右子树比较键值大小即可。

二叉搜索树的时间复杂度与树的高度有关，一般在理想情况下，树的高度为 O(log n)。但如果二叉搜索树不平衡，所有节点都在一条从根节点向左或向右的路径上，时间复杂度就会变为 O(n)。

为了保持二叉搜索树的平衡性，有很多优化的方法，如 AVL 树、红黑树、Treap 等，这些方法可以通过对树的旋转、颜色变换等方式来保持树的平衡，从而提升查找效率。

相关问题

Projects 1. Convert a binary search tree into a sorted circular doubly linked list 【Problem Description】 Given a binary search tree, you need to convert it into a circular doubly linked list, the elements in the linked list are sorted. For example, a binary search tree in Fig.1 is converted into a sorted circular doubly linked list in Fig.2. 【Basic Requirements】 The input data is a set of data elements to build a binary search tree, you should design algorithms to realize the conversion process and verify the accuracy of your code on multiple test data. The output includes the following: (1) Print the binary search tree (2) Traverse the binary search tree (3) Print the converted doubly linked list (4) Output all elements of the doubly linked list in positive and reverse order

【Solution】
Here is a C++ implementation of the solution to the problem:

#include <iostream>
#include <stack>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    TreeNode* treeToDoublyList(TreeNode* root) {
        if (!root) {
            return NULL;
        }
        stack<TreeNode*> s;
        TreeNode* p = root;
        TreeNode* pre = NULL;
        TreeNode* head = NULL;
        while (p || !s.empty()) {
            while (p) {
                s.push(p);
                p = p->left;
            }
            p = s.top();
            s.pop();
            if (pre) {
                pre->right = p;
                p->left = pre;
            } else {
                head = p;
            }
            pre = p;
            p = p->right;
        }
        head->left = pre;
        pre->right = head;
        return head;
    }
};

void printBST(TreeNode* root) {
    if (root) {
        printBST(root->left);
        cout << root->val << " ";
        printBST(root->right);
    }
}

void printList(TreeNode* head) {
    TreeNode* p = head;
    do {
        cout << p->val << " ";
        p = p->right;
    } while (p != head);
    cout << endl;
}

void printListReverse(TreeNode* head) {
    TreeNode* p = head->left;
    do {
        cout << p->val << " ";
        p = p->left;
    } while (p != head->left);
    cout << endl;
}

int main() {
    TreeNode* root = new TreeNode(4);
    root->left = new TreeNode(2);
    root->right = new TreeNode(5);
    root->left->left = new TreeNode(1);
    root->left->right = new TreeNode(3);

    Solution s;
    TreeNode* head = s.treeToDoublyList(root);

    cout << "Binary Search Tree: ";
    printBST(root);
    cout << endl;

    cout << "Doubly Linked List: ";
    printList(head);

    cout << "Doubly Linked List in Reverse Order: ";
    printListReverse(head);

    return 0;
}

【Explanation】
To convert a binary search tree into a sorted circular doubly linked list, we can use a stack to perform an inorder traversal of the binary search tree. During the traversal, we maintain a pointer to the previous node visited and link the current node to the previous node. After the traversal, we link the head and tail of the linked list to form a circular doubly linked list. Finally, we can print the binary search tree, traverse the doubly linked list, and output all elements in positive and reverse order.

【Example】

Input:

    4
   / \
  2   5
 / \
1   3

Output:

Binary Search Tree: 1 2 3 4 5
Doubly Linked List: 1 2 3 4 5
Doubly Linked List in Reverse Order: 5 4 3 2 1

如何用C++实现和操作二叉查找树（Binary Search Tree）的数据结构？写出完整c++代码

在C++中，你可以通过定义一个节点类（Node），然后创建一个二叉查找树类（BST）来实现二叉查找树。以下是一个简单的二叉查找树的实现，包括插入、查找和删除节点：

#include <iostream>

// 定义二叉查找树节点
class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int value) : data(value), left(nullptr), right(nullptr) {}
};

// 插入节点到二叉查找树
Node* insert(Node* root, int value) {
    if (root == nullptr)
        return new Node(value);
    
    if (value < root->data)
        root->left = insert(root->left, value);
    else
        root->right = insert(root->right, value);

    return root;
}

// 查找节点
Node* search(Node* root, int value) {
    if (root == nullptr || root->data == value)
        return root;
    
    if (value < root->data)
        return search(root->left, value);
    else
        return search(root->right, value);
}

// 删除节点（这里仅提供了一个基本版本，假设删除的是叶子节点）
Node* delete_node(Node* root, int value) {
    if (root == nullptr)
        return root;

    if (value < root->data)
        root->left = delete_node(root->left, value);
    else if (value > root->data)
        root->right = delete_node(root->right, value);
    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 = find_min(root->right);
        
        // 将该节点的数据替换为找到的最小值
        root->data = temp->data;

        // 在右子树中删除原来的最小值节点
        root->right = delete_node(root->right, temp->data);
    }
    return root;
}

// 找到右子树中的最小节点
Node* find_min(Node* node) {
    while (node->left != nullptr)
        node = node->left;
    return node;
}

int main() {
    Node* 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 << "搜索元素 20: ";
    Node* result = search(root, 20);
    if (result)
        std::cout << "Found at: " << result->data << "\n";
    else
        std::cout << "Not Found\n";

    std::cout << "删除元素 30:\n";
    root = delete_node(root, 30); 

    // ... 其他操作 ...

    return 0;
}