程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> 數據結構與算法——二叉查找樹類的C++實現

數據結構與算法——二叉查找樹類的C++實現

編輯：關於C++

二叉樹的平均深度為O(logN)；二叉查找樹在二叉樹的基礎上，增加的性質為：對於樹中每一個結點X，它的左子樹中所有項的值小於X中的項，而它的右子樹中所有項的值大於X中的項。

該二叉查找樹結點的數據結構:

struct BinaryNode{
    Comparable element;//結點的值
    BinaryNode * left;//結點的左孩子
    BinaryNode * right;//結點的右孩子
    int num;//相同值的結點出現的次數,如果不考慮重復元素的話，該成員可以省去
    BinaryNode(const Comparable & e, BinaryNode* lt, BinaryNode* rt, int n):element(e), left(lt), right(rt), num(n){}
};

該結點數據結構其實是一個結點類。

該二叉查找樹的主要成員函數：

BinarySearchTree(){root = NULL;}//構造函數
BinarySearchTree(vector & v);//構造函數
BinarySearchTree(const BinarySearchTree & rhs);//復制構造函數
const BinarySearchTree & operator=(const BinarySearchTree & rhs);//賦值運算符重載
~BinarySearchTree();//析構函數

void preOrderPrintTree() const;//從小到大打印該二叉查找樹
void inOrderPrintTree() const;//從大到小打印該二叉查找樹

Comparable findMin() const;//查找最小值
Comparable findMax() const;//查找最大值
bool contains(const Comparable & x) const;//判斷該二叉查找樹是否包含值為x的結點
bool isEmpty() const;//判斷該二叉查找樹是否為空 
void makeEmpty();//清空該二叉查找樹

void insert(const Comparable & x);//插入結點
void remove(const Comparable & x);//移除結點值為x的結點

主要成員函數介紹：

void remove(const Comparable & x);//移除結點值為x的結點

/****************************************************************
*   函數名稱：remove(const Comparable & x) 
*   功能描述: 移除結點
*   參數列表: x -- 要移除的結點的值 
*   返回結果：void
*****************************************************************/
template
void BinarySearchTree::remove(const Comparable & x)
{
    remove(x, root);    
}

template
void BinarySearchTree::remove(const Comparable & x, BinaryNode * &t) const
{
    if(t == NULL)
        return;

    if(x < t->element)
        remove(x, t->left);
    else if(x > t->element)
        remove(x, t->right);
    else if((t->left != NULL) && (t->right != NULL)){//該結點有兩個兒子的時候，將該結點右子樹的最小結點覆蓋該結點的值，然後再刪除那個最小結點
        t->element = findMin(t->right);
        remove(t->element, t->right);
    }
    else {//該結點只有一個兒子的時候，將兒子放在當前結點的位置。用另一個指針保存當前結點，然後刪除該結點；此時也包括該結點為葉子結點的情況
        BinaryNode * oldCurrentNode = t;
        t = (t->left == NULL) ? t->right : t->left;
        delete oldCurrentNode;
    }
}

下面的main函數是對remove成員函數的測試，用的就是上面兩個圖：

int main()
{
    BinarySearchTree tree;
    tree.insert(6);
    tree.insert(2);
    tree.insert(1);
    tree.insert(4);
    tree.insert(3);
    tree.insert(8);

    tree.preOrderPrintTree();
    tree.remove(4);
    tree.preOrderPrintTree();

    BinarySearchTree tree2;
    tree2.insert(6);
    tree2.insert(2);
    tree2.insert(1);
    tree2.insert(5);
    tree2.insert(3);
    tree2.insert(4);
    tree2.insert(8);
    tree2.preOrderPrintTree();
    tree2.remove(2);
    tree2.preOrderPrintTree();


    return 0;
}

下面是該二叉查找樹類的源代碼：

/*************************************************************************
	> File Name: BinarySearchTree.cpp
	> Author: 
	> Mail: 
	> Created Time: 2016年04月06日 星期三 17時19分47秒
 ************************************************************************/

#include 
#include 
#include 
#include 
using namespace std;

template
class BinarySearchTree{
    public:
        BinarySearchTree(){root = NULL;}
        BinarySearchTree(vector & v);
        BinarySearchTree(const BinarySearchTree & rhs);
        ~BinarySearchTree();
        
        const BinarySearchTree & operator=(const BinarySearchTree & rhs);//賦值運算符重載

