c++ - C++中的动态树

Question

我想制作一棵树，每个节点都可以有一些 child ，但我不知道 child 的数量。树必须在小内存中使用(无额外数据)对每个节点进行恒定时间编码。我认为我将创建具有值和子属性(值是 int，子是堆栈)的类树以及指向该树中每个节点的指针数组。我的问题是制作这个数组。我怎样才能做到没有额外的数据(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;
}