二叉树的中序遍历算法
时间: 2023-07-26 14:07:20 浏览: 41
二叉树的中序遍历算法可以描述为:
1. 如果树为空,则返回空。
2. 递归遍历左子树。
3. 访问当前节点。
4. 递归遍历右子树。
具体实现可以使用递归或者栈来实现。递归的代码如下:
```
void inorderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
inorderTraversal(root->left);
cout << root->val << " ";
inorderTraversal(root->right);
}
```
使用栈的代码如下:
```
void inorderTraversal(TreeNode* root) {
stack<TreeNode*> s;
TreeNode* p = root;
while (!s.empty() || p != nullptr) {
if (p != nullptr) {
s.push(p);
p = p->left;
} else {
p = s.top();
s.pop();
cout << p->val << " ";
p = p->right;
}
}
}
```
其中,栈的作用是用来存储还未访问的节点。首先将根节点入栈,然后不断将当前节点的左子节点入栈,直到左子节点为空。然后从栈中取出一个节点,并访问该节点,再将右子节点入栈。不断重复这个过程,直到栈为空。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)