编写一算法,输出二叉树的中序遍历序列。
时间: 2023-06-19 22:09:38 浏览: 55
中序遍历是指先遍历左子树,然后访问根节点,最后遍历右子树。因此,我们可以使用递归的方式实现中序遍历。
具体实现如下:
```
void inorderTraversal(TreeNode* root, vector<int>& res) {
if (root == nullptr) {
return;
}
inorderTraversal(root->left, res);
res.push_back(root->val);
inorderTraversal(root->right, res);
}
```
其中,`TreeNode` 是二叉树节点的结构体,包含 `val`、`left` 和 `right` 三个成员变量,分别表示节点的值、左子节点和右子节点。
我们可以定义一个 `vector<int>` 类型的变量 `res`,用来存储中序遍历的结果。然后调用 `inorderTraversal` 函数,将根节点和 `res` 作为参数传递进去,函数会递归遍历左子树、访问根节点和递归遍历右子树,并将访问的节点值存储到 `res` 中。
以下是完整代码实现:
```
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
void inorderTraversal(TreeNode* root, vector<int>& res) {
if (root == nullptr) {
return;
}
inorderTraversal(root->left, res);
res.push_back(root->val);
inorderTraversal(root->right, res);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
inorderTraversal(root, res);
return res;
}
```
调用 `inorderTraversal` 函数,并输出结果:
```
int main() {
TreeNode* root = new TreeNode(1);
root->right = new TreeNode(2);
root->right->left = new TreeNode(3);
vector<int> res = inorderTraversal(root);
for (int i = 0; i < res.size(); i++) {
cout << res[i] << " ";
}
cout << endl;
return 0;
}
```
输出:
```
1 3 2
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![](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)