用递归的方法实现以下算法: 1.以二叉链表表示二叉树,建立一棵二叉树; 2.输出二叉树的中序遍历结果; 3.输出二叉树的前序遍历结果; 4.输出二叉树的后序遍历结果; 5.计算二叉树的深度; 6.统计二叉树的叶结点个数; 7.输出二叉树中从每个叶子结点到根结点的路径。
时间: 2023-05-25 21:03:59 浏览: 96
1. 建立二叉树的递归函数:
```
// 定义二叉树结点
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 建立二叉树的递归函数
TreeNode* buildTree() {
int val;
cin >> val;
if (val == -1) { // 输入-1表示该节点为空
return nullptr;
}
TreeNode* root = new TreeNode(val);
root->left = buildTree(); // 递归建立左子树
root->right = buildTree(); // 递归建立右子树
return root;
}
```
2. 中序遍历的递归函数:
```
void inorder(TreeNode* root) {
if (root == nullptr) {
return;
}
inorder(root->left);
cout << root->val << " ";
inorder(root->right);
}
```
3. 前序遍历的递归函数:
```
void preorder(TreeNode* root) {
if (root == nullptr) {
return;
}
cout << root->val << " ";
preorder(root->left);
preorder(root->right);
}
```
4. 后序遍历的递归函数:
```
void postorder(TreeNode* root) {
if (root == nullptr) {
return;
}
postorder(root->left);
postorder(root->right);
cout << root->val << " ";
}
```
5. 计算二叉树深度的递归函数:
```
int depth(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int left_depth = depth(root->left);
int right_depth = depth(root->right);
return max(left_depth, right_depth) + 1;
}
```
6. 统计二叉树叶结点个数的递归函数:
```
int countLeaves(TreeNode* root) {
if (root == nullptr) {
return 0;
}
if (root->left == nullptr && root->right == nullptr) { // 叶结点
return 1;
}
return countLeaves(root->left) + countLeaves(root->right);
}
```
7. 输出二叉树中从每个叶子结点到根结点的路径的递归函数:
```
void printPath(TreeNode* root, vector<int>& path) {
if (root == nullptr) {
return;
}
path.push_back(root->val);
if (root->left == nullptr && root->right == nullptr) { // 叶结点
for (int i = path.size() - 1; i >= 0; i--) { // 逆序输出路径
cout << path[i] << " ";
}
cout << endl;
}
printPath(root->left, path); // 递归左子树
printPath(root->right, path); // 递归右子树
path.pop_back(); // 回溯,撤销该节点的选择
}
```