c语言分别实现二叉树前序 中序 后序的非递归算法

在C语言中，非递归地实现二叉树的前序、中序和后序遍历，通常会使用栈数据结构来辅助。下面我会分别给出三种遍历的非递归算法：

### 1. 前序遍历 (Preorder Traversal)
前序遍历顺序是：根节点 -> 左子树 -> 右子树。非递归版本通过栈保存访问路径。

void preOrder(Node* root) {
    Stack *stack = createStack(); // 创建空栈
    if (root != NULL) {
        push(stack, root); // 将根节点压入栈
        while (!isEmpty(stack)) {
            Node* node = pop(stack);
            // 打印当前节点
            print(node->data);

            // 如果左子节点存在，压入栈
            if (node->left != NULL)
                push(stack, node->left);

            // 如果右子节点存在，压入栈
            if (node->right != NULL)
                push(stack, node->right);
        }
    }
}

### 2. 中序遍历 (Inorder Traversal)
中序遍历顺序是：左子树 -> 根节点 -> 右子树。这里同样借助栈，先处理左子树。

void inOrder(Node* root) {
    Stack *stack = createStack();
    Node* curr = root;
    
    while (curr != NULL || !isEmpty(stack)) {
        // 遍历左子树
        while (curr != NULL) {
            push(stack, curr);
            curr = curr->left;
        }

        curr = pop(stack);
        // 打印当前节点
        print(curr->data);

        curr = curr->right; // 移动到右子树
    }
}

### 3. 后序遍历 (Postorder Traversal)
后序遍历顺序是：左子树 -> 右子树 -> 根节点。这里需要用到两个栈，先存储节点，然后按照相反的顺序出栈。

void postOrder(Node* root) {
    Stack *stack1 = createStack(), *stack2 = createStack();
    stack1 = pushAndPop(root, stack1, stack2); // 先将根节点压入第二个栈

    while (!isEmpty(stack1)) {
        Node* node = pop(stack1);
        // 如果当前节点有右子节点未访问，将它压入第一个栈
        if (node->right) {
            push(stack1, node->right);
        } else {
            // 现在处理左子树，将其余所有节点依次从第一个栈弹出并压入第二个栈
            Node* temp = node;
            while (!isEmpty(stack1) && temp->left == NULL) {
                temp = pop(stack1);
                push(stack2, temp);
            }
            // 最后将根节点（非空）放入第二个栈，以便于最后访问
            push(stack2, temp);
        }
    }

    // 从第二个栈中依次弹出并打印节点
    while (!isEmpty(stack2))
        print(pop(stack2)->data);
}

// 辅助函数，将节点及其子节点压入两个栈
Node* pushAndPop(Node* node, Stack* stack1, Stack* stack2) {
    push(stack1, node);
    if (node->left != NULL) {
        pushAndPop(node->left, stack1, stack2);
    }
    if (node->right != NULL) {
        pushAndPop(node->right, stack1, stack2);
    }
    return pop(stack2);
}