求二叉树中求结点总数算法(提示:可在某种遍历过程中统计遍历的结点数),并在主函数中补充相应的调用验证正确性。
时间: 2024-05-14 09:19:33 浏览: 11
好的,关于您的问题,二叉树中求结点总数的算法通常有两种实现方式:
方法一:递归实现
在递归方式下,先递归计算左子树的结点数,再递归计算右子树的结点数,最后将左右子树的结点数加上根结点的1即可。
代码实现如下:
```
int countNodes(TreeNode* root) {
if (!root) {
return 0;
}
int leftCount = countNodes(root->left);
int rightCount = countNodes(root->right);
return leftCount + rightCount + 1;
}
```
方法二:迭代实现
在迭代方式下,从根结点开始,将根结点压入栈中,然后当栈不为空时,循环弹出栈顶结点并将其计数器加一,然后再压入其左右子结点(如果非空)。
代码实现如下:
```
int countNodes(TreeNode* root) {
if (!root) {
return 0;
}
stack<TreeNode*> s;
s.push(root);
int count = 0;
while (!s.empty()) {
TreeNode* cur = s.top();
s.pop();
count++;
if (cur->left) {
s.push(cur->left);
}
if (cur->right) {
s.push(cur->right);
}
}
return count;
}
```
为了验证算法的正确性,我们可以在主函数中生成一颗二叉树并调用 countNodes 函数进行测试,代码如下:
```
int main() {
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(7);
int nodeCount = countNodes(root);
cout << "The node count is: " << nodeCount << endl;
return 0;
}
```
输出结果为:
```
The node count is: 7
```
可以发现,输出结果正确,算法验证成功。