Динамическое дерево в C ++

Question

Я хотел бы сделать дерево, в котором может быть несколько детей в каждом узле, но я не знаю их количество.Дерево должно быть закодировано в небольшой памяти с использованием (без дополнительных данных) с постоянным временем для каждого узла.Я думал, что создам класс Tree со значением и дочерним свойством (значение равно int, а children это стек) и массив указателей на каждый узел в этом дереве.Моя проблема состоит в том, чтобы сделать этот массив.Как я могу сделать это без лишних данных (std::vector иногда выделяет больше памяти, чем нужно) и с постоянным временем для каждой ячейки?

Все в порядке, но мне также нужно постоянное время для каждого узла.Я знаю, сколько будет узлов, но я не знаю, как сделать массив каждого узла.Должно работать что-то вроде: array[n];<br> A_Node *array[0]= new A_Node(16);<br> A_Node *n = new A_Node(1);<br> array[0]->addChild(n);<br> array[1]=n;<br> Или: * (массив + 1) = n;

Answer 1

Это возможный пример. Это не полный пример решения, но я надеюсь, что вы поняли суть. Дело в том, что вы можете иметь двойной указатель на узлы, который в основном представляет собой массив указателей на узлы дерева.

Тогда вы можете перераспределить размер самостоятельно и сколько захотите, когда в этом есть необходимость. Но std :: vector уже делает это для вас, поэтому нет никакой реальной причины не использовать его, если вы не хотите сами все контролировать, экспериментировать или писать что-то на C. В любом случае, надеюсь, это поможет.

#include <stdio.h>
#include <stdlib.h>

// The initial buffer length of a node's children
#define BUFFER_LENGTH   5
// How much to multiply with if an addition of a child goes over the buffer
#define MULTIPLIER 2

///Your node class
class A_Node
{
    public:
    A_Node(int value,unsigned int childrenN=0)
    {
        this->value = value;
        this->childrenN = childrenN;

        //allocate BUFFER_LENGTH children for the node at first or childrenN if the childrenN is not initially 0
        if(childrenN != 0)
        {
            this->children = (A_Node**) malloc(sizeof(A_Node*)*childrenN);
            this->bufferLength = childrenN;
        }
        else
        {
            this->children = (A_Node**) malloc(sizeof(A_Node*)*BUFFER_LENGTH);
                        this->bufferLength =BUFFER_LENGTH;
        }
    }

    //in the destructor of a node it would need some special care
    ~A_Node()
    {
        //for every child call the destructor of each child
        for(int i = 0; i < this->childrenN; i++)
        {
            delete this->children[i];
        }

        //and only then free the buffer of the pointers to the children
        free(this->children);
    }

    //adds a child
    void addChild(A_Node* child)
    {
        //reallocate if needed
        if(childrenN >= this->bufferLength)
        {
            realloc(this->children,sizeof(A_Node*)*MULTIPLIER);
        }

        this->children[childrenN] = child;
        this->childrenN++;
    }

    A_Node* getChild(unsigned int i)
    {
        if(i >= this->childrenN)
        {
            return 0;
        }

        return this->children[i];
    }

    void printValue()
    {
        printf("%d\n",this->value);
    }
private:
    int value;
    unsigned int childrenN;
    A_Node** children;
    unsigned int bufferLength;
};

///Your tree class
class A_Tree
{
    public:
        //constructor
        A_Tree(int rootValue)
        {
            root = new A_Node(rootValue);
        }
        //destructor
        ~A_Tree()
        {
            //recursively kills all the nodes due to the destructor of node
            delete root;
        }
        //your root node
        A_Node* root;
};


int main()
{
    A_Tree tree(16);

    tree.root->addChild(new A_Node(42));

    tree.root->printValue();

    (tree.root->getChild(0))->printValue();


    return 0;
}

Answer 2

Просто следите за памятью самостоятельно, а не с помощью вектора:

class Node {
public:
    // In the constructor, initialize your array of children to NULL
    // and the size of your children array to zero
    Node() : mChildren(NULL), mSize(0) {}

    void AddChild(Node* newChild) {
        // allocate space for your new array
        Node** newArray = new Node*[mSize + 1];

        // copy over nodes from old array to new array
        for (int i = 0; i < mSize; i++) {
            newArray[i] = mChildren[i];
        }

        // add in our new child to the end of the array
        newArray[mSize++] = newChild;

        // if there was an old array (null check) free the memory
        if (mChildren) {
            delete [] mChildren;
        }

        // set our children array equal to our new array
        mChildren = newArray;
    }

    Node* AccessChild(size_t index) {
        // make sure it's a valid index and then return
        assert(index < mSize);
        return mChildren[index];
    }

private:
    Node** mChildren;
    int mSize;
};

Это не будет иметь дополнительного пространства для дополнительных узлов, но для этого потребуется размер int, чтобы отслеживать, сколько узлов вы храните. Я не вижу, как вы могли бы сделать это без этого или без постоянного числа детей.

Обратите внимание, что векторы удваиваются по размеру каждый раз, когда им нужно перераспределить, потому что это более эффективно. Хотя приведенное выше решение будет более эффективным с точки зрения памяти, оно значительно ухудшит производительность, поскольку потребует выделения для каждого дочернего дополнения, которое потребует O (N) для добавления N узлов.

Производительность вектора будет состоять из O (log (N)) для добавления N узлов, но опять-таки это решение звучит так, как будто у вас есть требуемая эффективность памяти.