二叉查找樹 C++實現（含完整代碼）

由 我臉上有bug 發佈 2020-02-04T07:35:05+00:00

BSTNode *_lchild; //左孩 cout<<"節點"<<tree->_key<<"無右孩子"<<endl;

一般二叉樹的查找是通過遍歷整棵二叉樹實現，效率較低。二叉查找樹是一種特殊的二叉樹，可以提高查找的效率。二叉查找樹又稱為二叉排序樹或二叉搜索樹。

二叉查找樹的定義

二叉排序樹（Binary Search Tree）又稱二叉排序樹（Binary Sort Tree）,或者是一顆空二叉樹，或者是具有一下特性的二叉樹：

  1. 　　若它的左子樹不為空，則左子樹上的所有結點的值均小於根節點的值。
  2. 　　若它的右子樹不為空，則右子樹上的所有結點的值均小於根節點的值。
  3. 它的左右子樹又分別是二叉排序樹。

　　由定義可知，二叉查找樹中結點的值不允許重複。圖a是一棵二叉查找樹。當加入結點90後如圖b，圖b的二叉樹不是二叉查找樹，因其不滿足二叉排序樹的特性1.

　　 圖a 圖b

二叉樹的C++實現

  1. 二叉查找樹的結點結構
template<typename T>
//樹結點結構
class BSTNode{
public:
    T _key; //關鍵在字（鍵值）
    BSTNode *_lchild; //左孩
    BSTNode *_rchild; //右孩
    BSTNode *_parent; // 雙親
    
    //構造函數
    BSTNode(T key ,BSTNode *lchild,BSTNode *rchild,BSTNode *parent):
    _key(key),_lchild(lchild),_rchild(rchild),_parent(parent){};
};

 交流群：875300321

結點結構BSTNode中含有三個指針域，分別是：

  1. _lchild，指向結點的左孩子。
  2. _rchild，指向結點的右孩子。
  3. _parent，指向結點的雙親。

包含一個數據域 _key，為結點的關鍵字值。

使用構造函數初始化表列對以上四個數據進行初始化。

2. 二叉查找樹的操作

 template<typename T>
class BSTree{
private:
    BSTNode<T> *_Root ;  //根結點

public:
    BSTree():_Root(NULL){};
    ~BSTree(){};

    
    void insert (T key);//二叉樹的插入

    BSTNode<T>* search (T key)  ;//二叉樹的查找
    
    void preOrder()  ;  //先序輸出
    void inOrder() ;   //中序輸出
    void postOrder() ; //後序輸出

    BSTNode<T>* minimumNode();//查找最小的節點
    BSTNode<T>* maximumNode ();//查找最大的節點
    
    T minimumKey();//查找最小的鍵值
    T maximumKey();//查找最小的鍵值

    void print();//列印二叉樹
    void remove(T key);

    BSTNode<T>* predecessor(BSTNode<T>* x);//查找某個結點的前驅
    BSTNode<T>* sucessor(BSTNode<T>* x); //查找某個結點的後繼

    void destory ();

    //內部使用函數，供外部接口調用
private:
    void insert(BSTNode<T>* &tree,BSTNode<T>* z);
    BSTNode<T>* search(BSTNode<T>* &tree,T key) const;
    void preOrder(BSTNode<T>*&tree) const;
    void inOrder(BSTNode<T>*&tree) const;
    void postOrder(BSTNode<T>*&tree) const;
    BSTNode<T>* minimumNode(BSTNode<T> *&tree);
    BSTNode<T>* maximumNode (BSTNode<T> *&tree);
    void print(BSTNode<T>*& tree);
    BSTNode<T>* remove(BSTNode<T>* &tree, BSTNode<T> *z);
    void destory(BSTNode<T>*& tree);
};








 交流群：875300321

BSTree類包含了一個BSTNode指針數據成員，代表二叉查找樹的根結點。類種封裝了二叉查找樹常用的操作接口，包括：

  1. 插入操作：也是建立二叉查找樹的方法。
  2. 遍歷算法：包括前序、中序、後序（遞歸實現）。
  3. 查找操作：包括查找某個結點、查找最小結點、查找最大結點、查找最小值、查找最大值。
  4. 刪除操作。
  5. 銷毀操作。
  6. 列印操作：列印說明二叉樹的結構。

BSTree類大部分的函數都有兩個重載版本，一個僅供類內部使用（privata聲明），另一個則為類用戶使用的公用接口（public聲明）。

2.1二叉查找樹的遍歷

　　2.1.1遍歷二叉樹

