通过队列实现，从上往下一层一层去遍历，A ----> B、C ----> D、E、F ----> G、H
1.入队 2.打印数据
A入队，打印：A 队列中的元素：A 打印结果：A
A出队
判断 A->LChild != NULL，B != NULL，B入队 打印：B 队列中的元素：B 打印结果：A、B
判断 A->RChild != NULL，C != NULL，C入队 打印：C 队列中的元素：B、C 打印结果：A、B、C
B出队
判断 B->LChild != NULL D != NULL，D入队 打印：D 队列中的元素：C、D 打印结果：A、B、C、D
判断 B->RChild != NULL E != NULL，E入队 打印：E 队列中的元素：C、D、E 打印结果：A、B、C、D、E
C出队 、、、把C的左子树和右子树入队，打印C的左子树和右子树
D出队 、、、把D的左子树和右子树入队，打印D的左子树和右子树
当队列为 NULL，整个二叉树就打印出来了
测试代码：数据结构 --- c语言递归法遍历二叉树_考拉爱睡觉鸭~的博客-CSDN博客
//要遍历的树void layerOrder(LPTREE root) {LPTREE pmove = root; //定义一个移动的节点==根节点//准备一个队列--->存的是一个节点<->指针 定义的是一个指针，用数组充当队列的容器LPTREE queue[1024];int front = 0; //队头标记int tail = 0; //队尾标记queue[tail++] = pmove; //第一个节点入队 队尾做变化printf("%c", pmove->data); //打印第一个节点的数据while (front != tail) //队列不为空出队{pmove = queue[front++];//出队 队头做变化 出队后把左、右子树入队if (pmove->LChild != NULL) //左边!=NULL 左子树入队{queue[tail++] = pmove->LChild; //队尾做变化 1.入队 2.打印数据printf("%c", pmove->LChild->data);}if (pmove->RChild != NULL) //右边!=NULL 右子树入队{queue[tail++] = pmove->RChild;printf("%c", pmove->RChild->data);}}}int main() {//创建二叉树--->无序的树--->创建节点LPTREE A = createNode('A'); //A节点LPTREE B = createNode('B');LPTREE C = createNode('C');LPTREE D = createNode('D');LPTREE E = createNode('E');LPTREE F = createNode('F');LPTREE G = createNode('G');LPTREE H = createNode('H'); //一个个连接insertNode(A, B, C); //A下面插入B、CinsertNode(B, D, E); //B下面插入D、EinsertNode(E, G, NULL); insertNode(C, NULL, F);insertNode(F, H, NULL); //打印结果 layerOrder(A); //ABCDEFGHprintf("n"); return 0;}
前序、中序、后序的非递归法遍历
用栈实现回退效果
对于3种遍历方式的介绍：数据结构 --- c语言二叉树基础(无序二叉树)_考拉爱睡觉鸭~的博客-CSDN博客
定义一个移动的指针指向第一个位置
入栈顺序：ABD，出栈顺序：DBA
前序遍历 根左右//非递归法先序void preOrderByStack(LPTREE root) { if (root == NULL) //为空无法打印return;LPTREE pmove = root; //定义移动的指针==根节点//栈LPTREE stack[1024]; //准备栈存储节点的位置<->指针int stackTop = -1; //栈顶标记while (stackTop != -1 || pmove) //pmove!=NULL{//先走左边,边打印边入栈while (pmove != NULL) {printf("%c", pmove->data); //打印数据stack[++stackTop] = pmove; //入栈 栈顶标记从-1开始 ++栈顶标记pmove = pmove->LChild; //入栈后一直往左边走,直到走到空的位置}//退出循环，到达空的位置，出栈找右边if (stackTop != -1) //栈为空无法出栈{pmove = stack[stackTop--];pmove = pmove->RChild; //找 出栈后节点的右边}}}
中序遍历 左根右刚开始只做入栈操作，不做数据打印，先走到树的最左边在出栈的位置打印，先走完再做打印
//非递归法中序void midOrderByStack(LPTREE root) {if (root == NULL)return;LPTREE pmove = root;//栈LPTREE stack[1024];int stackTop = -1;while (pmove != NULL || stackTop != -1) {while (pmove) //pmove!=NULL{stack[++stackTop] = pmove; //入栈pmove = pmove->LChild; //pmove一直往左边走 走到最左边} //退出循环，到达空的位置if (stackTop != -1) //栈不为空出栈{pmove = stack[stackTop--];printf("%c", pmove->data); //打印数据pmove = pmove->RChild; //找 出栈后节点的右边}}}
后序遍历 左右根
按左根右的方式存在重复打印的现象，打印节点的前提是出栈节点的右边没有节点或者已经被遍历完了，才能打印当前节点，如果有右边就要走到最右边
第1步不需要重复，重复做2、3步即可
//非递归法后序void lastOrderByStack(LPTREE root) {if (root == NULL)return;LPTREE pmove = root;//栈LPTREE stack[1024];int stackTop = -1;//1.先走到最左边while (pmove) {stack[++stackTop] = pmove; //pmove!=NULL一直走到最左边 持续入栈pmove = pmove->LChild;}LPTREE lastvisited = NULL; //记录被访问的节点<->访问标记while (stackTop != -1) //栈不为空做出栈操作{pmove = stack[stackTop--]; //出栈 //右边没有节点或者被访问了一次-->走过一次了在做回退if (pmove->RChild == NULL || pmove->RChild == lastvisited) {printf("%c", pmove->data);lastvisited = pmove; //改变上一次访问的标记==当前遍历的节点}else //有右边就要走右边{stack[++stackTop] = pmove; //当前节点入栈pmove = pmove->RChild; //往当前节点右边走while (pmove) {stack[++stackTop] = pmove; //右子树的左边走到底pmove = pmove->LChild; }}}}
测试代码int main() {//创建二叉树--->无序的树--->创建节点LPTREE A = createNode('A'); //A节点LPTREE B = createNode('B');LPTREE C = createNode('C');LPTREE D = createNode('D');LPTREE E = createNode('E');LPTREE F = createNode('F');LPTREE G = createNode('G');LPTREE H = createNode('H'); //一个个连接insertNode(A, B, C); //A下面插入B、CinsertNode(B, D, E); //B下面插入D、EinsertNode(E, G, NULL); insertNode(C, NULL, F);insertNode(F, H, NULL); preOrderByStack(A); //ABDEGCFH printf("n"); midOrderByStack(A); //DBGEACHF printf("n"); lastOrderByStack(A); //DGEBHFCA printf("n"); }