二叉树的递归遍历和非递归遍历c语言代码

二叉树的遍历有三种方式：前序遍历、中序遍历和后序遍历。其中，递归遍历是比较常见的方式，而非递归遍历则需要借助栈的数据结构实现。

下面给出二叉树的递归遍历和非递归遍历的C语言代码实现：

1. 二叉树的递归遍历

前序遍历：

void preorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    printf("%d ", root->val); // 访问根节点
    preorderTraversal(root->left); // 递归遍历左子树
    preorderTraversal(root->right); // 递归遍历右子树
}

中序遍历：

void inorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left); // 递归遍历左子树
    printf("%d ", root->val); // 访问根节点
    inorderTraversal(root->right); // 递归遍历右子树
}

后序遍历：

void postorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    postorderTraversal(root->left); // 递归遍历左子树
    postorderTraversal(root->right); // 递归遍历右子树
    printf("%d ", root->val); // 访问根节点
}

2. 二叉树的非递归遍历

前序遍历：

void preorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* node = st.top();
        st.pop();
        printf("%d ", node->val); // 访问节点
        if (node->right != NULL) {
            st.push(node->right); // 右子节点先入栈，保证左子节点先出栈
        }
        if (node->left != NULL) {
            st.push(node->left);
        }
    }
}

中序遍历：

void inorderTraversal(TreeNode* root) {
    stack<TreeNode*> st;
    TreeNode* node = root;
    while (!st.empty() || node != NULL) {
        if (node != NULL) { // 当前节点不为空，继续将其左子节点入栈
            st.push(node);
            node = node->left;
        } else { // 当前节点为空，说明已经到达最左侧，开始出栈访问节点
            node = st.top();
            st.pop();
            printf("%d ", node->val); // 访问节点
            node = node->right; // 开始访问右子节点
        }
    }
}

后序遍历：

void postorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    stack<TreeNode*> st1, st2;
    st1.push(root);
    while (!st1.empty()) {
        TreeNode* node = st1.top();
        st1.pop();
        st2.push(node); // 先将当前节点入栈st2
        if (node->left != NULL) {
            st1.push(node->left); // 左子节点入栈st1
        }
        if (node->right != NULL) {
            st1.push(node->right); // 右子节点入栈st1
        }
    }
    while (!st2.empty()) { // 出栈访问节点
        TreeNode* node = st2.top();
        st2.pop();
        printf("%d ", node->val);
    }
}