中序遍历三叉树的C++代码
时间: 2024-09-28 16:10:08 浏览: 18
在C++中,中序遍历三叉树(也称为二叉搜索树,每个节点的左子树的所有节点都小于该节点,右子树的所有节点都大于该节点)通常涉及递归。以下是一个基本的中序遍历三叉树的示例代码:
```cpp
#include <iostream>
using namespace std;
// 定义三叉树结点
struct TreeNode {
int val; // 节点值
TreeNode* left; // 左孩子指针
TreeNode* middle; // 中间孩子指针(假设三叉树)
TreeNode* right; // 右孩子指针
TreeNode(int x) : val(x), left(NULL), middle(NULL), right(NULL) {}
};
// 中序遍历辅助函数
void inorderTraversal(TreeNode* node) {
if (node == NULL) {
return;
}
inorderTraversal(node->left); // 遍历左子树
cout << node->val << " "; // 访问根节点
inorderTraversal(node->right); // 遍历右子树
}
int main() {
// 创建一个示例三叉树
TreeNode* root = new TreeNode(5);
root->middle = new TreeNode(3);
root->middle->left = new TreeNode(1);
root->middle->right = new TreeNode(6);
root->right = new TreeNode(9);
root->right->left = new TreeNode(7);
// 执行中序遍历
inorderTraversal(root);
return 0;
}
```
在这个例子中,`inorderTraversal` 函数先递归地访问左子树,然后访问根节点,再递归地访问右子树。这样就能保证按照升序打印出所有节点的值。