c++ - 存储二叉搜索树节点中某些叶子的数量(优化)

Question

我必须为每个子树计算其父亲标签为奇数且标签为偶数的叶子数量，以及父亲标签为偶数标签且标签为奇数的叶子数量，并将该数字存储在子树的节点中。

例如:this tree (输出在左边)。

这是我的代码

struct node {
    int label;
    node*right;
    node*left;
    int L; //i use this to store the number of leaves
};

void addnodeBST(node*&tree, int l) { //adds a node
    if (!tree) {
        tree = new node;
        tree->label = l;
        tree->right = tree->left = 0;
        tree->L = 0;
        return;
    }
    if (l < tree->label)
        addnodeBST(tree->left, l);
    if (l > tree->label)
        addnodeBST(tree->right, l);
}

int counter(node*tree, int x) { 
    if (!tree)
        return 0;
    if ((!tree->left && !tree->right) && ((x % 2 == 0 && tree->label % 2 == 
       1) || (x % 2 == 1 && tree->label % 2 == 0)))
        return 1;
    return counter(tree->left, tree->label) + counter(tree->right, tree-
    >label);
}

void updateNode(node*tree) {
    if (!tree)
        return;
    tree->L = counter(tree, 0);
    if (!tree->right && !tree->left)
        tree->L = 0;
    updateNode(tree->left);
    updateNode(tree->right);
}

它可以工作，不好的是函数“counter”和“updateNode”在一起。

“计数器”计算要计数的叶子数。

“UpdateNode”利用“计数器”进行计数，然后将每个子树中的叶子数存储到L(我在结构中定义)。

通过这种方式，我将一个递归函数转换为另一个递归函数，并且我多次访问每个节点。

如何优化我的代码？

Answer 1

This way i have a recursive function into another recursive function and i visit each node multiple times.

和之前的部分让你的代码变得丑陋，但真正的问题在于你如何选择遍历树。

在您的 updateNode 函数中，节点的 L 的值只是它的左右子树的总和。因此，如果您更早地调用它们(后序)，而不是像现在这样在函数的末尾调用它们(预序)；现在您知道了它们的 L 而不是调用 counter，您只需将它们相加即可。您只访问每个节点一次。

您可以完全删除您的counter 函数。

这里是修改后的代码(注释解释代码):

//helper to check leaves, null nodes are not leaf
bool isLeaf(node* tree){
    return (tree && (!tree->right) && (!tree->left));
}

//change return type to catch child node's 'L' value through recursive calls 

int updateNode(node*tree) { 
    if (!tree) return 0; //0 for null, for example tree->right for '24'
    if (isLeaf(tree)) tree->L = 0; //All the leaves

    int a,b;
    //find 'L' for left child into a
    if(isLeaf(tree->left)){
        if(tree->left->label%2!=tree->label%2) a=1; //this will be true for '24' and '10'
        else a=0;
    }  
    else a = updateNode(tree->left);

    //Now find 'L' for right child into b
    if(isLeaf(tree->right)){ //this will be true for '10'
        if(tree->right->label%2!=tree->label%2) b=1;
        else b=0;
    }
    else b = updateNode(tree->right);

    //combine them
    tree->L = a+b; //this will be true for '20'
    return tree->L; //return for parent's sake
}

和运行它的驱动程序:

void inorder(node* tree){
    if(!tree) return ;
    inorder(tree->left);
    printf("%d : %d %d\n",tree->label,tree->L,isLeaf(tree) ); 
    inorder(tree->right);
}

int main(int argc, char const *argv[])
{
    node* tree = 0;
    addnodeBST(tree,20);
    addnodeBST(tree,10);
    addnodeBST(tree,24);
    addnodeBST(tree,17);
    addnodeBST(tree,23);
    addnodeBST(tree,5);
    updateNode(tree);
    inorder(tree);
    return 0;
}

并且..您的addnodeBST 将因相等的值而失败。将第二个 if 更改为 else。