二叉树的非递归遍历（详解）

二叉树非递归遍历原理
使用先序遍历的方式完成该二叉树的非递归遍历
通过添加现有项目的方式将原来编写好的栈文件导入项目中

目前项目存在三个文件一个头文件，两个cpp文件：

项目头文件的代码截图：QueueStorage.h
项目头文件的代码：QueueStorage.h

#ifndefLINKSTACK_H#defineLINKSTACK_H#include<stdio.h>#include<stdlib.h>// 链式栈的节点typedefstructLINKNODE{structLINKNODE* next;}LinkNode;// 链式栈typedefstructLINKSTACK{
    LinkNode head;int size;}LinkStack;// 初始化函数
LinkStack*Init_LinkStack();// 入栈voidPush_LinkStack(LinkStack* stack, LinkNode* data);// 出栈voidPop_LinkStack(LinkStack* stack);// 返回栈顶元素
LinkNode*TopLinkStack(LinkStack* stack);// 返回栈元素的个数intSize_LinkStack(LinkStack* stack);// 清空栈voidClear_LinkStack(LinkStack* stack);// 销毁栈voidFreeSpace_LinkStack(LinkStack* stack);#endif

项目cpp文件代码截图：QueueStorage.cpp该文件主要用于栈功能的实现
栈逻辑文件具体代码：QueueStorage.cpp

#define_CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<stdlib.h>#include<math.h>#include<iostream>#include<string.h>#include"QueueStorage.h"// 初始化函数
LinkStack*Init_LinkStack(){
    LinkStack* stack =(LinkStack*)malloc(sizeof(LinkStack));
    stack->head.next =NULL;
    stack->size =0;return stack;};// 入栈voidPush_LinkStack(LinkStack* stack, LinkNode* data){if(stack ==NULL){return;}if(data ==NULL){return;}// 入栈
    data->next = stack->head.next;
    stack->head.next = data;
    stack->size++;};// 出栈voidPop_LinkStack(LinkStack* stack){if(stack ==NULL){return;}if(stack->size ==0){return;}// 第一个有效节点
    LinkNode* pNext = stack->head.next;
    stack->head.next = pNext->next;
    stack->size--;};// 返回栈顶元素
LinkNode*TopLinkStack(LinkStack* stack){if(stack ==NULL){returnNULL;}if(stack->size ==0){returnNULL;}// 返回栈顶元素return stack->head.next;};// 返回栈元素的个数intSize_LinkStack(LinkStack* stack){if(stack ==NULL){return-1;}return stack->size;};// 清空栈voidClear_LinkStack(LinkStack* stack){if(stack ==NULL){return;}// 清空栈
    stack->head.next =NULL;
    stack->size =0;};// 销毁栈voidFreeSpace_LinkStack(LinkStack* stack){if(stack ==NULL){return;}free(stack);};

二叉树cpp文件截图：BinaryTree.cpp

二叉树cpp文件逻辑代码实现先序遍历：BinaryTree.cpp

#define_CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<stdlib.h>#include<math.h>#include<iostream>#include<string.h>#include"QueueStorage.h"#defineMY_FALSE0#defineMY_TRUE1// 二叉树的节点typedefstructBINARYNODE{// 数据char ch;// 二叉树的左节点structBINARYNODE* lchild;// 二叉树的右节点structBINARYNODE* rchild;}BinaryNode;//二叉树的非递归遍历typedefstructBITREESTACKNODE{
    LinkNode* node;
    BinaryNode* root;int flag;}BiTreeStackNode;// 创建栈中的节点
BiTreeStackNode*CreateBiTreeStackNode(BinaryNode* node,int flag){
    BiTreeStackNode* newnode =(BiTreeStackNode*)malloc(sizeof(BiTreeStackNode));
    newnode->root = node;
    newnode->flag = flag;return newnode;}voidNonRecursion(BinaryNode* root){// 创建栈
    LinkStack* stack =Init_LinkStack();// 将根节点放入栈中Push_LinkStack(stack,(LinkNode*)CreateBiTreeStackNode(root, MY_FALSE));// 判断栈是否为空while(Size_LinkStack(stack)>0){// 先弹出栈顶元素
        BiTreeStackNode* node =(BiTreeStackNode*)TopLinkStack(stack);Pop_LinkStack(stack);// 判断弹出的节点是否为空if(node->root ==NULL){continue;}if(node->flag == MY_TRUE){printf("%c", node->root->ch);}else{// 当前节点的右节点入栈Push_LinkStack(stack,(LinkNode*)CreateBiTreeStackNode(node->root->rchild,MY_FALSE));// 当前节点的左节点入栈Push_LinkStack(stack,(LinkNode*)CreateBiTreeStackNode(node->root->lchild, MY_FALSE));// 当前节点入栈
            node->flag = MY_TRUE;Push_LinkStack(stack,(LinkNode*)node);}}}// 二叉树的递归遍历voidRecursion(BinaryNode* root){if(root ==NULL){return;}printf("%c",root->ch);// 递归遍历Recursion(root->lchild);Recursion(root->rchild);}voidCresteBinaryTree(){// 将节点创建出来
    BinaryNode node1 ={'A',NULL,NULL};
    BinaryNode node2 ={'B',NULL,NULL};
    BinaryNode node3 ={'C',NULL,NULL};
    BinaryNode node4 ={'D',NULL,NULL};
    BinaryNode node5 ={'E',NULL,NULL};
    BinaryNode node6 ={'F',NULL,NULL};
    BinaryNode node7 ={'G',NULL,NULL};
    BinaryNode node8 ={'H',NULL,NULL};// 建立节点之间的关系
    node1.lchild =&node2;
    node1.rchild =&node6;
    node2.rchild =&node3;
    node3.lchild =&node4;
    node3.rchild =&node5;
    node6.rchild =&node7;
    node7.lchild =&node8;//二叉树的非递归打印NonRecursion(&node1);// 二叉树的递归遍历printf("\n");// Recursion(&node1);}intmain(){CresteBinaryTree();system("pause");return0;}

项目运行结果展示