你如何迭代計算BST（C++）中的節點？

Question

我已經知道如何遞歸地實現這個函數。這是我的：

int nodeCount(node *root){ 
    if(root == NULL) 
     return 0; 
    return 1 + nodeCount(root->left) + nodeCount(root->right); 
} 

我現在想執行節點計數沒有遞歸。

Answer 1

例如使用stack或queue。

Btw。你可能想看看Tail recursion wiki page。

int nodeCount(node * root) 
{ 
    int counter = 0; 
    stack<node*> v; // a container with remaining nodes "to check" 
    v.push(root); // first node "to check" 
    while (v.size() > 0) // while there is something "to check" 
    { 
     node * n = v.top(); // take element from the top of stack 
     v.pop(); // remove that element from the top of stack 
     if (n != NULL) // if node is valid 
     { 
      counter++; // count it 
      v.push(n->left); // and add 
      v.push(n->right); // his children to the stack 
     } 
    } 
    return counter; 
}