二进制搜索树阵列Imp。 C++

我只是在插入到数组中遇到问题...并让孩子从根分支或“父母”..二进制搜索树阵列Imp。 C++

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

有几件事情是错误的。首先让我说第一个传入的数据将是根。所有其他数据将与它进行比较。当我递归调用“插入”时，基本上我是如何“思考”我是“遍历”（如果它是一个链表）。我的主要问题是知道我的左右儿童会被覆盖。我想知道如何保持从孩子的“节点”分支......？

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

来源

2009-11-10 user40120

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

它看起来像你试图递归定义insert。您应该定义一个插入帮助器函数，该函数可以同时获取插入点的项目和索引。这应该让你走上正轨。

该wikipedia article有更多的伪代码，你可以看看。

来源

2009-11-10 23:53:05

好的。鉴于他们应该是项目结构的成员，使用它们作为我的数组实现的索引还是明智的吗？ – user40120 2009-11-10 23:59:12

这就是我的困惑所在。如何作为一个数组工作？我已经完成链表，但我似乎无法完成连接。 – user40120 2009-11-11 00:00:44

链表实现是否使用指针或索引？相同的技术将在这里工作，只是每个项目有两个下一个指针而不是一个。还有几件事需要考虑：一个新项目是如何分配的（eqivalently，leftChild和rightChild如何设置）？如果物品没有离开孩子，那么leftChild有什么价值？如何实现查找（应该比插入更容易）？ – 2009-11-11 00:10:40

二进制搜索树阵列Imp。 C++

回答

相关问题