首页C++构造二叉链表求叶子个数代码

C++构造二叉链表求叶子个数代码

时间: 2025-02-13 16:23:28 浏览: 23

在C++中，构造二叉链表并计算其中叶子节点的数量通常需要定义一个结构体表示二叉树节点，并编写函数来插入节点、遍历以及检查是否为叶子节点。下面是一个简单的示例： ```cpp #include <iostream> // 定义二叉链表节点结构 struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; // 检查节点是否为叶子节点 bool isLeaf(TreeNode* node) { return !node->left && !node->right; // 如果左右子节点都为空，则是叶子节点 } // 插入新节点到链表 TreeNode* insertNode(TreeNode*& root, int val) { if (!root) { root = new TreeNode(val); return root; } if (val < root->val) root->left = insertNode(root->left, val); else root->right = insertNode(root->right, val); return root; } // 计算叶子节点的数量 int countLeaves(TreeNode* root) { if (!root) return 0; return isLeaf(root) ? 1 : countLeaves(root->left) + countLeaves(root->right); } int main() { TreeNode* root = nullptr; // 假设这里已经通过insertNode函数构建了完整的链表 // ... int leafCount = countLeaves(root); std::cout << "The number of leaves in the binary tree is: " << leafCount << std::endl; return 0; } ``` 在这个例子中，`insertNode` 函数用于添加新节点到二叉链表，`isLeaf` 函数检查某个节点是否为叶子节点，`countLeaves` 函数则递归地计算所有叶子节点的总数。

阅读全文