(一)用递归的方法实现以下算法 1.以二叉链表表示二叉树,建立一棵二叉树; 2.输出二叉树的先序、中序和后序遍历结果; 3.统计二叉树的叶结点个数;
时间: 2023-12-01 07:58:05 浏览: 52
好的,我准备回答这个问题。下面是用递归的方法实现以上算法的C++代码:
1. 以二叉链表表示二叉树,建立一棵二叉树
```c++
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (inorder.empty() || postorder.empty()) return NULL;
int root_val = postorder.back();
TreeNode* root = new TreeNode(root_val);
int root_idx = 0;
while (inorder[root_idx] != root_val) ++root_idx;
vector<int> left_inorder(inorder.begin(), inorder.begin() + root_idx);
vector<int> right_inorder(inorder.begin() + root_idx + 1, inorder.end());
vector<int> left_postorder(postorder.begin(), postorder.begin() + root_idx);
vector<int> right_postorder(postorder.begin() + root_idx, postorder.end() - 1);
root->left = buildTree(left_inorder, left_postorder);
root->right = buildTree(right_inorder, right_postorder);
return root;
}
```
2. 输出二叉树的先序、中序和后序遍历结果
```c++
void preorder(TreeNode* root) {
if (!root) return;
cout << root->val << " ";
preorder(root->left);
preorder(root->right);
}
void inorder(TreeNode* root) {
if (!root) return;
inorder(root->left);
cout << root->val << " ";
inorder(root->right);
}
void postorder(TreeNode* root) {
if (!root) return;
postorder(root->left);
postorder(root->right);
cout << root->val << " ";
}
```
3. 统计二叉树的叶结点个数
```c++
int countLeaves(TreeNode* root) {
if (!root) return 0;
if (!root->left && !root->right) return 1;
return countLeaves(root->left) + countLeaves(root->right);
}
```
希望这些代码可以帮助到你!
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)