c 二叉树的非递归遍历的全部代码

非递归遍历二叉树常用的方法是使用栈。以下是C语言实现二叉树非递归遍历的全部代码。

先定义二叉树节点结构体：

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

接下来是三种遍历方式的代码：

1. 非递归前序遍历

void preorderTraversal(struct TreeNode* root){
    if(root == NULL){
        return;
    }
    struct TreeNode* stack[1000];
    int top = -1;
    stack[++top] = root;
    while(top >= 0){
        struct TreeNode* node = stack[top--];
        printf("%d ", node->val);
        if(node->right != NULL){
            stack[++top] = node->right;
        }
        if(node->left != NULL){
            stack[++top] = node->left;
        }
    }
}

2. 非递归中序遍历

void inorderTraversal(struct TreeNode* root){
    if(root == NULL){
        return;
    }
    struct TreeNode* stack[1000];
    int top = -1;
    struct TreeNode* cur = root;
    while(cur != NULL || top >= 0){
        while(cur != NULL){
            stack[++top] = cur;
            cur = cur->left;
        }
        struct TreeNode* node = stack[top--];
        printf("%d ", node->val);
        cur = node->right;
    }
}

3. 非递归后序遍历

void postorderTraversal(struct TreeNode* root){
    if(root == NULL){
        return;
    }
    struct TreeNode* stack[1000];
    int top = -1;
    stack[++top] = root;
    struct TreeNode* pre = NULL;
    while(top >= 0){
        struct TreeNode* node = stack[top];
        if((node->left == NULL && node->right == NULL) || (pre != NULL && (pre == node->left || pre == node->right))){
            printf("%d ", node->val);
            top--;
            pre = node;
        } else {
            if(node->right != NULL){
                stack[++top] = node->right;
            }
            if(node->left != NULL){
                stack[++top] = node->left;
            }
        }
    }
}