我已经知道如何递归地实现这个函数。这是我的:你如何迭代计算BST(C++)中的节点?
int nodeCount(node *root){
if(root == NULL)
return 0;
return 1 + nodeCount(root->left) + nodeCount(root->right);
}
我现在想执行节点计数没有递归。
我已经知道如何递归地实现这个函数。这是我的:你如何迭代计算BST(C++)中的节点?
int nodeCount(node *root){
if(root == NULL)
return 0;
return 1 + nodeCount(root->left) + nodeCount(root->right);
}
我现在想执行节点计数没有递归。
例如使用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;
}
放松:)被盲目编码 – Scony
@JamesRoot然后,你会如何解决这个问题'n == nullptr'?在循环之前添加'if(root == NULL)return 0;'之类的东西? – CaptainAmericode
@CaptainAmericode旧评论,现在无关紧要。 –
为什么你不想使用递归? – user463035818
如果没有递归,您需要将需要查看的节点存储在数据结构(如堆栈或队列)中。那时你基本上在做“手动”递归。 – Kevin
我试图完全理解递归与迭代的优点,缺点和实现。我试图无情地寻找这个代码的迭代版本,但没有成功。我只是不知道它是什么样子或者它会如何工作。 – CaptainAmericode