c++2-3-4-tree

node array declaration


I am trying to initialize a node array in the node class, they are private members:

    #include<iostream>
    #include<string>
    using namespace std;
    class Data
    {
    public:
        long data;
        Data(long dd)
        {
            data=dd;
        }
        void displaydata()
        {
            cout<<data <<"  "<<endl;
        }
    };
    class node
    {
//these are what i have changed
        const static int order=4;
        int numitems;
        node *parent;


    vector<node>childarray(order);
        vector<Data>itemarray(order-1);

    };

but unfortunately it does not compile, the errors are:

  1>c:\users\dato\documents\visual studio 2010\projects\234_tree\234_tree\234_tree.cpp(26): error C2061: syntax error : identifier 'order'
    1>c:\users\dato\documents\visual studio 2010\projects\234_tree\234_tree\234_tree.cpp(27): error C2061: syntax error : identifier 'order'
    ========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

From the following java code.

class DataItem
{
public long dData; // one data item
//--------------------------------------------------------------
public DataItem(long dd) // constructor
{ dData = dd; }
//--------------------------------------------------------------
public void displayItem() // display item, format “/27”
{ System.out.print(“/”+dData); }
//--------------------------------------------------------------
} // end class DataItem
////////////////////////////////////////////////////////////////
class Node
{
private static final int ORDER = 4;
private int numItems;
private Node parent;
private Node childArray[] = new Node[ORDER];
private DataItem itemArray[] = new DataItem[ORDER-1];
// -------------------------------------------------------------
// connect child to this node
public void connectChild(int childNum, Node child)
{
childArray[childNum] = child;
if(child != null)
child.parent = this;
}
// -------------------------------------------------------------
// disconnect child from this node, return it
public Node disconnectChild(int childNum)
{
Node tempNode = childArray[childNum];
childArray[childNum] = null;
return tempNode;
}
// -------------------------------------------------------------
public Node getChild(int childNum)
{ return childArray[childNum]; }
// -------------------------------------------------------------
public Node getParent()
{ return parent; }
// -------------------------------------------------------------
public boolean isLeaf()
Java Code for a 2-3-4 Tree 479
LISTING 10.1 Continued
{ return (childArray[0]==null) ? true : false; }
// -------------------------------------------------------------
public int getNumItems()
{ return numItems; }
// -------------------------------------------------------------
public DataItem getItem(int index) // get DataItem at index
{ return itemArray[index]; }
// -------------------------------------------------------------
public boolean isFull()
{ return (numItems==ORDER-1) ? true : false; }
// -------------------------------------------------------------
public int findItem(long key) // return index of
{ // item (within node)
for(int j=0; j<ORDER-1; j++) // if found,
{ // otherwise,
if(itemArray[j] == null) // return -1
break;
else if(itemArray[j].dData == key)
return j;
}
return -1;
} // end findItem
// -------------------------------------------------------------
public int insertItem(DataItem newItem)
{
// assumes node is not full
numItems++; // will add new item
long newKey = newItem.dData; // key of new item
for(int j=ORDER-2; j>=0; j--) // start on right,
{ // examine items
if(itemArray[j] == null) // if item null,
continue; // go left one cell
else // not null,
{ // get its key
long itsKey = itemArray[j].dData;
if(newKey < itsKey) // if it’s bigger
itemArray[j+1] = itemArray[j]; // shift it right
else
{
itemArray[j+1] = newItem; // insert new item

Please help me to convert code easily, do I have to declare the order as public? I have tried but it does not work, I have also tried declaration of order outside of the class, like const int node::order=4 but have had no success yet, what is the problem? I need array which holds members, size should be order or 4. When I was reading book, author said what you need while writing java code in C++ from this book, it says pointer, so I have added pointer, but no success yet.


Solution

  • The lines

    node *childarray[]=new node[order];
    Data *itemarray[]=new Data[order-1];
    

    are in error here. Beside that you can not assign like this in the class, you also have the declaration wrong. You are declaring e.g. childarray to be an array of pointers, but you are creating it as a simple array. Change declarations to

    node *childarray;
    Data *itemarray;
    

    To actually do the allocation you have to do it in a constructor.

    However, I really recommend you use std::array (or possibly std::vector) instead.

    Edit: Using std::array:

    struct node
    {
        static const int ORDER = 4;
        int numitems;
        node* parent;
        std::array<node*, ORDER> childarray;
        std::array<Data*, ORDER - 1> itemarray;
    
        node()
            : numitems{0},
              parent{nullptr},
              childarray{{nullptr}},
              itemarray{{nullptr}}
            { }
    };
    

    Now childarray and itemarray are arrays with ORDER and ORDER - 1 (respectively) number of pointers, all initialized to nullptr (what NULL should now).