欧美一级特黄大片做受成人-亚洲成人一区二区电影-激情熟女一区二区三区-日韩专区欧美专区国产专区

BST二叉搜索樹

1、二叉搜索樹

創(chuàng)新互聯(lián)建站-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價比墨江網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式墨江網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋墨江地區(qū)。費用合理售后完善，10余年實體公司更值得信賴。

  (1)、逼近折半查找的查找算法；

  (2)、一般不允許出現(xiàn)重復(fù)數(shù)字，不然沒法存儲；

  (3)、滿足：左孩子數(shù)據(jù) < 根結(jié)點數(shù)據(jù) < 右孩子數(shù)據(jù)；根(父)結(jié)點比左孩子的大，比右孩子的小；

  (4)左子樹和右子樹也是二叉搜索樹；

2、為什么叫二叉搜索樹？

  如果對一顆二叉搜索樹進行中序遍歷，可以按從小到大的順序輸出，此時又叫做二叉排序樹。

如圖：

BST二叉搜索樹

3、搜索二叉樹上的操作

  全部用C++實現(xiàn)的。

  (1)、之前學(xué)習(xí)二叉樹，并沒有說什么插入，刪除操作，那是因為，沒有規(guī)律而言，怎么進行操作呢？搜索二叉樹的規(guī)律如此明顯，那么插入，刪除必是重中之中！

  (2)、我們輸入相同的數(shù)字，但是順序不同的話，生成的搜索二叉樹是不一樣的！  

  例：int ar[] = {3, 7, 9, 1, 0, 6, 4, 2,}; 和int ar[] = {7, 3, 9, 1, 0, 6, 4, 2,}; 生成的搜索二叉樹不一樣。

BST二叉搜索樹

  (3)插入函數(shù)：

重分利用搜索二叉樹的性質(zhì)：

    void insert(BSTreeNode<Type> *&t, const Type &x){
        if(t == NULL){
            t = new BSTreeNode<Type>(x);
            return;
        }else if(x < t->data){
            insert(t->leftChild, x);
        }else if(x > t->data){
            insert(t->rightChild, x);
        }else{
            return;
        }    
    }

  (4)、刪除函數(shù)：

  思想：要刪除一個有左孩子或右孩子或是葉子結(jié)點，看成一種情況，做法：保存要刪除的結(jié)點,因為傳的是引用，可以直接修改上一個結(jié)點的左孩子或右孩子，使其跨過當(dāng)前的直指下一個結(jié)點，在釋放當(dāng)前的結(jié)點空間。

  第二種情況：就是要刪除的既有左子樹，又有右子樹，此時可以有兩種做法：i>找左子樹最大的數(shù)字，覆蓋要刪除的數(shù)字，在往左子樹找這個數(shù)字刪除-->遞歸！ii>找右子樹最小的數(shù)字，覆蓋要刪除的數(shù)字，在往右子樹找這個數(shù)字刪除-->遞歸！

第一種情況圖形想法如下：

BST二叉搜索樹

刪除左邊和刪除右邊，還有是葉子結(jié)點，想法一樣。

第二種情況圖形想法如下：

BST二叉搜索樹

代碼如下：

    bool remove(BSTreeNode<Type> *&t, const Type &key){
        if(t == NULL){  //t傳的是引用，每次可以進行直接更改!
            return false;
        }

        if(key < t->data){
            remove(t->leftChild, key);
        }else if(key > t->data){
            remove(t->rightChild, key);
        }else{
            if(t->leftChild != NULL && t->rightChild != NULL){  //第二種情況
                BSTreeNode<Type> *p = t->rightChild;
                while(p->leftChild != NULL){
                    p = p->leftChild;
                }
                t->data = p->data;
                remove(t->rightChild, p->data);  //在右樹找p->data的數(shù)字進行刪除;
            }else{     //第一種情況
                BSTreeNode<Type> *p = t;
                if(t->leftChild == NULL){
                    t = t->rightChild; //引用的好處體現(xiàn)出來了;
                }else{ 
                    t = t->leftChild;  //引用的好處體現(xiàn)出來了;
                }
                    delete p;

            }
        }
        
        return true;
    }
