【数据结构】二叉树非递归前中后序遍历详解

二叉树的遍历是二叉树操作的基础核心递归遍历实现简单但存在栈溢出风险在处理深度较大的二叉树时非递归遍历凭借手动维护栈的方式更具稳定性。本文将详细讲解二叉树前序、中序、后序的非递归遍历实现思路结合 C 语言代码完整实现帮助大家理解非递归遍历的核心逻辑。一、二叉树基础准备1.1 二叉树节点结构定义首先定义二叉树的节点结构体包含数据域和左右孩子指针同时定义栈结构用于非递归遍历的节点暂存栈的最大容量通过宏定义MAXSIZE设置。#include stdio.h #include stdlib.h #define MAXSIZE 100 typedef char ElemType; // 二叉树节点结构体 typedef struct TreeNode { ElemType data; // 节点数据字符型 struct TreeNode *lchild; // 左孩子指针 struct TreeNode *rchild; // 右孩子指针 } TreeNode; typedef TreeNode* BiTree; // 栈结构体用于非递归遍历手动维护节点 typedef struct { BiTree data[MAXSIZE]; int top; // 栈顶指针初始为-1表示空栈 } Stack;1.2 二叉树的构建本文所有遍历均基于前序遍历序列构建二叉树序列中用#表示空节点示例序列为ABDH#K###E##CFI###G#J##。构建逻辑为递归读取序列字符非#则创建节点依次递归构建左子树和右子树#则置为空节点。char str[] ABDH#K###E##CFI###G#J##; int idx 0; // 全局索引用于遍历构建序列 // 前序构建二叉树 void createTree(BiTree *T) { ElemType ch str[idx]; if (ch #) { *T NULL; // 空节点 } else { *T (BiTree)malloc(sizeof(TreeNode)); (*T)-data ch; createTree((*T)-lchild); // 先构建左子树 createTree((*T)-rchild); // 后构建右子树 } }1.3 栈的基本操作非递归遍历的核心是手动操作栈实现栈的初始化、判空、入栈、出栈基础功能为后续遍历提供支撑// 初始化栈 void initStack(Stack *s) { s-top -1; } // 判断栈是否为空 int isEmpty(Stack *s) { return s-top -1; } // 入栈成功返回1栈满返回0 int push(Stack *s, BiTree p) { if (s-top MAXSIZE - 1) return 0; s-data[(s-top)] p; return 1; } // 出栈成功返回1栈空返回0p接收出栈节点 int pop(Stack *s, BiTree *p) { if (isEmpty(s)) return 0; *p s-data[(s-top)--]; return 1; }二、非递归前序遍历2.1 遍历规则前序遍历的核心规则是根节点 → 左子树 → 右子树即先访问当前根节点再依次遍历左、右子树。2.2 非递归实现思路若二叉树为空直接返回初始化栈将根节点压入栈中循环处理栈直到栈空弹出栈顶节点立即访问该节点根节点处理先将右孩子压入栈再将左孩子压入栈栈是后进先出保证左孩子先出栈被访问循环结束完成前序遍历。2.3 完整代码实现// 非递归前序遍历 void preOrderNonRecursive(BiTree T) { if (T NULL) return; Stack s; initStack(s); push(s, T); // 根节点入栈 while (!isEmpty(s)) { BiTree p; pop(s, p); // 弹出栈顶节点 printf(%c , p-data); // 访问根节点 // 先压右后压左保证左子树先遍历 if (p-rchild) { push(s, p-rchild); } if (p-lchild) { push(s, p-lchild); } } }2.4 遍历结果基于示例序列构建的二叉树前序非递归遍历结果为A B D H K E C F I G J。三、非递归中序遍历3.1 遍历规则中序遍历的核心规则是左子树 → 根节点 → 右子树即先遍历左子树至最底层再访问根节点最后遍历右子树。3.2 非递归实现思路中序遍历无法像前序那样直接入栈根节点需要先遍历左子树核心思路为初始化栈定义节点指针p指向根节点循环处理条件为p不为空 或 栈不为空若p不为空将p压入栈p指向其左孩子一直向左走遍历左子树若p为空弹出栈顶节点访问该节点左子树遍历完成处理根节点然后p指向其右孩子遍历右子树循环结束完成中序遍历。3.3 完整代码实现// 非递归中序遍历 void inOrderNonRecursive(BiTree T) { Stack s; initStack(s); BiTree p T; while (p ! NULL || !isEmpty(s)) { // 遍历左子树依次入栈 while (p ! NULL) { push(s, p); p p-lchild; } // 左子树遍历完成处理根节点和右子树 if (!isEmpty(s)) { pop(s, p); printf(%c , p-data); // 访问根节点 p p-rchild; // 遍历右子树 } } }3.4 遍历结果基于示例序列构建的二叉树中序非递归遍历结果为H K D B E A I F C G J。四、非递归后序遍历4.1 遍历规则后序遍历的核心规则是左子树 → 右子树 → 根节点是三种遍历中最复杂的因为根节点需要在左右子树都遍历完成后才能访问本文采用双栈法实现逻辑清晰易理解。4.2 双栈法实现思路利用两个栈s1主栈和s2辅助栈通过反转遍历顺序实现后序核心思路若二叉树为空直接返回初始化两个栈将根节点压入s1循环处理s1直到s1为空弹出s1栈顶节点将其压入s2辅助栈暂存先将左孩子压入s1再将右孩子压入s1使s1弹出顺序为根→右→左s2存储顺序为左→右→根的反序循环处理s2依次弹出节点并访问即为左→右→根的后序遍历结果。4.3 完整代码实现// 非递归后序遍历双栈法 void postOrderNonRecursive(BiTree T) { if (T NULL) return; Stack s1, s2; initStack(s1); initStack(s2); push(s1, T); BiTree p; // 主栈s1处理节点按根→右→左压入辅助栈s2 while (!isEmpty(s1)) { pop(s1, p); push(s2, p); // 先压左后压右保证s1弹出右→左 if (p-lchild) { push(s1, p-lchild); } if (p-rchild) { push(s1, p-rchild); } } // 弹出s2得到后序遍历结果 while (!isEmpty(s2)) { pop(s2, p); printf(%c , p-data); } }4.4 遍历结果基于示例序列构建的二叉树后序非递归遍历结果为K H D E B I F J G C A。五、主函数测试将二叉树构建和三种非递归遍历整合到主函数直接运行即可输出遍历结果int main(int argc, char const *argv[]) { BiTree T; createTree(T); // 构建二叉树 printf(非递归前序遍历); preOrderNonRecursive(T); printf(\n非递归中序遍历); inOrderNonRecursive(T); printf(\n非递归后序遍历); postOrderNonRecursive(T); printf(\n); return 0; }完整代码如下#include stdio.h #include stdlib.h // 栈最大容量根据二叉树大小调整 #define MAXSIZE 100 // 定义二叉树节点的数据类型这里用字符型方便演示 typedef char ElemType; // 1. 二叉树节点结构体定义 typedef struct TreeNode { ElemType data; // 节点数据域 struct TreeNode *lchild; // 左孩子指针 struct TreeNode *rchild; // 右孩子指针 } TreeNode; // 给二叉树指针起别名简化代码 typedef TreeNode* BiTree; // 2. 栈结构体定义用于非递归遍历 typedef struct { BiTree data[MAXSIZE]; // 栈存储二叉树节点指针 int top; // 栈顶指针-1表示空栈 } Stack; // 3. 栈的基础操作函数 // 初始化栈 void initStack(Stack *s) { s-top -1; } // 判断栈是否为空空返回1非空返回0 int isEmpty(Stack *s) { return s-top -1; } // 入栈操作将节点p压入栈s int push(Stack *s, BiTree p) { // 栈满判断 if (s-top MAXSIZE - 1) return 0; // 栈顶指针1存入节点 s-data[(s-top)] p; return 1; } // 出栈操作将栈顶节点弹出存入p int pop(Stack *s, BiTree *p) { // 栈空判断 if (isEmpty(s)) return 0; // 取出栈顶节点栈顶指针-1 *p s-data[(s-top)--]; return 1; } // 4. 二叉树创建前序遍历序列创建#表示空节点 // 测试用二叉树序列ABDH#K###E##CFI###G#J## char str[] ABDH#K###E##CFI###G#J##; int idx 0; // 全局索引遍历序列字符串 // 前序递归创建二叉树 void createTree(BiTree *T) { // 读取当前字符 ElemType ch str[idx]; // #代表空节点 if (ch #) { *T NULL; } else { // 分配节点内存 *T (BiTree)malloc(sizeof(TreeNode)); // 赋值节点数据 (*T)-data ch; // 递归创建左子树 createTree((*T)-lchild); // 递归创建右子树 createTree((*T)-rchild); } } // 5. 非递归前序遍历 // 规则根 - 左 - 右 void preOrderNonRecursive(BiTree T) { // 二叉树为空直接返回 if (T NULL) return; Stack s; // 初始化栈 initStack(s); // 根节点先入栈 push(s, T); // 栈不为空循环遍历 while (!isEmpty(s)) { BiTree p; // 弹出栈顶节点 pop(s, p); // 【访问节点】前序先访问根 printf(%c , p-data); // 栈是后进先出所以先压右孩子再压左孩子 // 保证出栈时左孩子先被访问 if (p-rchild) { push(s, p-rchild); } if (p-lchild) { push(s, p-lchild); } } } // 6. 非递归中序遍历 // 规则左 - 根 - 右 void inOrderNonRecursive(BiTree T) { Stack s; initStack(s); // 遍历指针p初始指向根节点 BiTree p T; // 循环条件p不为空 或 栈不为空 while (p ! NULL || !isEmpty(s)) { // 1. 一直向左走把所有左节点入栈直到左节点为空 while (p ! NULL) { push(s, p); p p-lchild; } // 2. 左节点为空弹出栈顶根节点并访问 if (!isEmpty(s)) { pop(s, p); // 【访问节点】中序左走完访问根 printf(%c , p-data); // 3. 访问右子树 p p-rchild; } } } // 7. 非递归后序遍历双栈法最易理解 // 规则左 - 右 - 根 // 双栈法思路s1存节点s2存逆序后序序列最后弹出s2即为后序 void postOrderNonRecursive(BiTree T) { if (T NULL) return; Stack s1, s2; initStack(s1); initStack(s2); // 根节点入s1 push(s1, T); BiTree p; // 处理s1将节点按 根-右-左 压入s2 while (!isEmpty(s1)) { pop(s1, p); push(s2, p); // 先压左后压右保证s1弹出顺序为 根-右-左 if (p-lchild) { push(s1, p-lchild); } if (p-rchild) { push(s1, p-rchild); } } // 弹出s2所有节点就是后序遍历结果 while (!isEmpty(s2)) { pop(s2, p); // 【访问节点】后序左、右都走完访问根 printf(%c , p-data); } } // 8. 主函数测试三种遍历 int main() { BiTree T; // 1. 创建二叉树 createTree(T); // 2. 测试非递归前序遍历 printf(非递归前序遍历结果); preOrderNonRecursive(T); printf(\n); // 3. 测试非递归中序遍历 printf(非递归中序遍历结果); inOrderNonRecursive(T); printf(\n); // 4. 测试非递归后序遍历 printf(非递归后序遍历结果); postOrderNonRecursive(T); printf(\n); return 0; }运行截图如下六、核心总结前序遍历根先出利用栈后进先出先压右、后压左实现根→左→右的访问顺序中序遍历先遍历左子树至最底层左空出根访问再处理右子树循环条件需同时判断节点和栈后序遍历双栈法通过两个栈反转顺序s1 实现根→右→左s2 暂存后弹出即为左→右→根非递归遍历的核心是手动模拟递归的栈帧过程通过栈暂存未处理的节点控制遍历顺序。三种非递归遍历的时间复杂度均为O(n)每个节点入栈、出栈、访问各一次空间复杂度为O(n)最坏情况二叉树退化为链表栈存储所有节点在实际开发中非递归遍历更适合处理深度较大的二叉树避免递归的栈溢出问题。