ID #5729

二叉查找树的解析与实现

二叉查找树是二叉树的一个特化,它具有的特殊性质是:对于树中的任何一个结点,它的左子树的所有结点的关键字都小于此结点的关键字,而右子树的所有结点的关键字都大于此结点的关键字.

二叉查找树的这种特殊性质使得它在查找元素的时候特别的方便,每一次查找都可以去掉一半的元素,因此查找的时间是O(logN).

二叉查找树的插入和查找算法也是很简单的,就是与当前结点的关键字作比较决定在右边还是左边继续操作.

二叉查找树最复杂的算法就是删除结点的算法了,根据所要删除的结点有两个子结点还是只有一个或者没有子结点会有不同的处理.有两个子结点的情况一般的处理是找到右子树中值最小的一个结点,将它的值替代当前的结点值,然后再把这个值最小的结点删除,也就是说有两个子结点的情况是用最小的一个大于当前结点关键字的结点替代了当前的结点(很拗口,但愿我说清楚了:)在只有一个或者没有子结点的情况就比较的简单了,如果还有子结点就把子结点的位置往上挪,然后把当前结点删除.

实现如下:

1)BSTree.h

/**//********************************************************************
    created:    2006/07/28
    filename:     BSTree.h
    author:        李创
                http://www.cppblog.com/converse/

    purpose:    二叉查找树的实现代码
*********************************************************************/

#ifndef BINARY_SEARCH_TREE_H
#define BINARY_SEARCH_TREE_H

#include <stdio.h>

template<typename T>
struct BTreeNode
{
    T    Data;
    BTreeNode* pLeft;
    BTreeNode* pRight;
    BTreeNode* pParent;

    BTreeNode(    T data = T(), BTreeNode<T>* Parent = NULL,
                BTreeNode<T>* Left = NULL, BTreeNode<T>* Right = NULL)
                : Data(data), pLeft(Left), pRight(Right), pParent(Parent)
    {
    }
};

template<typename T>
class BSTree
{
protected:
    BTreeNode<T>*    m_pRootNode;

public:
    BSTree(BTreeNode<T>* pRoot = NULL)
        : m_pRootNode(pRoot)
    {
    }
    ~BSTree();

    void            Display();
    BTreeNode<T>*    Insert(const T& data);
    BTreeNode<T>*    Find(const T& data);
    BTreeNode<T>*    FindMin();
    BTreeNode<T>*    FindMax();
    BTreeNode<T>*    Delete(const T& data);

private:
    void            Display(BTreeNode<T>* p);
    BTreeNode<T>*    Insert(const T& data, BTreeNode<T>* p);
    BTreeNode<T>*    Find(const T& data, BTreeNode<T>* p);
    BTreeNode<T>*    FindMin(BTreeNode<T>* p);
    BTreeNode<T>*    FindMax(BTreeNode<T>* p);
    BTreeNode<T>*    Delete(const T& data, BTreeNode<T>* p);

    void            DestructImpl(BTreeNode<T>* p);
};

#endif

2)BSTree.cpp

/**//********************************************************************
    created:    2006/07/28
    filename:     BSTree.cpp
    author:        川幹
                http://www.cppblog.com/converse/

    purpose:    屈我臥孀峯議糞・旗鷹
*********************************************************************/

#include <iostream>
#include "BSTree.h"

template<typename T>
BSTree<T>::~BSTree()
{
    DestructImpl(m_pRootNode);
}

template<typename T>
void BSTree<T>::DestructImpl(BTreeNode<T>* p)
{
    if (NULL == p)
        return;

    DestructImpl(p->pLeft);
    DestructImpl(p->pRight);
    p->pLeft = NULL;
    p->pRight = NULL;
    p->pParent = NULL;
    delete p;
    p = NULL;
}

template<typename T>
void BSTree<T>::Display()
{
    Display(m_pRootNode);
}

// 嶄會嬉咫竃峯嶄議圷殆,宸劔哘乎頁貫弌欺寄議乏會
template<typename T>
void BSTree<T>::Display(BTreeNode<T>* p)
{
    if (NULL == p)
        return;

    Display(p->pLeft);
    std::cout << "Node = " << p->Data << std::endl;
    Display(p->pRight);
}

template<typename T>
BTreeNode<T>* BSTree<T>::Insert(const T& data)
{
    return Insert(data, m_pRootNode);
}

template<typename T>
BTreeNode<T>* BSTree<T>::Insert(const T& data, BTreeNode<T>* p)
{
    if (NULL == p)
    {
        p = new BTreeNode<T>(data);

        if (NULL == p)
        {
            return NULL;
        }
        else if (NULL == m_pRootNode)
        {
            m_pRootNode = p;
        }
    }
    else if (data > p->Data)
    {
        p->pRight = Insert(data, p->pRight);
        if (NULL != p->pRight)
        {
            p->pRight->pParent = p;
        }
    }
    else
    {
        p->pLeft = Insert(data, p->pLeft);
        if (NULL != p->pLeft)
        {
            p->pLeft->pParent = p;
        }
    }

    return p;
}

template<typename T>
BTreeNode<T>* BSTree<T>::Find(const T& data)
{
    return Find(data, m_pRootNode);
}

template<typename T>
BTreeNode<T>* BSTree<T>::Find(const T& data, BTreeNode<T>* p)
{
    if (NULL == p)
    {
        return NULL;
    }
    else
    {
        if (data == p->Data)
        {
            return p;
        }
        else if (data > p->Data)
        {
            return Find(data, p->pRight);
        }
        else
        {
            return Find(data, p->pLeft);
        }
    }
}

