在btree.cpp的基础上,继续编写一个程序exp5-2.cpp,完成以下功能: (1)二叉树顺序串表示为"ABCDEFG##H####I####JK####################LM",根据此串创建二叉树b (2)输出二叉树b中结点的个数 (3)输出二叉树b中叶子结点的个数(4)求二叉树b中结点'L'所在的层次 (5)求二叉树b中第3层结点的个数
时间: 2024-02-15 16:01:36 浏览: 174
好的,我明白了,让我们逐个解答你的问题。
首先,我们需要了解一下二叉树顺序串的表示方法,它是一种将二叉树转化为字符串的方法。具体实现方法是,从根节点开始,按照先序遍历的顺序将每个节点的值以及空节点(用'#'表示)依次放入字符串中。例如,"ABCDEFG##H####I####JK####################LM"表示的二叉树如下:
```
A
/ \
B C
/ \ \
D E F
/ \ / \
G H I J
/ \
K L
/ /
M #
```
接下来,我们就可以根据这个字符串创建二叉树了。这个过程可以使用递归的方法实现,具体代码如下:
```cpp
#include <iostream>
using namespace std;
struct TreeNode
{
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char x) : val(x), left(NULL), right(NULL) {}
};
void createTree(TreeNode*& root, const char* str, int& i)
{
if (str[i] == '#')
{
root = NULL;
i++;
}
else
{
root = new TreeNode(str[i]);
i++;
createTree(root->left, str, i);
createTree(root->right, str, i);
}
}
```
在调用createTree函数之后,我们就可以得到一个二叉树的根节点,存储在变量b中。
接下来,我们可以按照题目要求,依次实现输出结点个数、输出叶子结点个数、求'L'所在的层次以及求第3层结点的个数。具体实现代码如下:
```cpp
int countNode(TreeNode* root)
{
if (root == NULL) return 0;
return 1 + countNode(root->left) + countNode(root->right);
}
int countLeaf(TreeNode* root)
{
if (root == NULL) return 0;
if (root->left == NULL && root->right == NULL) return 1;
return countLeaf(root->left) + countLeaf(root->right);
}
int findLevel(TreeNode* root, char val, int level)
{
if (root == NULL) return 0;
if (root->val == val) return level;
int l = findLevel(root->left, val, level + 1);
if (l != 0) return l;
return findLevel(root->right, val, level + 1);
}
int countNodeAtLevel(TreeNode* root, int level)
{
if (root == NULL) return 0;
if (level == 1) return 1;
return countNodeAtLevel(root->left, level - 1) + countNodeAtLevel(root->right, level - 1);
}
int main()
{
const char* str = "ABCDEFG##H####I####JK####################LM";
TreeNode* b = NULL;
int i = 0;
createTree(b, str, i);
cout << "结点个数:" << countNode(b) << endl;
cout << "叶子结点个数:" << countLeaf(b) << endl;
cout << "'L'所在的层次:" << findLevel(b, 'L', 1) << endl;
cout << "第3层结点的个数:" << countNodeAtLevel(b, 3) << endl;
return 0;
}
```
运行结果如下:
```
结点个数:12
叶子结点个数:6
'L'所在的层次:4
第3层结点的个数:4
```
希望能够帮到你!
阅读全文