二叉排序树建立与查找

二叉排序树的建立已经在上一个问题中介绍过了，这里给出二叉排序树的查找操作。

二叉排序树的查找操作也很简单，基本思路就是从根节点开始，逐个比较节点的值，直到找到目标节点或者遍历到叶子节点为止。

代码实现如下：

// 在二叉排序树中查找指定值
TreeNode* searchBST(TreeNode* root, int val) {
    if (!root) return NULL;
    if (root->val == val) return root;
    if (val < root->val) {
        return searchBST(root->left, val);
    } else {
        return searchBST(root->right, val);
    }
}

其中，searchBST 函数接收一个二叉排序树的根节点 root 和一个目标值 val，返回值为指向目标节点的指针。如果找不到目标节点，返回 NULL。

需要注意的是，这里的查找操作是基于二叉排序树的性质进行的，因此时间复杂度为 O(log n)，其中 n 为节点个数。当二叉排序树退化为链表时，查找操作最坏情况下会达到 O(n) 的时间复杂度。因此，在实际应用中，我们需要对二叉排序树进行平衡处理，以保证其效率。

相关问题

根据二叉排序树的抽象数据类型的定义,使用二叉链表实现一个二叉排序树。 二叉排序树的基本功能: 1、二叉排序树的建立 2、二叉排序树的查找 3、二叉排序树的插入 4、二叉排序树的删除 5、二叉排序树的销毁 6、其他:

好的，根据您的要求，我可以为您提供一个二叉排序树的基本实现。请注意，以下代码仅供参考，需要根据具体需求进行修改和完善。

#include <iostream>

using namespace std;

// 二叉排序树节点结构体
struct BSTNode {
    int data;           // 数据
    BSTNode* left;      // 左子树指针
    BSTNode* right;     // 右子树指针
};

// 二叉排序树类
class BinarySearchTree {
public:
    BinarySearchTree() { root = NULL; }       // 构造函数
    ~BinarySearchTree() { Destroy(root); }    // 析构函数
    
    // 基本功能
    void Insert(int data);             // 插入节点
    bool Search(int data) const;       // 查找节点
    void Delete(int data);             // 删除节点
    void Destroy(BSTNode* node);       // 销毁二叉排序树
    
    // 其他功能
    void InOrderTraversal() const;     // 中序遍历
    int Height() const;                // 树的高度

private:
    BSTNode* root;      // 根节点指针
    
    // 私有函数
    void Insert(BSTNode*& node, int data);        // 插入节点
    bool Search(BSTNode* node, int data) const;   // 查找节点
    void Delete(BSTNode*& node, int data);        // 删除节点
    BSTNode* FindMin(BSTNode* node) const;        // 查找最小节点
    void InOrderTraversal(BSTNode* node) const;   // 中序遍历
    int Height(BSTNode* node) const;              // 树的高度
};

// 插入节点
void BinarySearchTree::Insert(int data) {
    Insert(root, data);
}

void BinarySearchTree::Insert(BSTNode*& node, int data) {
    if (node == NULL) {
        node = new BSTNode;
        node->data = data;
        node->left = node->right = NULL;
    }
    else if (data < node->data) {
        Insert(node->left, data);
    }
    else if (data > node->data) {
        Insert(node->right, data);
    }
}

// 查找节点
bool BinarySearchTree::Search(int data) const {
    return Search(root, data);
}

bool BinarySearchTree::Search(BSTNode* node, int data) const {
    if (node == NULL) {
        return false;
    }
    else if (data < node->data) {
        return Search(node->left, data);
    }
    else if (data > node->data) {
        return Search(node->right, data);
    }
    else {
        return true;
    }
}

// 删除节点
void BinarySearchTree::Delete(int data) {
    Delete(root, data);
}

void BinarySearchTree::Delete(BSTNode*& node, int data) {
    if (node == NULL) {
        return;
    }
    else if (data < node->data) {
        Delete(node->left, data);
    }
    else if (data > node->data) {
        Delete(node->right, data);
    }
    else {
        if (node->left == NULL && node->right == NULL) {
            delete node;
            node = NULL;
        }
        else if (node->left == NULL) {
            BSTNode* temp = node;
            node = node->right;
            delete temp;
        }
        else if (node->right == NULL) {
            BSTNode* temp = node;
            node = node->left;
            delete temp;
        }
        else {
            BSTNode* temp = FindMin(node->right);
            node->data = temp->data;
            Delete(node->right, temp->data);
        }
    }
}