/*  以下這個代碼是先想到的，比較容易，上面這個是經(jīng)過思考的，將三種情況看成一種情況來處理。
    bool remove(BSTreeNode<Type> *&t, const Type &key){
        if(t == NULL){
            return false;
        }

        if(key < t->data){
            remove(t->leftChild, key);
        }else if(key > t->data){
            remove(t->rightChild, key);
        }else{  //以下三種情況可以看成一種；
            if(t->leftChild == NULL && t->rightChild == NULL){
                delete t;
                t = NULL;
            }else if(t->leftChild != NULL && t->rightChild == NULL){
                BSTreeNode<Type> *p = t;
                t = t->leftChild;
                delete p;
            }else if(t->leftChild == NULL && t->rightChild != NULL){
                BSTreeNode<Type> *p = t;
                t = t->rightChild;
                delete p;
            }else{
                BSTreeNode<Type> *p = t->rightChild;
                while(p->leftChild != NULL){
                    p = p->leftChild;
                }
                t->data = p->data;
                remove(t->rightChild, p->data);
            }
        }
        
        return true;
    }
*/

4、搜索二叉樹的完整代碼、測試代碼、測試結(jié)果   

  (1)、完整代碼：

#ifndef _BSTREE_H_
#define _BSTREE_H_

#include<iostream>
using namespace std;

#define MIN_NUMBER    -8937589
#define MAX_NUMBER    99999999


template<typename Type>
class BSTree;

template<typename Type>
class BSTreeNode{
    friend class BSTree<Type>;
public:
    BSTreeNode() : data(Type()), leftChild(NULL), rightChild(NULL){}
    BSTreeNode(Type d, BSTreeNode *left = NULL, BSTreeNode *right = NULL) 
        : data(d), leftChild(left), rightChild(right){}
    ~BSTreeNode(){}
private:
    Type data;
    BSTreeNode *leftChild;
    BSTreeNode *rightChild;
};

template<typename Type>
class BSTree{
public:
    BSTree() : root(NULL){}
    BSTree<Type>& operator=(const BSTree &bst){
        if(this != &bst){
            root = copy(bst.root);
        }

        return *this;
    }
    ~BSTree(){}
public:
    void insert(const Type &x){
        insert(root, x);
    }
    void inOrder()const{
        inOrder(root);
    }
    Type Min()const{
        return Min(root);
    }
    Type Max()const{
        return Max(root);
    }
    BSTreeNode<Type>* find(const Type &key)const{
        return find(root, key);
    }
    BSTreeNode<Type> *copy(const BSTreeNode<Type> *t){
        if(t == NULL){
            return NULL;
        }
        BSTreeNode<Type> *tmp = new BSTreeNode<Type>(t->data);
        tmp->leftChild = copy(t->leftChild);
        tmp->rightChild = copy(t->rightChild);

        return tmp;
    }
    BSTreeNode<Type>* parent(const Type &key)const{
        return parent(root, key);
    }
    bool remove(const Type &key){
        return remove(root, key);
    }
protected:
    bool remove(BSTreeNode<Type> *&t, const Type &key){
        if(t == NULL){     //重點：傳的是引用
            return false;
        }

        if(key < t->data){
            remove(t->leftChild, key);
        }else if(key > t->data){
            remove(t->rightChild, key);
        }else{
            if(t->leftChild != NULL && t->rightChild != NULL){
                BSTreeNode<Type> *p = t->rightChild;
                while(p->leftChild != NULL){
                    p = p->leftChild;
                }
                t->data = p->data;
                remove(t->rightChild, p->data);
            }else{
                BSTreeNode<Type> *p = t;
                if(t->leftChild == NULL){
                    t = t->rightChild;  //可以直接更改左右孩子
                }else{
                    t = t->leftChild;   //可以直接更改左右孩子
                }
                    delete p;

            }
        }
        
        return true;
    }
/*  
    bool remove(BSTreeNode<Type> *&t, const Type &key){
        if(t == NULL){
            return false;
        }

        if(key < t->data){
            remove(t->leftChild, key);
        }else if(key > t->data){
            remove(t->rightChild, key);
        }else{  //以下三種情況可以看成一種；
            if(t->leftChild == NULL && t->rightChild == NULL){
                delete t;
                t = NULL;
            }else if(t->leftChild != NULL && t->rightChild == NULL){
                BSTreeNode<Type> *p = t;
                t = t->leftChild;
                delete p;
            }else if(t->leftChild == NULL && t->rightChild != NULL){
                BSTreeNode<Type> *p = t;
                t = t->rightChild;
                delete p;
            }else{
                BSTreeNode<Type> *p = t->rightChild;
                while(p->leftChild != NULL){
                    p = p->leftChild;
                }
                t->data = p->data;
                remove(t->rightChild, p->data);
            }
        }
        
        return true;
    }*/
    BSTreeNode<Type>* parent(BSTreeNode<Type> *t, const Type &key)const{
        if(t == NULL || t->data == key){
            return NULL;
        }
        if(t->leftChild->data == key || t->rightChild->data == key){
            return t;
        }
        if(key < t->data){
            return parent(t->leftChild, key);
        }else{
            return parent(t->rightChild, key);
        }
    }
    BSTreeNode<Type>* find(BSTreeNode<Type> *t, const Type &key)const{
        if(t == NULL){
            return NULL;
        }

        if(t->data == key){
            return t;
        }else if(key < t->data){
            return find(t->leftChild, key);
        }else{
            return find(t->rightChild, key);
        }
    }
    Type Max(BSTreeNode<Type> *t)const{
        if(t != NULL){
            while(t->rightChild){
                t = t->rightChild;
            }

            return t->data;
        }

        return MAX_NUMBER;
    }
    Type Min(BSTreeNode<Type> *t)const{
        if(t != NULL){
            while(t->leftChild){
                t = t->leftChild;
            }

            return t->data;
        }
        return MIN_NUMBER;
    }
    void inOrder(BSTreeNode<Type> *t)const{
        if(t != NULL){
            inOrder(t->leftChild);
            cout<<t->data<<" ";
            inOrder(t->rightChild);
        }
    }
    void insert(BSTreeNode<Type> *&t, const Type &x){
        if(t == NULL){
            t = new BSTreeNode<Type>(x);
            return;
        }else if(x < t->data){
            insert(t->leftChild, x);
        }else if(x > t->data){
            insert(t->rightChild, x);
        }else{
            return;
        }    
    }
private:
    BSTreeNode<Type> *root;
};
#endif

  (2)測試代碼：

