在C动树++ [英] Dynamic tree in C++
问题描述
我想作一棵树，可以有一些儿童在每一个节点上，但我不知道他们的号码。树必须在小内存使用恒定时间到每个节点codeD（无需额外的数据）。我因子评分，我将让类树价值和子女财产（价值类型为int，儿童叠加）和指针数组在树中的每个节点。我的问题是让这个数组。我怎样才能使它没有额外的数据（的std ::矢量有时会分配更多的内存比它需要）和恒定时间的每一个细胞？
一切正常，但我也需要一定的时间到每个节点。我知道很多节点会如何，但我不知道如何使每个节点的数组。它应该是这样的：
数组[N];结果
A_Node *数组[0] =新A_Node（16）;结果
A_Node * N =新A_Node（1）;结果
数组[0] - >的addChild（N）;结果
阵列[1] = N;结果
要么：
*（数组+ 1）= N;
这是一个可能的例子。它不是一个完整的示例解决方案，但我希望你明白了吧。的一点是，可以有一个双指针的节点，这基本上是一个指针数组到树的节点。
然后你可以自己重新分配的大小和多少但是你要每当有必要。但是，性病::向量已经这样做了你所以除非你想控制一切自己或实验，或者正在写在C的东西在任何情况下，希望这可以帮助没有真正的理由不使用它。
的#include＆LT;＆stdio.h中GT;
＃包括LT＆;＆stdlib.h中GT;//一个节点的子节点的初始缓冲区长度
BUFFER_LENGTH的#define 5
//多少带有如果加法的孩子越过缓冲区倍增
＃定义乘数2///您的节点类
类A_Node
{
上市：
A_Node（int值，无符号整型childrenN = 0）
{
这 - ＆GT;值=价值;
这 - ＆GT; childrenN = childrenN; //分配BUFFER_LENGTH孩子在第一或childrenN节点如果childrenN不是最初为0
如果（childrenN！= 0）
{
这 - ＆GT;孩子=（A_Node **）的malloc（sizeof的（A_Node *）* childrenN）;
这 - ＆GT; BufferLength中= childrenN;
}
其他
{
这 - ＆GT;孩子=（A_Node **）的malloc（sizeof的（A_Node *）* BUFFER_LENGTH）;
这 - ＆GT; BufferLength中BUFFER_LENGTH =;
}
} //在一个节点的析构函数会需要一些特殊照顾
〜A_Node（）
{
//为每一个孩子叫每个孩子的析构函数
的for（int i = 0; I＆LT;这 - ＆GT; childrenN;我++）
{
这 - 删除 - GT;孩子[我]
} //才把释放指针的缓冲器向孩子
免费的（这 - ＆GT;儿童）;
} //添加一个孩子
无效的addChild（A_Node *子）
{
//如果需要重新分配
如果（childrenN＆GT; =＆这个 - GT; BufferLength中）
{
realloc的（这 - ＆GT;孩子的sizeof（A_Node *）*乘数）;
} 这 - ＆GT;儿童[childrenN] =小孩;
这 - ＆GT; childrenN ++;
} A_Node * getChild（无符号整数I）
{
如果（I＆GT; =＆这个 - GT; childrenN）
{
返回0;
} 返回这个 - ＆GT;孩子[我]
} PRINTVALUE无效（）
{
的printf（％d个\\ N，这 - ＆GT;值）;
}
私人的：
int值;
无符号整型childrenN;
A_Node **儿童;
无符号整型BufferLength中;
};///你的树类
类A_Tree
{
上市：
//构造
A_Tree（INT rootValue）
{
根=新A_Node（rootValue）;
}
//析构函数
〜A_Tree（）
{
//递归杀死由于节点的析构函数中的所有节点
删除根;
}
//你的根节点
A_Node *根;
};
诠释的main（）
{
A_Tree树（16）; tree.root-＆GT;的addChild（新A_Node（42））; tree.root-＆GT; PRINTVALUE（）; （tree.root-＆GT; getChild（0）） - ＆GT; PRINTVALUE（）;
返回0;
}
I'd like to make a tree which can have some childrens in every node, but i don't know number of them. Tree have to be coded in small memory using (no extra data) with constant time to every node. I tought that i will make class Tree with value and children property (value is int, and children is stack) and array of pointers to every node in that Tree. My problem is to make this array. How can i make it with no extra data (std::vector sometimes allocate more memory than it needs) and constant time to every cell?
Everything's ok, but i also need constant time to every node. I know how many nodes will be, but i dont know how to make array of every node. It should work something like:
array[n];
Or:
*(array+1)=n;
A_Node *array[0]= new A_Node(16);
A_Node *n = new A_Node(1);
array[0]->addChild(n);
array[1]=n;
This is a possible example. It is not a full example solution but I hope you get the point. The point is that you can have a double pointer to nodes, which is basically an array of pointers to nodes of the tree.
Then you can reallocate the size yourself and to however much you want whenever there is a need to. But std::vector already does that for you so there is no real reason not to use it unless you want to control everything yourself or experiment, or are writing something in C. In any case hope this helps.
#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;
}
这篇关于在C动树++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
