我目前正在编写一个CART树的实现,它是机器学习中使用的二进制树。它是递归训练的,如以下代码所示:
struct Node
{
Node * parent;
Node * left;
Node * right;
};
void train(Node* node)
{
//perform training algorithm on node
train(node->left);
train(node->right);
}
现在假设我将训练迭代次数限制为一个选定的值,比如nTraining=4
。
然后,通过展开递归函数调用,我预计只有left
分支得到了演化。所以前四个调用是:
train(node);
train(node->left);
train(node->left->left);
train(node->left->left->left);
//only now train(node->left->left->right); would follow
这使得一个完全不平衡的树看起来像
O
/
O O
/
O O
/
O O
/
O O
有人能提出一种方法吗?我可以进一步使用递归训练方法,仍然可以获得平衡树
我想说,不要使用递归(DFS)。使用BFS,也就是队列,这样树就可以逐级遍历:
std::queue<Node*> q;
Node* root;
q.push(root);
for (int i = 0; i < nTraining; ++i) {
Node* node = q.front();
q.pop();
train(node);
q.push(node->left);
q.push(node->right);
}