二叉树非递归遍历C语言如何实现？-C语言-盈思创科技

非递归遍历的核心思想是使用栈来模拟递归调用的过程，递归本质上就是系统帮我们维护了一个函数调用栈，非递归则是我们自己手动实现这个栈。

（图片来源网络，侵删）

准备工作：二叉树节点和栈的定义

我们需要定义二叉树的节点结构,为了方便非递归遍历，我们最好同时定义一个用于存储节点指针和访问次数的栈结构。

#include <stdio.h>
#include <stdlib.h>
// 二叉树节点定义
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;
// 用于非递归遍历的栈节点定义
// 这个栈不仅要存节点指针，还要存一个“访问次数”或“状态”
// 0表示该节点的左子树还未被访问
// 1表示该节点的左子树已被访问，右子树还未被访问
typedef struct StackNode {
    TreeNode *treeNode;      // 指向二叉树节点的指针
    int flag;                // 访问标志，0:未访问左子树, 1:已访问左子树
} StackNode;
// 栈的定义
typedef struct Stack {
    StackNode *data;         // 栈数组
    int top;                 // 栈顶指针
    int capacity;            // 栈容量
} Stack;
// 辅助函数：创建新节点
TreeNode* createNode(int val) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    if (!newNode) {
        perror("Memory allocation failed");
        exit(EXIT_FAILURE);
    }
    newNode->val = val;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}
// 辅助函数：初始化栈
Stack* createStack(int capacity) {
    Stack* s = (Stack*)malloc(sizeof(Stack));
    if (!s) {
        perror("Memory allocation failed");
        exit(EXIT_FAILURE);
    }
    s->data = (StackNode*)malloc(capacity * sizeof(StackNode));
    if (!s->data) {
        perror("Memory allocation failed");
        exit(EXIT_FAILURE);
    }
    s->top = -1;
    s->capacity = capacity;
    return s;
}
// 辅助函数：判断栈是否为空
int isEmpty(Stack* s) {
    return s->top == -1;
}
// 辅助函数：入栈
void push(Stack* s, TreeNode* treeNode, int flag) {
    if (s->top == s->capacity - 1) {
        printf("Stack is full\n");
        return;
    }
    s->top++;
    s->data[s->top].treeNode = treeNode;
    s->data[s->top].flag = flag;
}
// 辅助函数：出栈
StackNode pop(Stack* s) {
    if (isEmpty(s)) {
        printf("Stack is empty\n");
        // 返回一个无效的节点，调用者需要处理
        StackNode emptyNode = {NULL, -1};
        return emptyNode;
    }
    return s->data[s->top--];
}
// 辅助函数：获取栈顶元素（不出栈）
StackNode peek(Stack* s) {
    if (isEmpty(s)) {
        StackNode emptyNode = {NULL, -1};
        return emptyNode;
    }
    return s->data[s->top];
}

前序遍历 (Preorder Traversal - 根-左-右)

思路：

创建一个空栈,并将根节点入栈（状态为0）。
当栈不为空时,循环执行以下操作： a. 弹出栈顶元素。 b. 访问该节点（打印值）。 c. 如果该节点有右子树，则将右子节点入栈（状态为0）。 d. 如果该节点有左子树，则将左子节点入栈（状态为0）。

注意：因为栈是“后进先出”（LIFO）的结构，为了让左子树后进先出，我们必须先压右子树，再压左子树。

// 非递归前序遍历
void preorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    // 栈容量可以根据树的最大深度来设定，这里简单设为100
    Stack* s = createStack(100); 
    push(s, root, 0); // 根节点入栈
    while (!isEmpty(s)) {
        StackNode current = pop(s);
        TreeNode* node = current.treeNode;
        // 访问节点
        printf("%d ", node->val);
        // 先处理右子树，再处理左子树（因为栈是后进先出）
        if (node->right) {
            push(s, node->right, 0);
        }
        if (node->left) {
            push(s, node->left, 0);
        }
    }
    free(s->data);
    free(s);
}

中序遍历 (Inorder Traversal - 左-根-右)

思路：

（图片来源网络，侵删）

创建一个空栈。
从根节点开始,沿着左子树一直向下遍历，将沿途的节点全部入栈（状态为0）。
当遇到一个没有左子树的节点（或者左子树已经访问完毕）时，从栈中弹出一个节点并访问它。
然后转向该节点的右子树,重复步骤2和3。
当栈为空且当前节点也为空时,遍历结束。

// 非递归中序遍历
void inorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    Stack* s = createStack(100);
    TreeNode* current = root;
    while (current != NULL || !isEmpty(s)) {
        // 1. 沿着左子树一直向左，将节点入栈
        while (current != NULL) {
            push(s, current, 0);
            current = current->left;
        }
        // 2. 当current为NULL时，说明已经到达最左端，从栈中弹出节点
        StackNode topNode = pop(s);
        TreeNode* node = topNode.treeNode;
        printf("%d ", node->val);
        // 3. 转向右子树
        current = node->right;
    }
    free(s->data);
    free(s);
}

后序遍历 (Postorder Traversal - 左-右-根)

后序遍历的非递归实现是三种遍历中最复杂的,因为它需要知道一个节点的左右子树是否已经被访问过，我们使用之前定义的 StackNode 结构中的 flag 字段来辅助判断。

思路：