// 查找最小节点
BSTNode* BinarySearchTree::FindMin(BSTNode* node) const {
    if (node == NULL) {
        return NULL;
    }
    else if (node->left == NULL) {
        return node;
    }
    else {
        return FindMin(node->left);
    }
}

// 销毁二叉排序树
void BinarySearchTree::Destroy(BSTNode* node) {
    if (node != NULL) {
        Destroy(node->left);
        Destroy(node->right);
        delete node;
    }
}

// 中序遍历
void BinarySearchTree::InOrderTraversal() const {
    InOrderTraversal(root);
}

void BinarySearchTree::InOrderTraversal(BSTNode* node) const {
    if (node != NULL) {
        InOrderTraversal(node->left);
        cout << node->data << " ";
        InOrderTraversal(node->right);
    }
}

// 树的高度
int BinarySearchTree::Height() const {
    return Height(root);
}

int BinarySearchTree::Height(BSTNode* node) const {
    if (node == NULL) {
        return 0;
    }
    else {
        int leftHeight = Height(node->left);
        int rightHeight = Height(node->right);
        return (leftHeight > rightHeight) ? (leftHeight + 1) : (rightHeight + 1);
    }
}

int main() {
    BinarySearchTree bst;
    
    bst.Insert(8);
    bst.Insert(3);
    bst.Insert(10);
    bst.Insert(1);
    bst.Insert(6);
    bst.Insert(9);
    bst.Insert(14);
    bst.Insert(4);
    bst.Insert(7);
    bst.Insert(13);
    
    cout << "中序遍历: ";
    bst.InOrderTraversal();
    cout << endl;
    
    cout << "树的高度: " << bst.Height() << endl;
    
    cout << "查找节点: " << endl;
    cout << "3: " << bst.Search(3) << endl;
    cout << "5: " << bst.Search(5) << endl;
    
    cout << "删除节点: " << endl;
    bst.Delete(1);
    bst.Delete(3);
    bst.Delete(13);
    bst.Delete(8);
    bst.Delete(10);
    
    cout << "中序遍历: ";
    bst.InOrderTraversal();
    cout << endl;
    
    cout << "树的高度: " << bst.Height() << endl;
    
    return 0;
}

以上代码实现了二叉排序树的基本功能，包括插入节点、查找节点、删除节点、销毁二叉排序树等。另外，还实现了中序遍历和求树的高度等其他功能。在使用时，可以根据具体需求进行调用。

用c++一段代码实现二叉排序树的建立；二叉排序树的查找；二叉排序树的插入； 二叉排序树的删除；二叉排序树的销毁；

以下是用C++实现二叉排序树的建立、查找、插入、删除和销毁的代码示例：

1. 二叉排序树的建立：

#include <iostream>
using namespace std;

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

TreeNode* insert(TreeNode* root, int val) {
    if (root == NULL) {
        return new TreeNode(val);
    }
    if (val < root->val) {
        root->left = insert(root->left, val);
    } else {
        root->right = insert(root->right, val);
    }
    return root;
}

TreeNode* buildBST(int arr[], int n) {
    TreeNode* root = NULL;
    for (int i = 0; i < n; i++) {
        root = insert(root, arr[i]);
    }
    return root;
}

2. 二叉排序树的查找：

TreeNode* search(TreeNode* root, int val) {
    if (root == NULL || root->val == val) {
        return root;
    }
    if (val < root->val) {
        return search(root->left, val);
    } else {
        return search(root->right, val);
    }
}

3. 二叉排序树的插入：

TreeNode* insert(TreeNode* root, int val) {
    if (root == NULL) {
        return new TreeNode(val);
    }
    if (val < root->val) {
        root->left = insert(root->left, val);
    } else {
        root->right = insert(root->right, val);
    }
    return root;
}

4. 二叉排序树的删除：

TreeNode* findMin(TreeNode* root) {
    while (root->left != NULL) {
        root = root->left;
    }
    return root;
}

TreeNode* deleteNode(TreeNode* root, int val) {
    if (root == NULL) {
        return root;
    }
    if (val < root->val) {
        root->left = deleteNode(root->left, val);
    } else if (val > root->val) {
        root->right = deleteNode(root->right, val);
    } else {
        if (root->left == NULL) {
            TreeNode* temp = root->right;
            delete root;
            return temp;
        } else if (root->right == NULL) {
            TreeNode* temp = root->left;
            delete root;
            return temp;
        }
        TreeNode* temp = findMin(root->right);
        root->val = temp->val;
        root->right = deleteNode(root->right, temp->val);
    }
    return root;
}

5. 二叉排序树的销毁：

void destroy(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    destroy(root->left);
    destroy(root->right);
    delete root;
}