用c++写出(1)构造利用二叉链表存储表示的二叉树; (2)利用先序遍历创建一个二叉树; (3)递归计算二叉树的深度和叶子结点的个数的实验代码并注明实验结论
时间: 2024-01-15 19:04:51 浏览: 84
以下是用C++实现构造利用二叉链表存储表示的二叉树、利用先序遍历创建一个二叉树、递归计算二叉树的深度和叶子结点的个数的代码:
```cpp
#include<iostream>
using namespace std;
struct TreeNode {
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char x) : val(x), left(NULL), right(NULL) {}
};
// 构造利用二叉链表存储表示的二叉树
TreeNode* createTree() {
char c;
cin >> c;
if (c == '#') {
return NULL;
}
TreeNode* root = new TreeNode(c);
root->left = createTree();
root->right = createTree();
return root;
}
// 利用先序遍历创建一个二叉树
TreeNode* createTreeByPreorder() {
char c;
cin >> c;
if (c == '#') {
return NULL;
}
TreeNode* root = new TreeNode(c);
root->left = createTreeByPreorder();
root->right = createTreeByPreorder();
return root;
}
// 递归计算二叉树的深度和叶子结点的个数
void countDepthAndLeaves(TreeNode* root, int& depth, int& leaves) {
if (root == NULL) {
return;
}
depth++;
if (root->left == NULL && root->right == NULL) {
leaves++;
}
countDepthAndLeaves(root->left, depth, leaves);
countDepthAndLeaves(root->right, depth, leaves);
}
int main() {
// 构造利用二叉链表存储表示的二叉树
TreeNode* root1 = createTree();
// 利用先序遍历创建一个二叉树
TreeNode* root2 = createTreeByPreorder();
// 递归计算二叉树的深度和叶子结点的个数
int depth = 0, leaves = 0;
countDepthAndLeaves(root1, depth, leaves);
cout << "Depth: " << depth << ", Leaves: " << leaves << endl;
depth = 0, leaves = 0;
countDepthAndLeaves(root2, depth, leaves);
cout << "Depth: " << depth << ", Leaves: " << leaves << endl;
return 0;
}
```
实验结论:
通过构造利用二叉链表存储表示的二叉树和利用先序遍历创建一个二叉树,我们可以得到两棵不同的二叉树。通过递归计算二叉树的深度和叶子结点的个数,我们可以得到两棵二叉树的深度和叶子结点的个数。因此,实验结论是:不同的二叉树的深度和叶子结点的个数是不同的。
阅读全文