c++ - 二进制搜索树数组 Imp。 C++

Question

我只是在插入数组时遇到了麻烦...让子项从根或“父项”分支出来。

我一直在尝试将数据插入到基于数组的 BST 实现中:

BST::BST(int capacity) : items(new item[capacity]), size(0)
{
     // define the constructor to the BST Class.
}

void BST::insert (const data& aData)
{
    if ( items[root].empty ) // make the first data the root.
    {
        items[root].theData = aData;
        items[root].empty = false;
        size++;
    }
    else if ( items[root].theData.getName() < aData )
    {
        items[leftChild].theData = aData; // will be overwritten...
        this->insert(aData);
    }
    else if ( aData < items[root].theData.getName() )
    {
        items[rightChild].theData = aData;
        this->insert(aData);
    }   
}   

这有一些问题。首先让我说第一个传入的数据将是根。所有其他数据将与它进行比较。当我对“插入”进行递归调用时，这基本上就是我“认为”我正在“遍历”的方式(如果它是一个链表)。我的主要问题是知道我的左右 child 将被覆盖。我想知道如何从子“节点”继续分支...？

这是我的 BST 类的头文件，我还担心我是否已正确设置成员以及所有内容......？

class BST
{ 
public:
    BST(int capacity = 5);
    BST(const BST& aTable);

    void insert(const data& aData);
         ....
 private:
    int size;  // size of the ever growing/expanding tree :)

    struct item
    {
        bool empty;
        data theData;
    };

    item  * items;    // The tree array
    int   rightChild; // access to the RHS
    int   leftChild;  // access to the LHS
    int   root;   // index to the root
};

我有另一个源文件，“数据”，我正在调用它，“getname”。到目前为止，我定义的三个简单方法是赋值运算符重载、比较“<”重载和数据类的构造函数:

data::data(char const * const name) : name(new char[strlen(name)+1])
{
    if (name)
    {
        strcpy(this->name , name);
    }  
    else this->name = NULL;
}

data& data::operator=(const data& data2)
{ 
    if ( this != &data2 ) // check for selfassignment
    {
        delete [] name;
        name = NULL;

        this->name = new char[strlen(data2.name)+1];
        strcpy(this->name , data2.name);
    }
    return *this;
     }

bool operator< (const data& d1, const data& d2)
{
    if ( strcmp( d1.getName(), d2.getName() ) == -1 )
    {
        return false;
    }
    else if ( strcmp( d1.getName(), d2.getName() ) == 1 )
    {
        return true;
    }
    return false; // if they are equal return false
}    

Answer 1

我看到了一些问题。 leftChild 和 rightChild 应该是项目结构的成员，而不是 BST 的成员，因为它们对于每个项目都是不同的(或者它们不应该作为字段存在并且被动态计算)。我没有看到任何代码将 leftChild 和 rightChild 设置为任何东西。

看起来您正在尝试递归定义 insert。您可能应该定义一个插入辅助函数，它接受一个项目和一个插入点的索引。这应该会让您走上正确的轨道。

wikipedia article您可以查看更多伪代码。