创建一个空栈,并将根节点入栈（状态为0）。
当栈不为空时,循环执行以下操作： a. 查看栈顶元素。 b. 如果栈顶节点的 flag 为 0（表示左子树未访问）： i. 将 flag 设为 1。 ii. 如果有左子树，将左子节点入栈（状态为0），并继续循环。 iii. 如果没有左子树，则直接访问该节点（打印值），并将其出栈。（因为左右都没有，可以直接访问） c. 如果栈顶节点的 flag 为 1（表示左子树已访问，右子树未访问）： i. 将 flag 设为 2。 ii. 如果有右子树，将右子节点入栈（状态为0），并继续循环。 iii. 如果没有右子树，则直接访问该节点（打印值），并将其出栈。（因为右子树为空，可以访问根节点了） d. 如果栈顶节点的 flag 为 2（表示左右子树都已访问）： i. 直接访问该节点（打印值），并将其出栈。

// 非递归后序遍历
void postorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    Stack* s = createStack(100);
    push(s, root, 0); // 根节点入栈，状态为0
    while (!isEmpty(s)) {
        StackNode current = peek(s); // 只查看，不弹出
        if (current.flag == 0) {
            // 状态0：左子树未访问
            current.flag = 1;
            if (current.treeNode->left) {
                push(s, current.treeNode->left, 0);
            }
        } else if (current.flag == 1) {
            // 状态1：左子树已访问，右子树未访问
            current.flag = 2;
            if (current.treeNode->right) {
                push(s, current.treeNode->right, 0);
            }
        } else { // current.flag == 2
            // 状态2：左右子树都已访问，可以访问根节点了
            current = pop(s);
            printf("%d ", current.treeNode->val);
        }
    }
    free(s->data);
    free(s);
}

完整示例与测试

下面是一个完整的 C 语言程序，包含了所有定义和遍历函数，并有一个 main 函数来测试。

#include <stdio.h>
#include <stdlib.h>
// ... (将上面所有的代码，包括 TreeNode, StackNode, Stack 的定义，
// 以及 createNode, createStack, isEmpty, push, pop, peek 函数都放在这里) ...
// 非递归前序遍历
void preorderTraversal(TreeNode* root) {
    if (root == NULL) return;
    Stack* s = createStack(100);
    push(s, root, 0);
    while (!isEmpty(s)) {
        StackNode current = pop(s);
        printf("%d ", current.treeNode->val);
        if (current.treeNode->right) push(s, current.treeNode->right, 0);
        if (current.treeNode->left) push(s, current.treeNode->left, 0);
    }
    free(s->data);
    free(s);
}
// 非递归中序遍历
void inorderTraversal(TreeNode* root) {
    if (root == NULL) return;
    Stack* s = createStack(100);
    TreeNode* current = root;
    while (current != NULL || !isEmpty(s)) {
        while (current != NULL) {
            push(s, current, 0);
            current = current->left;
        }
        StackNode topNode = pop(s);
        printf("%d ", topNode.treeNode->val);
        current = topNode.treeNode->right;
    }
    free(s->data);
    free(s);
}
// 非递归后序遍历
void postorderTraversal(TreeNode* root) {
    if (root == NULL) return;
    Stack* s = createStack(100);
    push(s, root, 0);
    while (!isEmpty(s)) {
        StackNode current = peek(s);
        if (current.flag == 0) {
            current.flag = 1;
            if (current.treeNode->left) push(s, current.treeNode->left, 0);
        } else if (current.flag == 1) {
            current.flag = 2;
            if (current.treeNode->right) push(s, current.treeNode->right, 0);
        } else {
            current = pop(s);
            printf("%d ", current.treeNode->val);
        }
    }
    free(s->data);
    free(s);
}
// 主函数：测试
int main() {
    /*
     * 构建如下二叉树:
     *       1
     *      / \
     *     2   3
     *    / \   \
     *   4   5   6
     */
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->right = createNode(6);
    printf("Preorder Traversal: ");
    preorderTraversal(root); // 预期输出: 1 2 4 5 3 6
    printf("\n");
    printf("Inorder Traversal: ");
    inorderTraversal(root); // 预期输出: 4 2 5 1 3 6
    printf("\n");
    printf("Postorder Traversal: ");
    postorderTraversal(root); // 预期输出: 4 5 2 6 3 1
    printf("\n");
    // 释放内存 (简单示例，实际应用中需要更完整的释放逻辑)
    free(root->left->right);
    free(root->left->left);
    free(root->right->right);
    free(root->left);
    free(root->right);
    free(root);
    return 0;
}

遍历方式	核心思想	栈中存储内容	访问时机
前序	根-左-右	节点指针	节点被弹出时立即访问
中序	左-根-右	节点指针	节点从栈中弹出时访问（即其左子树为空时）
后序	左-右-根	节点指针 + 访问状态	节点的左右子树都被访问后（即状态为2时）访问

非递归遍历虽然代码比递归版本稍长,但它避免了递归可能带来的栈溢出问题，并且在某些应用场景（如需要中断和恢复遍历过程）中更具灵活性。

二叉树非递归遍历C语言如何实现？

准备工作：二叉树节点和栈的定义

前序遍历 (Preorder Traversal - 根-左-右)

中序遍历 (Inorder Traversal - 左-根-右)

后序遍历 (Postorder Traversal - 左-右-根)

完整示例与测试

相关文章

目录[+]