C ++平衡树/递归函数中的调用顺序

Question

我正在写一个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

这给出了一个完全不平衡的树看起来像

任何人都可以建议我可以进一步使用递归训练方法并仍然获得平衡树的方法吗？

Answer 1

我会说，不要使用递归 (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);
}

C ++平衡树/递归函数中的调用顺序

C++ balanced tree / call order in recursive function

c++

tree

recursion

machine-learning

tree-balancing