首页用C语言求二叉树的结点总数的非递归算法

用C语言求二叉树的结点总数的非递归算法

时间: 2024-12-19 13:24:50 浏览: 48

在C语言中，非递归地计算二叉树节点总数可以采用栈的数据结构。这种方法称为“层次遍历”或“广度优先搜索(BFS)”，因为它是从根节点开始，按照层次顺序逐层遍历。以下是步骤： 1. 创建一个栈，并将根节点压入栈中。 2. 初始化一个计数器`count`用于存储节点总数，初始值为0。 3. 当栈不为空时，循环执行以下操作： a. 弹出栈顶节点。 b. 将该节点的左子节点和右子节点（如果存在）分别压入栈中。 c. 计数器加一，表示当前访问了一个节点。 4. 遍历完成后，`count`变量就是二叉树的节点总数。下面是一个简单的C语言函数示例： ```c #include <stdio.h> #include <stdlib.h> typedef struct TreeNode { int val; struct TreeNode* left; struct TreeNode* right; } TreeNode; int countNodes(TreeNode* root) { if (root == NULL) return 0; // 如果空节点，返回0 stack<TreeNode*> s; s.push(root); while (!s.isEmpty()) { TreeNode* node = s.pop(); count++; // 如果有左右子节点，再将其推入栈 if (node->left != NULL) s.push(node->left); if (node->right != NULL) s.push(node->right); } return count; } // 示例用法： TreeNode* createBinaryTree() { ... } // 你自己定义创建二叉树的函数 int main() { TreeNode* tree = createBinaryTree(); int nodesCount = countNodes(tree); printf("The total number of nodes is: %d\n", nodesCount); return 0; } ```

阅读全文