二进制搜索树数组展示次数.C ++ [英] Binary Search Tree Array Imp. C++

问题描述

我只是在插入数组时遇到麻烦...并且让子级从根或父级"分支出来..

I'm just having trouble with Inserting into the array...And having the children branch off from the root, or "parent"..

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

I've been trying to insert data into an array based implementation of a 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);
    }   
}   

这有一些问题.首先，我要说的是第一个传入的数据将是根.所有其他数据都将与之进行比较.当我对插入"进行递归调用时，这实际上是我思考"的方式，即遍历"(如果它是一个链表).我的主要问题是知道我的左右孩子将被覆盖.我想知道如何继续从子节点"分支……?

A few things are wrong with this. Let me start by saying that the first incoming data will be the root. All other data will be compared against it. When I make the recursive calls to "insert" that is essentially how I "think" i am "traversing" (if it were a linked list). The main problem for me is knowing that my left and right children will be overwritten. I'm wondering How I can keep branching from the child "nodes"...?

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

Here is my header file for the BST class, I'm also concerned if I have set the members up right and everything..?

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".到目前为止，我已经定义了三种简单的方法，即赋值运算符重载，比较<"重载和数据类的ctor:

I have another source file, "data" to which i am making the calls, "getname". Three simple methods I have defined so far are the assignment operator overload, comparison '<' overload and the ctor to the data class:

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
}    

推荐答案

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

I see a few problems. leftChild and rightChild should be members of the item struct, not of BST, because they are different for every item (or they should not exist as fields and be computed dynamically). I see no code that ever sets leftChild and rightChild to anything.

您似乎正在尝试递归定义插入.您可能应该定义一个插入帮助器函数，该函数同时接受项和插入点的索引.那应该使您走上正确的轨道.

It looks like you're trying to recursively define insert. You should probably define an insert helper function that takes both an item and an index of the insertion point. That should set you on the right track.

维基百科文章有更多的伪代码，您可以查看.

The wikipedia article has more pseudocode you can look at.

这篇关于二进制搜索树数组展示次数.C ++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！