Binary Search Tree Array Imp.C++

Question

我只是在将子代从根分支或“父”分支插入到array...And中时遇到了问题。

我一直在尝试将数据插入到基于数组的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);
    }   
}   

这其中有一些地方是错误的。首先让我说，第一个传入的数据将是根。所有其他数据都将与其进行比较。当我对"insert“进行递归调用时，这本质上就是我”思考“的方式，我正在”遍历“(如果它是一个链表)。对我来说，主要的问题是知道我的左边和右边的孩子会被覆盖。我想知道怎样才能保持从子“节点”开始的分支？

这是我的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
};

我还有另一个源文件"data“，我正在调用它"getname”。到目前为止，我已经定义了三个简单的方法:赋值操作符重载，比较'<‘重载和数据类的ctor：

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应该是item结构的成员，而不是BST的成员，因为它们对于每个item都是不同的(或者它们不应该作为字段存在并动态计算)。我看不到任何代码会将leftChild和rightChild设置为任何值。

看起来您正在尝试递归地定义insert。您可能应该定义一个插入帮助器函数，该函数同时接受插入点的项和索引。这应该会让你走上正确的道路。

wikipedia article有更多的伪代码可供查看。