        void preOrderPrintTree() const;//從小到大打印該二叉查找樹
        void inOrderPrintTree() const;//從大到小打印該二叉查找樹

        Comparable findMin() const;//查找最小值
        Comparable findMax() const;//查找最大值

        bool contains(const Comparable & x) const;//判斷該二叉查找樹是否包含值為x的結點

        void makeEmpty();//清空該二叉查找樹
        bool isEmpty() const;//判斷該二叉查找樹是否為空 

        void insert(const Comparable & x);//插入結點
        void remove(const Comparable & x);//移除結點值為x的結點


    private:
        //樹結點的數據結構
        struct BinaryNode{
            Comparable element;
            BinaryNode * left;
            BinaryNode * right;
            int num;//相同值的結點出現的次數
            BinaryNode(const Comparable & e, BinaryNode* lt, BinaryNode* rt, int n):element(e), left(lt), right(rt), num(n){}
        };

        BinaryNode* root;

        void insert(const Comparable & x, BinaryNode * &t) const;
        void remove(const Comparable & x, BinaryNode * &t) const;

        void preOrder(BinaryNode * t) const;//前序遍歷
        void inOrder(BinaryNode * t) const;//中序遍歷
        void deleteNode(BinaryNode * t);//釋放結點t
        Comparable &findMin(BinaryNode * node) const;
        Comparable &findMax(BinaryNode * node) const;
        bool contains(const Comparable & x, BinaryNode * t) const;//判斷該二叉查找樹是否包含值為x的結點
        BinaryNode *clone(BinaryNode * t) const{
            if(t == NULL)
                return NULL;

            return new BinaryNode(t->element, clone(t->left), clone(t->right), t->num);
        }

};

/****************************************************************
*   函數名稱：BinarySearchTree(const BinarySearchTree & rhs)
*   功能描述: 該二叉查找樹的復制構造函數
*   參數列表: rhs 要復制的二叉查找樹 
*   返回結果：無
*****************************************************************/
template
BinarySearchTree::BinarySearchTree(const BinarySearchTree & rhs)
{
    root = clone(rhs.root);
}

/****************************************************************
*   函數名稱：BinarySearchTree(const BinarySearchTree & rhs)
*   功能描述: 該二叉查找樹的復制構造函數
*   參數列表: rhs 要復制的二叉查找樹 
*   返回結果：無
*****************************************************************/
template
const BinarySearchTree & BinarySearchTree::operator=(const BinarySearchTree & rhs)//賦值運算符重載
{
    if(this != &rhs){
        makeEmpty();
        root = clone(rhs.root);
    }

    return *this;
}

/****************************************************************
*   函數名稱：contains(const Comparable & x)const
*   功能描述: 判斷該二叉查找樹是否含有值為x的結點 
*   參數列表: 無
*   返回結果：如果有值為x的結點，則返回true;
*             如果沒有值為x的結點，則返回false;
*****************************************************************/
template
bool BinarySearchTree::contains(const Comparable & x) const
{
    if(isEmpty())
        return false;
    else
        return contains(x, root); 
}

template
bool BinarySearchTree::contains(const Comparable & x, BinaryNode * t) const
{
    if(t == NULL)
        return false;

    if(x == t->element)
        return true;
    else if(x > t->element)
        return contains(x, t->right);
    else if(x < t->element)
        return contains(x, t->left);
}

/****************************************************************
*   函數名稱：findMax()const
*   功能描述: 查找樹的最大值 
*   參數列表: 無
*   返回結果：結點值的引用
*****************************************************************/
template
Comparable BinarySearchTree::findMax() const
{
    if(!isEmpty())
        return findMax(root); 
}

/****************************************************************
*   函數名稱：findMax(BinaryNode *node)const
*   功能描述: 查找樹的最大值 
*   參數列表: 無
*   返回結果：結點值的引用
*****************************************************************/
template
Comparable & BinarySearchTree::findMax(BinaryNode * node) const
{
    if(node->right== NULL)
        return node->element;
    else 
        return findMax(node->right);
}

/****************************************************************
*   函數名稱：findMin()const
*   功能描述: 查找樹的最小值 
*   參數列表: 無
*   返回結果：結點值的引用
*****************************************************************/
template
Comparable BinarySearchTree::findMin() const
{
    if(!isEmpty())
        return findMin(root); 
}

/****************************************************************
*   函數名稱：findMin(BinaryNode *node)const
*   功能描述: 查找樹的最小值 
*   參數列表: 無
*   返回結果：結點值的引用
*****************************************************************/
template
Comparable & BinarySearchTree::findMin(BinaryNode * node) const
{
    if(node->left == NULL)
        return node->element;
    else 
        return findMin(node->left);
}

