c语言数据结构二叉树的非递归遍历代码

二叉树的非递归遍历通常使用栈来实现。以下是三种非递归遍历方式的代码实现：

1. 非递归中序遍历：

void inorderTraversal(TreeNode* root) {
    stack<TreeNode*> st;
    TreeNode* cur = root;
    while (cur != nullptr || !st.empty()) {
        if (cur != nullptr) {
            st.push(cur);
            cur = cur->left;
        } else {
            cur = st.top();
            st.pop();
            cout << cur->val << " ";
            cur = cur->right;
        }
    }
}

2. 非递归先序遍历：

void preorderTraversal(TreeNode* root) {
    stack<TreeNode*> st;
    if (root != nullptr) {
        st.push(root);
    }
    while (!st.empty()) {
        TreeNode* cur = st.top();
        st.pop();
        cout << cur->val << " ";
        if (cur->right != nullptr) {
            st.push(cur->right);
        }
        if (cur->left != nullptr) {
            st.push(cur->left);
        }
    }
}

3. 非递归后序遍历：

void postorderTraversal(TreeNode* root) {
    stack<TreeNode*> st;
    TreeNode* prev = nullptr;
    if (root != nullptr) {
        st.push(root);
    }
    while (!st.empty()) {
        TreeNode* cur = st.top();
        if ((cur->left == nullptr && cur->right == nullptr) || (prev != nullptr && (prev == cur->left || prev == cur->right))) {
            cout << cur->val << " ";
            st.pop();
            prev = cur;
        } else {
            if (cur->right != nullptr) {
                st.push(cur->right);
            }
            if (cur->left != nullptr) {
                st.push(cur->left);
            }
        }
    }
}