　　遍歷二叉樹是指從根結點出發，按照某種次序訪問二叉樹所有結點，使得每個結點被且僅被訪問一次，這裡的訪問可以是輸出、比較、更新、查看結點信息等各種操作。遍歷是二叉樹的一類重要操作，也是二叉樹的其他一些操作和各種應用算法的基本框架。用V表示根節點，用L表示左孩子，用R表示右孩子，且規定先L後R的訪問順序，則有VLR（前序）、LVR（中序）、LRV（後續）三種遍歷算法。對於圖a中的二叉樹，其遍歷結果為：

　　

　　前序遍歷：88 47 19 55 50 98

　　中序遍歷：19 47 50 55 88 98

　　後序遍歷：19 50 55 47 98 88

下面來看BSTtree提供的三種遍歷接口：

　　前序遍歷：




        1. 訪問根節點。
        2. 遍歷訪問左子樹。
        3. 遍歷訪問右子樹。
/*
*
*前序遍歷算法
*BSTree類內部調用函數
*
*/
template<typename T>
void BSTree<T>::preOrder(BSTNode<T>*&tree) const
{
    if(tree)
    {
        cout<<tree->_key<<" ";
        preOrder(tree->_lchild);
        preOrder(tree->_rchild);
    }
}

/*
*接口
*
*/template<typename T>
void BSTree<T>::postOrder()
{
    postOrder(_Root);
}





 交流群：875300321

中序遍歷：

  1. 遍歷訪問左子樹
  2. 訪問根節點。
  3. 遍歷訪問右子樹。


/*
*
*中序遍歷算法
*類內部調用函數
*
*/
template <typename T>
void BSTree<T>::inOrder(BSTNode<T>*&tree) const
{
    if(tree)
    {
        inOrder(tree->_lchild);
        cout<<tree->_key<<" ";
        inOrder(tree->_rchild);
    }
}

/*
*
*接口
*
*/
template<typename T>
void BSTree<T>::inOrder()
{
    inOrder(_Root);
}

後序遍歷：

  1. 遍歷訪問左子樹。
  2. 遍歷訪問右子樹。
  3. 訪問根節點。
/*
*
*後序遍歷算法
*類內部調用函數
*
*/
template <typename T>
void BSTree<T>::postOrder(BSTNode<T>*&tree) const
{
    if(tree)
    {
        postOrder(tree->_lchild);
        postOrder(tree->_rchild);
        cout<<tree->_key<<" ";
    }
}

/*
*
*接口
*
*/
template<typename T>
void BSTree<T>::postOrder()
{
    postOrder(_Root);
}





 交流群：875300321

2.2二叉查找樹的插入

　　構建查找二叉樹通過二叉查找樹的插入操作來進行。插入時嚴格按照查找二叉樹的定義來進行，其插入算法的基本過程可以分解為：


    1. 根結點為空則進行插入。
    2. 值比根結點小，在根結點的左子樹進行插入。
    3. 值比根結點大，在根節點的右子樹進行插入。

　　本文採用非遞歸算法實現插入操作。

/*
*插入操作
*非遞歸實現
*內部使用函數
*/
template<typename T>
void BSTree<T> ::insert(BSTNode<T>* &tree,BSTNode<T>* z)
{
    BSTNode<T>* parent = NULL;
    BSTNode<T>* temp = tree;

    //尋找插入點
    while(temp!=NULL)
    {
        parent= temp;
        if(z->_key>temp->_key)
            temp= temp->_rchild;
        else 
            temp=temp->_lchild;
    }
    z->_parent = parent;
    if(parent==NULL) //如果樹本來就是空樹，則直接把z節點插入根節點
        tree = z;
    else if(z->_key>parent->_key) //如果z的值大於其雙親，則z為其雙親的右孩
        parent->_rchild = z;
    else                          
        parent->_lchild = z;
}
/*
*
*接口
*/
template <typename T>
void BSTree<T>::insert(T key)
{
    //創建一個新的節點，使用構造函數初始化
    BSTNode<T>* z= new BSTNode<T>(key,NULL,NULL,NULL);
    if(!z) //如果創建失敗則返回
        return ;
    //調用內部函數進行插入
    insert(_Root,z);
}




 交流群：875300321

2.3 二叉查找樹的查找

　　 　　2.3.1 查找某個值的結點

　　　　　這裡提供遞歸與非遞歸算法實現查找操作。

