バイナリ検索ツリーのノードにある特定のリーフの数を格納する（最適化）

Question

各サブツリーに対して、偶数ラベルの偶数ラベルと奇数ラベルの葉数サブツリーのノードにその番号をラベル付けして格納することもできます。

たとえば、this tree（出力は左側にあります）。

は、これが機能し、「カウンター」と「updateNode」一緒に罰金ではありませんどのような私のコード

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

それが動作する、です。

"カウンタ"は、カウントされる葉の数をカウントします。

"UpdateNode"は "counter"を使用して、各サブツリーのリーフ数をカウントし、L（これは構造体で定義したもの）に格納します。

このように私は別の再帰関数への再帰関数を持っており、私は各ノードを複数回訪れます。

コードを最適化するにはどうすればよいですか？

Answer 1

このように、私は別の再帰関数に再帰関数を持ち、各ノードに複数回アクセスします。

andより前の部分は、コードが醜いものになりますが、本当の悪魔はあなたがツリーを横断する方法にあります。

あなたのupdateNode関数では、ノードの値Lは単純に左と右のサブツリーの合計です。だから、あなたが以前に（postorder）呼び出す場合は、今のようにあなたの関数（preorder）の終わりにそれらを呼び出すのではなく、今すぐあなたはLを知っていて、counterに電話をかけるのではなく、単にそれを追加するだけです。すべてのノードを正確に1回訪問します。

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

And..your addnodeBSTが同じ値で失敗します。 2番目のifをelseに変更します。