首页已知二叉树采用二叉链表存储，（1）定义其存储结构。（3分）（2）写算法输出所有叶子结点的个数。（7分）

已知二叉树采用二叉链表存储，（1）定义其存储结构。（3分）（2）写算法输出所有叶子结点的个数。（7分）

时间: 2024-10-27 09:11:49 浏览: 44

（1）已知二叉树采用二叉链表存储，存储结构通常包含以下几个关键部分： ```c++ // 定义二叉树节点 struct TreeNode { int val; // 节点值 TreeNode* left; // 左子节点指针 TreeNode* right; // 右子节点指针 TreeNode(int x) : val(x), left(NULL), right(NULL) {} // 构造函数，初始化值和空指针 }; ``` 在这个结构中，`val`用于存储节点的值，`left`和`right`分别指向左子节点和右子节点，如果某个子节点不存在，则相应的指针为NULL。（2）以下是计算二叉树叶子节点个数的算法（假设我们有一个名为`root`的根节点）： ```c++ int countLeaves(TreeNode* root) { if (root == NULL) return 0; // 如果根节点为空，直接返回0 // 递归地检查左右子节点 if (root->left == NULL && root->right == NULL) return 1; // 如果当前节点既是左子又是右子节点，它是叶子 else return countLeaves(root->left) + countLeaves(root->right); // 否则，累加左右子树的叶子数 } ``` 该算法通过深度优先搜索（DFS），遍历整棵树并计数叶子节点。每个非叶子节点都会递归地调用自身两次，直到找到叶子节点为止。

阅读全文