二叉树非递归遍历：栈实现DFS

"二叉树的非递归遍历C语言实现" 在计算机科学中，二叉树是一种数据结构，每个节点最多有两个子节点，通常分为左子节点和右子节点。二叉树的遍历是指按照特定顺序访问树中的每一个节点。常见的遍历方法有前序遍历、中序遍历和后序遍历。本资源主要讨论了非递归方式实现二叉树的深度优先搜索（DFS）遍历，特别地，是采用栈来辅助进行的后序遍历。 二叉树的非递归遍历避免了递归带来的调用栈空间问题，适用于处理大规模或深度较大的二叉树。以下是代码实现的关键部分： 1. **二叉树节点定义**： 在C语言中，我们首先定义一个结构体`TreeNode`来表示二叉树的节点，包含整型值`val`以及指向左右子节点的指针`left`和`right`。 ```c typedef struct TreeNode { int val; struct TreeNode* left; struct TreeNode* right; } TreeNode; ``` 2. **栈操作**： 为了实现非递归遍历，我们需要借助栈的数据结构。这里假设`Stack`已经实现了基本的栈操作，如`createStack()`用于创建栈，`isEmpty()`检查栈是否为空，以及`stackPush()`和`stackPop()`分别用于入栈和出栈。 3. **深度优先搜索（DFS）**： 深度优先搜索是一种遍历策略，先访问当前节点，然后尽可能深地探索其子树。在这个例子中，我们采用后序遍历，即左子树→右子树→根节点的顺序。`dfs`函数实现了这一逻辑： ```c void dfs(TreeNode* root) { if (root == NULL) { return; } Stack* stack = createStack(); stackPush(stack, root); while (!isEmpty(stack)) { TreeNode* node = stackPop(stack); printf("%d", node->val); // 访问根节点（后序遍历的最后一步） if (node->right) { stackPush(stack, node->right); // 先右子树 } if (node->left) { stackPush(stack, node->left); // 然后左子树 } } } ``` 4. **主程序**： 在`main`函数中，我们创建了一个简单的二叉树，并调用`dfs`函数进行遍历。这棵树的结构为： ``` 1 / \ 2 3 / \ 4 5 ``` 非递归的后序遍历会按照5, 4, 2, 3, 1的顺序打印节点值。 总结来说，这段代码展示了如何使用C语言和栈实现二叉树的非递归后序遍历。这种实现方式可以有效处理大型二叉树，避免了递归可能导致的栈溢出问题，同时也体现了深度优先搜索的基本思想。