C++数据结构——中序遍历二叉树
时间: 2023-08-25 12:07:56 浏览: 146
中序遍历是二叉树遍历的一种,遍历顺序为左子树、根节点、右子树。以下是C++代码实现:
```c++
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void inorderTraversal(TreeNode* root) {
if(root == NULL) return;
inorderTraversal(root->left);
cout << root->val << " ";
inorderTraversal(root->right);
}
int main() {
TreeNode* root = new TreeNode(1);
root->right = new TreeNode(2);
root->right->left = new TreeNode(3);
inorderTraversal(root);
return 0;
}
```
输出结果为:1 3 2
这里我们只是简单地输出了遍历的结果,实际应用中可以对遍历到的节点进行其他操作。
相关问题
c++实现非递归中序遍历二叉树
以下是C++实现非递归中序遍历二叉树的代码:
```c++
#include <iostream>
#include <stack>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void inorderTraversal(TreeNode* root) {
stack<TreeNode*> s;
TreeNode* cur = root;
while (cur != NULL || !s.empty()) {
while (cur != NULL) {
s.push(cur);
cur = cur->left;
}
cur = s.top();
s.pop();
cout << cur->val << " ";
cur = cur->right;
}
}
int main() {
TreeNode* root = new TreeNode(1);
root->right = new TreeNode(2);
root->right->left = new TreeNode(3);
inorderTraversal(root); // 输出:1 3 2
return 0;
}
```
数据结构中序遍历二叉树图解
好的,我知道你的问题。
中序遍历是二叉树遍历的一种。它的基本思想是:按照左子树、根结点、右子树的顺序,访问二叉树中的所有节点,得到的序列就是二叉树的中序遍历序列。
下面是对二叉树进行中序遍历的图解:
首先,先访问左子树,一直递归到最左下角的叶子节点。如图中的节点A。
然后,依次访问每个节点的根节点,如图中的节点B。
最后,访问右子树,一直递归到最右下角的叶子节点。如图中的节点C。
按照这个顺序,我们访问完整棵二叉树之后,得到的就是中序遍历序列。