#include"bstree.h"

int main(void){
    int ar[] = {3, 7, 9, 1, 0, 6, 4, 2,};
    int n = sizeof(ar) / sizeof(int);
    BSTree<int> bst;
    for(int i = 0; i < n; i++){
        bst.insert(ar[i]);
    }

    bst.inOrder();
    cout<<endl;
    cout<<bst.Min()<<endl;
    cout<<bst.Max()<<endl;
    BSTreeNode<int> *p = bst.find(6);
    BSTreeNode<int> *q = bst.parent(4);
    printf("%p %p\n", p, q);
    bst.remove(0);
    bst.inOrder();
    cout<<endl;
    return 0;
}

  (3)、測試結(jié)果：

BST二叉搜索樹

文章題目：BST二叉搜索樹
瀏覽路徑：http://aaarwkj.com/article22/peiccc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供企業(yè)網(wǎng)站制作、網(wǎng)站導(dǎo)航、企業(yè)建站、微信小程序、ChatGPT、面包屑導(dǎo)航

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)

網(wǎng)站優(yōu)化排名
国产剧免费看视频网站成人| 中文一级伦理一区二区| 欧美成人精品三级在线网站| 国内久久婷婷综合五月趴| 国产福利在线观看午夜| 国产一区二区不卡自拍| 日韩av高清在线免费观看| 人妻少妇被粗大爽av| 国产传媒免费在线播放| 国产日韩欧美 一区二区三区| 免费高清av一区二区| 欧美日韩精品福利一区二区| 美女在线免费观看av| 亚洲无人区码一码二码三码| 国产三级精品三级在线专区1| 亚洲精品午夜久久久av| 高清一区高清二区高清三区| 成人在线一区二区三区观看| 日韩视频 一区 二区| 日韩精品在线观看电影| 亚洲夫妻性生活免费视频| 国产不卡的视频在线观看| 99久久中文字幕伊人| 国产成人综合亚洲乱淫.| 欧美日韩一区二区三区大片| 亚洲国产精品综合久久久| 激情四射五月天亚洲婷婷| 中文字幕韩国三级电影| 久久好大好爽要死了欧美| 91亚洲自偷观看高清| 亚洲精品国产av成人| 中文字幕日韩激情欧美一区| 成人综合影视中文字幕| 日韩精品国产专区一区| 91午夜福利视频在线观看| 久久一区二区视频在线观看| 国产高清白丝免费在线观看| 91国语对白在线观看| 中文字幕人妻久久精品一区| 日韩三级视频一区二区| 久久婷婷欧美激情综合|