/*
*查找操作
*非遞歸實現
*內部使用函數
*/
template <typename T>
BSTNode<T>*  BSTree<T>::search(BSTNode<T>* &tree,T key) const
{
    BSTNode<T>* temp = tree;
    while(temp != NULL)
    {
        if(temp->_key == key)
            return temp;
        else if(temp->_key>key)
            temp = temp->_lchild;
        else
            temp = temp->_rchild;
    }
    return NULL;
}
////查找算法的遞歸實現
//template<typename T>
//BSTNode<T>* BSTree<T>::search( BSTNode<T>* &tree,T key) const
//{
//    if(!tree)
//    {
//        if(tree->_key==key)
//            return tree;
//        if(tree->_key>key)
//            return search(tree->_lchild,key);
//        if(tree->_key<z->_key)
//            return search(tree->_rchild,key);
//    }
//    return NULL;
//}

/*
*接口
*/
template <typename T>
BSTNode<T> * BSTree<T>::search(T key) 
{
    return search(_Root,key);
}






 交流群：875300321

　　2.3.2查找二叉查找樹值最小的結點

/*
*
*查找最小的結點
*內部調用函數
*
*/
template <typename T>
BSTNode<T>* BSTree<T>::minimumNode(BSTNode<T>*&tree)
{
    BSTNode<T>* temp = tree;
    while(temp->_lchild)
    {
        temp= temp->_lchild;
    }
    return temp;
}

/*
*接口
*/
template<typename T>
BSTNode<T>* BSTree<T>::minimumNode()
{
    return minimumNode(_Root);
}

　　2.3.3查找二叉查找樹中值最大的結點

/*
*
*查找鍵值最大的節點
*內部調用函數
*非遞歸實現
*/
template<typename T>
BSTNode<T>* BSTree<T>::maximumNode(BSTNode<T>* &tree)
{
    BSTNode<T>* temp=tree;
    while(temp->_rchild)
    {
        temp= temp->_rchild;
    }

    return temp;
}

/*
*接口
*/
template<typename T>
BSTNode<T>* BSTree<T>::maximumNode()
{
    return maximumNode(_Root);
}

　　2.3.4查找二叉查找樹中最小的值

/*
*
*查找最小的鍵值
*外部接口函數
*調用內部函數minimumNode實現
*/
template<typename T>
T BSTree<T>::minimumKey()
{
    BSTNode<T> *temp = minimumNode(_Root);
    return temp->_key;
}

　　2.4.5查找二叉查找樹中最大的值

/*
*
*查找最大的鍵值
*外部接口函數
*調用內部函數maximumKey
*/
template<typename T>
T BSTree<T>::maximumKey()
{
    BSTNode<T> *temp = maximumNode(_Root);
    return temp->_key;
}

　　2.3列印查找二叉樹

　　該操作把二叉樹中每個結點的父結點、左右孩子結點的信息描述出來。

/*
*
*列印函數
*列印出平衡二叉樹
*BStree內部函數
*/
template<typename T>
void BSTree<T>::print(BSTNode<T>*& tree)
{
    if(tree) //如果tree不為空
    {
        if(tree->_lchild) //結點有左孩子
        {
            cout<<"節點"<<tree->_key<<"有左孩子為"<<tree->_lchild->_key<<endl;
        }
        else 
            cout<<"節點"<<tree->_key<<"無左孩子"<<endl;
        if(tree->_rchild)
        {
            cout<<"節點"<<tree->_key<<"有右孩子為"<<tree->_rchild->_key<<endl;
        }
        else 
            cout<<"節點"<<tree->_key<<"無右孩子"<<endl;
        print(tree->_lchild);
        print(tree->_rchild);
    }
}

/*
*接口
*/
template<typename T>
void BSTree<T>::print()
{
    print(_Root);
}

運行結果：


關鍵字：
#code #程式開發 #我臉上有bug

MAGICOM美肌之鏡_高水感抗靜電_髮香噴霧

售價 NT$ 1,180-1,680

【amz嚴選】創意手工編織鑰匙圈

售價 NT$ 90

【amz嚴選】可愛造型聖誕禮品袋

售價 NT$ 180-190

【amz獨家組合】Relove_私密潔淨凝露_三款全系列

售價 NT$ 1,200-1,840

Nature Tree_深層美白_精華液

售價 NT$ 990

【E‧Heart】機能型壓力褲裙 S-M/L-LL/3L

售價 NT$ 799-849

Relove_男性專用私密潔淨凝露

售價 NT$ 1,280

【amz嚴選】輕奢磁吸式_保鮮膜切割器

售價 NT$ 319