/****************************************************************
*   函數名稱：BinarySearchTree(vector &)
*   功能描述: 構造函數
*   參數列表: v 用於構造二叉查找樹的數據序列
*   返回結果：無
*****************************************************************/
template
BinarySearchTree::BinarySearchTree(vector & v)
{
    root = NULL;//必須初始化,否則析構的時候會出錯

    for(vector::iterator it = v.begin(); it != v.end(); ++it)
        insert(*it); 
}

/****************************************************************
*   函數名稱：~BinarySearchTree()
*   功能描述: 析構函數 
*   參數列表: 無 
*   返回結果：無
*****************************************************************/
template
BinarySearchTree::~BinarySearchTree()
{
   //deleteNode(root); 
    makeEmpty();//兩種方式都可以
}

/****************************************************************
*   函數名稱：deleteNode(BinaryNode *t)
*   功能描述: 釋放結點 
*   參數列表: 要釋放結點的指針 
*   返回結果：void
*****************************************************************/
template
void BinarySearchTree::deleteNode(BinaryNode * t)
{
    //後序遍歷的方式釋放所有結點 
    if(t != NULL){
        deleteNode(t->left);
        deleteNode(t->right);
        //cout << "t->element = " << t->element << endl;
        delete t;
    }
}


/****************************************************************
*   函數名稱：isEmpty() const
*   功能描述: 判斷該二叉查找樹是否為空 
*   參數列表: 無 
*   返回結果：如果該樹為空，則返回true；
*             如果該樹為不為空，則返回false
*****************************************************************/
template
bool BinarySearchTree::isEmpty()const
{
    return (root == NULL) ? true : false;
}


/****************************************************************
*   函數名稱：makeEmpty() 
*   功能描述: 將該二叉查找樹清空 
*   參數列表: 無 
*   返回結果：無
*****************************************************************/
template
void BinarySearchTree::makeEmpty()
{
    deleteNode(root);//移除所有結點
    root = NULL;
}


/****************************************************************
*   函數名稱：preOrderPrintTree() const
*   功能描述: 按從小到大的順序輸出該二叉查找樹
*   參數列表: 無 
*   返回結果：void
*****************************************************************/
template
void BinarySearchTree::preOrderPrintTree() const
{
    cout << "按從小到大的順序輸出該二叉查找樹: ";
    preOrder(root); 
    cout << endl;
}

/****************************************************************
*   函數名稱：preOrder(BinaryNode * t) const
*   功能描述: 按從小到大的順序輸出該二叉查找樹，前序遍歷
*   參數列表: 當前結點的指針 
*   返回結果：void
*****************************************************************/
template
void BinarySearchTree::preOrder(BinaryNode * t) const
{
    if(t != NULL){
        preOrder(t->left);//打印左子樹

        for(int i = 0; i < t->num; ++i)
            cout << t->element << " ";//打印父結點，可能有多個值

        preOrder(t->right);//打印右子樹
    }
}

/****************************************************************
*   函數名稱：inOrderPrintTree() const
*   功能描述: 按從大到小的順序打印該二叉樹
*   參數列表: 無 
*   返回結果：void
*****************************************************************/
template
void BinarySearchTree::inOrderPrintTree() const
{
    cout << "按從大到小的順序輸出該二叉查找樹: ";
    inOrder(root); 
    cout << endl;
}

/****************************************************************
*   函數名稱：inOrder(BinaryNode * t) const
*   功能描述: 按從小到大的順序輸出該二叉查找樹，前序遍歷
*   參數列表: 當前結點的指針 
*   返回結果：void
*****************************************************************/
template
void BinarySearchTree::inOrder(BinaryNode * t) const
{
    if(t != NULL){
        inOrder(t->right);//打印右子樹

        for(int i = 0; i < t->num; ++i)
            cout << t->element << " ";//打印父結點，可能有多個值

        inOrder(t->left);//打印左子樹
    }
}


/****************************************************************
*   函數名稱：remove(const Comparable & x) 
*   功能描述: 移除結點
*   參數列表: x -- 要移除的結點的值 
*   返回結果：void
*****************************************************************/
template
void BinarySearchTree::remove(const Comparable & x)
{
    remove(x, root);    
}

