基于二叉链表的二叉树的遍历

二叉树的遍历分为三种方式：前序遍历、中序遍历和后序遍历。在基于二叉链表的二叉树中，每个结点（包括根结点）都有左右子树指针，因此可以通过递归方式实现二叉树的遍历。

1. 前序遍历（根-左-右）：

void preOrder(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    cout << root->val << " "; // 输出当前结点的值
    preOrder(root->left); // 递归遍历左子树
    preOrder(root->right); // 递归遍历右子树
}

2. 中序遍历（左-根-右）：

void inOrder(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    inOrder(root->left); // 递归遍历左子树
    cout << root->val << " "; // 输出当前结点的值
    inOrder(root->right); // 递归遍历右子树
}

3. 后序遍历（左-右-根）：

void postOrder(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    postOrder(root->left); // 递归遍历左子树
    postOrder(root->right); // 递归遍历右子树
    cout << root->val << " "; // 输出当前结点的值
}