二分搜索树系列之「特性及完整源代码-code」

二分搜索树特性及完整源代码

一.特性

1.顺序性

二分搜索树可以当做查找表的一种实现。

我们使用二分搜索树的目的是通过查找 key 马上得到 value。minimum、maximum、successor(后继)、predecessor(前驱)、floor(地板)、ceil(天花板、rank(排名第几的元素)、select(排名第n的元素是谁)这些都是二分搜索树顺序性的表现。

2.局限性

二分搜索树在时间性能上是具有局限性的。

如下图所示,元素节点一样,组成两种不同的二分搜索树,都是满足定义的:

二分搜索树系列之【特性及完整源代码-code】

二叉搜索树可能退化成链表,相应的,二叉搜索树的查找操作是和这棵树的高度相关的,而此时这颗树的高度就是这颗树的节点数 n,同时二叉搜索树相应的算法全部退化成 O(n) 级别。

二.完整代码

前面我们将了二分搜索树元素的插入、查找、遍历删除等,我将完整的源码放在这里了:

#include <iostream>
#include <queue>
#include <cassert>
using namespace std;

//套用模板函数
template <typename Key, typename Value>
class BST {
private:
    //构造节点Node
  struct Node {
        Key key;
  Value value;
  Node *left;
  Node *right;

  Node(Key key, Value value) {
             this->key = key;
             this->value = value;
  //初始值为空
             this->left = this->right = NULL;
  }
        Node(Node *node){
            this->key = node->key;
            this->value = node->value;
            this->left = node->left;
            this->right = node->right;
         }
    };

  //根节点
  Node *root;
  //节点数量
  int count;

public:
    BST() {
        //初始值为空
  root = NULL;
  count = 0;
  }

    ~BST() {
        distroy(root);
  }

    int size() {
        return count;
  }

    bool isEmpty() {
        return count == 0;
  }

    //插入操作
  void insert(Key key, Value value) {
        //向根节点中插入key, value
         root = insert(root, key, value);
  }

    //在树中寻找是否存在key
  bool contain(Key key) {
         return contain(root, key);
  }

    //找到key相应的节点并且返回value的地址
  Node *seacher(Key key, Value value) {
          return seacher(root, key, value);
  }

    //前序遍历,传入节点,打印节点相应信息
  void preOrder() {
        return preOrder(root);
  }

    //中序遍历,以节点为node的节点为根节点
  void inOrder() {
        return inOrder(root);
  }

    //后序遍历,以node为根节点的二分搜索树进行前序遍历,打印节点相应信息
  void postOrder() {
        return postOrder(root);
  }

    //层序遍历
  void levelOrder(){
        queue<Node*> q;
        q.push(root);
  //队列不为空的情况
  while(!q.empty()){
            Node *node  = q.front();
            q.pop();

            cout<<node->key<<endl;
            if(node->left)
                q.push(node->left);
            if(node->right)
                q.push(node->right);
  }
    }

    // 寻找二分搜索树的最小的键值
  Node* minmum(){
        assert(count != 0);
        Node* minnode = minmum(root);
        return minnode->left;
  }

    // 寻找二分搜索树的最大的键值
  Node* maxmum(){
        assert(count != 0);
        Node* maxnode = maxmum(root);
        return maxnode ->right;
  }

    //删除最小值的node
  void removeMin(){
        if(root)
            root = removeMin(root);
  }

    //删除最大值的node
  void removeMax(){
        if(root)
            root = removeMax(root);
  }

    //删除二分搜索树中值的任意节点
  void remove( Key key){
        root = remove(root, key);
  }

private:
    //插入操作
 //向以node为根节点的二分搜索树中,插入节点(key,value),使用递归算法 //返回插入新节点后的二分搜索树的根 
 Node *insert(Node *node, Key key, Value value) {
        if (node == NULL) {
            count++;
            return new Node(key, value);
  }

        if (key == node->key) {
            node->value = value;
         } 
        else if (key > node->key) {
            node->right = insert(node->right, key, value);
  }
        else //key < node->key
            node->left = insert(node->left, key, value);
  }

    //在二分搜索树中查找key,存在返回trun不存在返回false
  bool contain(Node *node, Key key) {
        //元素不存在
       if (key == NULL)
            return false;
  //元素存在
       if (key == node->key)
            return true;

       else if (key > node->key)
            return contain(node->right, key);

       else return contain(node->left, key);
  }

    //在二分搜索树中找到相应元素并返回该元素的地址
  Value *seacher(Node *node, Key key) {
        if (key == NULL)
            return NULL;
  //找到key 返回value的地址
        if (key == node->key)
            return &(node->value);

        else if (key > node->key)
            return seacher(node->right, key);

        else 
            return seacher(node->left, key);
  }

    //前序遍历,以node为根节点的二分搜索树进行前序遍历,打印节点相应信息
  void preOrder(Node *node) {
        if (node != NULL) {
            //不一定用打印,还可以对node->key和node->value进行操作
               cout << node->key << endl;

               preOrder(node->left);

               preOrder(node->right);
         }
   }

    //中序遍历,以node为根节点的二分搜索树进行前序遍历,打印节点相应信息
  void inOrder(Node *node) {
        if (node != NULL) {
            inOrder(node->left);

            cout << node->key << endl;

            inOrder(node->right);
       }
  }

    //后序遍历,以node为根节点的二分搜索树进行前序遍历,打印节点相应信息
  void postOrder(Node *node) {
        if (node != NULL) {
            postOrder(node->left);

            postOrder(node->right);

            cout << node->key << endl;
         }
  }

    //析构函数的实现,其本质是后序遍历
  void distroy(Node *node) {
        if (node != NULL) {
            distroy(node->left);
            distroy(node->right);

            delete node;
            count--;

         }
  }

    // 寻找二分搜索树的最小的键值
  Node* minmum(Node* node){
            if(node != NULL){
                minmum(node->left);
             }
            return node;
  }

    // 寻找二分搜索树的最大的键值
  Node* maxmum(Node* node){
        if(node != NULL){
            maxmum(node->right);
         }
        return node;
  }

    // 从二分搜索树中删除最小值所在的节点
  Node* removeMin(Node* node){
        if(node->left == NULL){
            Node* NODE = node->right;
            delete node;
            count--;
            return NODE;
          }
         node->left = removeMax(node->left);
         return node;
  }
    //从二分搜索树中删除最大值所在的节点
  Node* removeMax(Node* node){
        if(node->right == NULL){
            Node* NODE = node->left;
            delete node;
            count--;
            return NODE;
         }
        node->right = removeMax(node->right);
        return node;
  }

    //删除二分搜索树中值的任意节点
  Node* remove(Node* node, Key key){
        //判断node是否为空
       if(node == NULL) {
            return NULL;
        }

       //先找到需要删除的值的node
       else if(key < node->key) {
            node->left =  remove(node->left, key);
            return node;
        }

        else if(key > node->key) {
            node->right = remove(node->right, key);
            return node;
        }

        //这里就找到了需要delete的node
        else {   //key == node->key)

               // 待删除节点左子树为空的情况 
                if(node->left == NULL){
                    Node* rightNode = node->right;
                    delete node;
                    count--;
                    return rightNode;
                 }
            // 待删除节点右子树为空的情况
                if(node->right == NULL){
                    Node* leftNode = node->left;
                    delete node;
                    count--;
                    return leftNode;
                 }

            // 待删除节点左右子树都不为为空的情况
                 Node *succeer =new Node(minmum(node->right)); //找到最小key值的节点返回给succeer
                 count ++;
                 succeer->right = removeMin(node->right); //将最小key值的node删除,并将返回值给succeer的右孩子

                 succeer->left = node->left;
                 delete node;
                 count--;
                 return succeer;
        }
    }
 };

void shuffle( int arr[], int n ){

    srand( time(NULL) );
 for( int i = n-1 ; i >= 0 ; i -- ){
        int x = rand()%(i+1);
  swap( arr[i] , arr[x] );
  }
}

测试也写在这里了:

// 测试 remove
int main() {

    srand(time(NULL));
    BST<int,int> bst = BST<int,int>();

  // 取n个取值范围在[0...n)的随机整数放进二分搜索树中
    int n = 10000;
    for( int i = 0 ; i < n ; i ++ ){
         int key = rand()%n;
  // 为了后续测试方便,这里value值取和key值一样
    int value = key;
    bst.insert(key,value);
    }
    // 注意, 由于随机生成的数据有重复, 所以bst中的数据数量大概率是小于n的

 // order数组中存放[0...n)的所有元素  int order[n];
   for( int i = 0 ; i < n ; i ++ )
          order[i] = i;
  // 打乱order数组的顺序
   shuffle( order , n );

  // 乱序删除[0...n)范围里的所有元素
   for( int i = 0 ; i < n ; i ++ )
        if( bst.contain( order[i] )){
            bst.remove( order[i] );
   cout<<"After remove "<<order[i]<<" size = "<<bst.size()<<endl;
  }

    // 最终整个二分搜索树应该为空
    cout << bst.size() << endl;

    return 0;
}

(图片来源:慕课网bobo老师)

本作品采用《CC 协议》,转载必须注明作者和本文链接
刻意学习
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
未填写
文章
118
粉丝
88
喜欢
173
收藏
245
排名:367
访问:2.6 万
私信
所有博文
社区赞助商