我目前正在编写一个CART树的实现，这是一种用于机器学习的二叉树。它按照以下代码所示的方式递归训练：

struct Node{    Node * parent;    Node * left;    Node * right;};void train(Node* node){    //在节点上执行训练算法    train(node->left);    train(node->right);}

现在假设我将训练迭代次数限制为一个选定的值，比如nTraining=4。

那么，通过展开递归函数调用，我期望只有left分支会被展开。因此，前四个调用是：

    train(node);    train(node->left);    train(node->left->left);    train(node->left->left->left);    //只有现在才会调用train(node->left->left->right);

这会得到一个完全不平衡的树，看起来像这样：

          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);}