template<typename T>
BTreeNode<T>* BSTree<T>::FindMin()
{
    return FindMin(m_pRootNode);
}

template<typename T>
BTreeNode<T>* BSTree<T>::FindMin(BTreeNode<T>* p)
{
    if (NULL == p)
    {
        return NULL;
    }

    if (NULL != p->pLeft)
    {
        return FindMin(p->pLeft);
    }
    else
    {
        return p;
    }
}

template<typename T>
BTreeNode<T>* BSTree<T>::FindMax()
{
    return FindMax(m_pRootNode);
}

template<typename T>
BTreeNode<T>* BSTree<T>::FindMax(BTreeNode<T>* p)
{
    if (NULL == p)
    {
        return NULL;
    }

    if (NULL != p->pRight)
    {
        return FindMax(p->pRight);
    }
    else
    {
        return p;
    }
}

template<typename T>
BTreeNode<T>* BSTree<T>::Delete(const T& data)
{
    return Delete(data, m_pRootNode);
}

template<typename T>
BTreeNode<T>* BSTree<T>::Delete(const T& data, BTreeNode<T>* p)
{
    if (NULL == p)
    {
        return NULL;
    }
    else if (data < p->Data)
    {
        p->pLeft = Delete(data, p->pLeft);
    }
    else if (data > p->Data)
    {
        p->pRight = Delete(data, p->pRight);
    }
    else if (NULL != p->pLeft && NULL != p->pRight)
    {
        // 孀欺潤泣拝嗤曾倖徨潤泣
        BTreeNode<T>* pNode;
        // 孀欺嘔徨峯嶄恷弌議潤泣,委万議峙紋算輝念潤泣峙,隼朔評茅孀欺議椎倖潤泣
        pNode = FindMin(p->pRight);
        p->Data = pNode->Data;
        p->pRight = Delete(p->Data, p->pRight);
    }
    else
    {
        // 孀欺潤泣徽頁峪嗤匯倖賜短嗤徨潤泣
        // 泌惚嗤徨潤泣祥喘徨潤泣旗紋輝念潤泣,隼朔評茅輝念潤泣
        BTreeNode<T>* pNode = p;
        if (NULL == p->pLeft)
        {
            p = p->pRight;
        }
        else if (NULL == p->pRight)
        {
            p = p->pLeft;
        }
        delete pNode;
        pNode = NULL;
    }

    return p;
}


3)Main.cpp
#include "BSTree.h"
#include <stdlib.h>
#include <time.h>

// 幹秀匯倖方怏,圷殆峙昧字譜崔
void CreateNewArray(int array[], int length)
{
    for (int i = 0; i < length; i++)
    {
        array[i] = rand() % 256;
    }
}

int main()
{
    int array[10];
    srand(time(NULL));

    CreateNewArray(array, 10);
    BSTree<int> tree;
    for (int i = 0; i < 10; ++i)
    {
        tree.Insert(array[i]);
    }
    tree.Display();
    if (NULL != tree.Find(array[7]))
    {
        std::cout << "Find!\n";
    }

    BTreeNode<int>* pNode;

    if (NULL != (pNode = tree.FindMin()))
    {
        std::cout << "Min = " << pNode->Data << std::endl;
    }

    if (NULL != (pNode = tree.FindMax()))
    {
        std::cout << "Max = " << pNode->Data << std::endl;
    }

    tree.Delete(array[7]);
    std::cout << "\nafter delete " << array[7] << std::endl;
    tree.Display();

    system("pause");
    return 0;
}

需要说明一点:上面做测试用的Main.cpp如果单独写在一个文件中就会在链接的时候报错,报的错误是:

BSTree error LNK2019: unresolved external symbol "public: struct BTreeNode<int> * __thiscall BSTree<int>::Insert(int const &)" ([email protected][email protected]@@[email protected]@@[email protected]) referenced in function _main
BSTree error LNK2019: unresolved external symbol "public: __thiscall BSTree<int>::~BSTree<int>(void)" ([email protected]@@[email protected]) referenced in function _main
BSTree error LNK2019: unresolved external symbol "public: struct BTreeNode<int> * __thiscall BSTree<int>::Delete(int const &)" ([email protected][email protected]@@[email protected]@@[email protected]) referenced in function _main
BSTree error LNK2019: unresolved external symbol "public: struct BTreeNode<int> * __thiscall BSTree<int>::FindMax(void)" ([email protected][email protected]@@[email protected]@@XZ) referenced in function _main
BSTree error LNK2019: unresolved external symbol "public: struct BTreeNode<int> * __thiscall BSTree<int>::FindMin(void)" ([email protected][email protected]@@[email protected]@@XZ) referenced in function _main
BSTree error LNK2019: unresolved external symbol "public: struct BTreeNode<int> * __thiscall BSTree<int>::Find(int const &)" ([email protected][email protected]@@[email protected]@@[email protected]) referenced in function _main
BSTree error LNK2019: unresolved external symbol "public: void __thiscall BSTree<int>::Display(void)" ([email protected][email protected]@@QAEXXZ) referenced in function _main

所以没有办法,我只能将main.cpp中的内容copy到BSTree.cpp中才能链接过去.

如果哪位朋友知道如何解决上面因为采用了模板类出现的链接错误,我不胜感激,谢谢!


2011-07-01 18:29
阅读:
I'm VC , Just U know Y
本站部分文章来源于互联网,版权归原作者所有。

延伸阅读:

比较数据排序前后的查找次数

根据前序和中序序列生成二叉树

关于后序递归建二叉树的方法

二叉树的创建、前序遍历、中序遍历、后序遍历

二叉树遍历算法集合