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

0 下载量 166 浏览量 更新于2024-08-03 收藏 1KB MD 举报
"二叉树的非递归遍历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语言和栈实现二叉树的非递归后序遍历。这种实现方式可以有效处理大型二叉树,避免了递归可能导致的栈溢出问题,同时也体现了深度优先搜索的基本思想。