template
void BinarySearchTree::remove(const Comparable & x, BinaryNode * &t) const
{
    if(t == NULL)
        return;

    if(x < t->element)
        remove(x, t->left);
    else if(x > t->element)
        remove(x, t->right);
    else if((t->left != NULL) && (t->right != NULL)){//該結點有兩個兒子的時候，將該結點右子樹的最小結點覆蓋該結點的值，然後再刪除那個最小結點
        t->element = findMin(t->right);
        remove(t->element, t->right);
    }
    else {//該結點只有一個兒子的時候，將兒子放在當前結點的位置。用另一個指針保存當前結點，然後刪除該結點
        BinaryNode * oldCurrentNode = t;
        t = (t->left == NULL) ? t->right : t->left;
        delete oldCurrentNode;
    }
}
/****************************************************************
*   函數名稱：insert(const Comparable & x) 
*   功能描述: 插入值為x的結點 
*   參數列表: x 要插入的值 
*   返回結果：void
*****************************************************************/
template
void BinarySearchTree::insert(const Comparable & x)
{
    insert(x, root);
}

/****************************************************************
*   函數名稱：insert(const Comparable & x, BinaryNode * & t) const
*   功能描述: 在結點t上插入值為x的結點 
*   參數列表: x 要插入的值 
*             t 要插入到結點t上
*   返回結果：void
*****************************************************************/
template
void BinarySearchTree::insert(const Comparable & x, BinaryNode * & t) const
{
    if(t == NULL)
        t = new BinaryNode(x, NULL, NULL, 1);
    else if(x > t->element)
        insert(x, t->right);
    else if(x < t->element)
        insert(x, t->left);
    else if(x == t->element)//如果要插入的值和當前結點的值相同，則將當前結點的個數加1
        t->num++;
}



//測試該二叉查找樹的成員函數 
int main0()
{

//    srand(unsigned (time(0)));

    vector v;

    //隨機生成一個數據序列
    for(int i = 0; i < 10; ++i)
        v.push_back(rand()%10); 

    cout << "隨機產生的數據序列: ";
    for(vector::iterator it = v.begin(); it != v.end(); ++it)
        cout << *it << " ";
    cout << endl;

    //用第一個構造函數生成該二叉查找樹
    BinarySearchTree tree;

    if(tree.isEmpty())
        cout << "該樹此時為空." << endl;
    else
        cout << "該樹此時為不為空." << endl;

    for(vector::iterator it = v.begin(); it != v.end(); ++it)
        tree.insert(*it); 

    if(tree.isEmpty())
        cout << "該樹此時為空." << endl;
    else
        cout << "該樹此時為不為空." << endl;


    cout << "tree1: " << endl;
    tree.preOrderPrintTree();//從小到大輸出該二叉查找樹
    tree.inOrderPrintTree();//從大到小輸出該二叉查找樹

    int min = tree.findMin();
    cout << "min = " << min << endl;
    int max = tree.findMax();
    cout << "max = " << max << endl;

    if(tree.contains(5))
        cout << "contains(5))" << endl;
    else
        cout << "not contains(5)" << endl;

    BinarySearchTree tree3 = tree;
    tree3.preOrderPrintTree();
    tree3.inOrderPrintTree();

    BinarySearchTree tree4;
    tree4 = tree;
    tree4.preOrderPrintTree();
    tree4.inOrderPrintTree();
/*
    tree.makeEmpty();
    if(tree.isEmpty())
        cout << "該樹此時為空." << endl;
    else
        cout << "該樹此時為不為空." << endl;
*/



    //用第二個構造函數生成該二叉查找樹
    cout << "tree2: " << endl;
    BinarySearchTree tree2(v);
    tree2.preOrderPrintTree();//從小到大輸出該二叉查找樹
    tree2.inOrderPrintTree();//從大到小輸出該二叉查找樹

    return 0;
}


//test the functiona of remove
int main()
{
    BinarySearchTree tree;
    tree.insert(6);
    tree.insert(2);
    tree.insert(1);
    tree.insert(4);
    tree.insert(3);
    tree.insert(8);

    tree.preOrderPrintTree();
    tree.remove(4);
    tree.preOrderPrintTree();

    BinarySearchTree tree2;
    tree2.insert(6);
    tree2.insert(2);
    tree2.insert(1);
    tree2.insert(5);
    tree2.insert(3);
    tree2.insert(4);
    tree2.insert(8);
    tree2.preOrderPrintTree();
    tree2.remove(2);
    tree2.preOrderPrintTree();


    return 0;
}