用 C++ 标准模板库（STL）的 vector 实现二叉搜索树（BST）

本文由 Justme0翻译自 Code Project 转载请参见文章末尾处的要求。

介绍

众所周知，要建一棵树，我们需要关注它的内存分配与释放。为了避开这个问题，我打算用C++ STL(vector和deque)来建一棵小型的BST。很明显，这篇文章是出于这个想法的。

背景

BST是应用最广泛的数据结构之一。C是首选语言，不过因为C++尤其是C++11的出现，我更有兴趣用C++来实现。但是这篇文章里没有涉及到C++11，代码可用C++98来编译。

使用代码

要建BST，我们需要BST的数据结构。传统的BST数据结构包含指向左右子树的指针。我将用vector而不用指针，所以我将用vector的下标作为指向左右子树的指针。

struct bst
{
    unsigned int data;
    int leftIdx;
    int rightIdx;
};

接下来，我会写各种建BST和它的孩子结点的函数。第一个函数用来建BST。它将用传入的数据来初始化数据结构，并且把左右下标置为-1（相当于置指针为NULL）。

void MakeNode(vector<struct> &v1, int aData)
{
    struct bst b1 = { aData, -1, -1 };
    v1.push_back(b1);
}

下面这个函数的功能是设置结点的左右孩子。设置时，会把左右孩子的真正下标（译者注：相当于它们的地址）赋到根结点上。

void setleft(vector <struct>&v1, int currIndex, int aData)
{
    unsigned int leftIndex = v1.size();
    v1[currIndex].leftIdx = leftIndex;
    struct bst b1 = { aData, -1, -1 };
    v1.push_back(b1);
}

void setright(vector<struct> &v1, int currIndex, int aData)
{
    unsigned int rightIndex = v1.size();
    v1[currIndex].rightIdx = rightIndex;
    struct bst b1 = { aData, -1, -1 };
    v1.push_back(b1);
}

下面这个函数用于向BST插入数据。对所有结点（译者注：不应是“所有”，平均时间复杂度应是O(logn)）遍历直至找到合适的位置插入元素，其中会调用上面定义的左右函数。

void Insert(vector<struct bst> &v1, int aData)
{
    if(v1.size() == 0)
    {
        cout<<"Note is not made yet. MakeNode first..."<<endl;
        return;
    }
    unsigned int currentIdx = 0;
    while ( currentIdx < v1.size() )
    {
        if(aData <= v1[currentIdx].data)
        {
            if( v1[currentIdx].leftIdx == -1)
            {
                setleft(v1, currentIdx, aData);
                break;
            }
            else
                currentIdx = v1[currentIdx].leftIdx;
        }
        else
        {
            if(v1[currentIdx].rightIdx == -1)
            {
                setright(v1, currentIdx, aData);
                break;
            }
            else
                currentIdx = v1[currentIdx].rightIdx;
        }
    }
}

下面的代码将以前序、中序、后序遍历BST。下标参数是开始点。

void InTrav(vector <struct bst> &v1, unsigned int Idx)
{
    if(v1[Idx].leftIdx != -1)
        InTrav(v1,v1[Idx].leftIdx );
    cout<<v1[Idx].data<<endl;
    if( v1[Idx].rightIdx != -1)
        InTrav(v1, v1[Idx].rightIdx);
}

void PreTrav(vector <struct bst> &v1, unsigned int Idx)
{
    cout<<v1[Idx].data<<endl;
    if(v1[Idx].leftIdx != -1)
        PreTrav(v1,v1[Idx].leftIdx );
    if( v1[Idx].rightIdx != -1)
        PreTrav(v1, v1[Idx].rightIdx);
}
void PostTrav(vector <struct bst> &v1, unsigned int Idx)
{
    if(v1[Idx].leftIdx != -1)
        PostTrav(v1,v1[Idx].leftIdx );
    if( v1[Idx].rightIdx != -1)
        PostTrav(v1, v1[Idx].rightIdx);
    cout<<v1[Idx].data<<endl;
}

主程序比较简单，如下

int main()
{
    vector <struct bst> v1;
    MakeNode(v1, 30);
    Insert(v1, 20);
    Insert(v1, 6);
    Insert(v1, 40);
    Insert(v1, 35);
    Insert(v1, 16);
    Insert(v1, 7);

    InTrav(v1, 0);
    PreTrav(v1,0);
    PostTrav(v1,0);
    return 0;
}

兴趣点

1、同样的代码也可用于STL deque。我还没为任何其他容器测试。

2、与原生指针比起来，效率较低，除非做一些vector(STL)优化。我还没去尝试。

3、你可以用它来建小型的BST，可以一下子删除它而不用担心内存释放。

4、对于BST的删除元素操作，我会在下一篇帖子中介绍。

历史

第一篇帖子

许可证

本文及相关源代码、文件，由代码项目开放许可证(CPOL)授权。

关于作者

Deepak Kumar Gupta

架构师

印度

我热爱编程，甚至在我接受专业教育之前就开始了（1995年）。从那以后，我一直从事于IP网络栈（写IPv6栈和下一代TCP栈），VoIP，IP安全（IKE/IPSec）。

我最热衷的编程语言是C++，喜欢研究用加强的算法和数据结构来提高基于人工智能的系统。

原文链接：Code Project  翻译：Justme0 (@Just_me0)

译文链接：http://blog.****.net/justme0/article/details/11161191

[ 转载必须在正文中标注并保留原文链接、译文链接和译者等信息。]