二叉树非递归遍历

// BinaryTree.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include<stack>
using namespace std;
#define MY_FALSE 0
#define MY_TRUE  1
//二叉树结点结构体
 struct BinaryNode {
    char ch;
    struct BinaryNode*lchild;
    struct BinaryNode*rchild;
};

void Recursion(BinaryNode * root) 
{
    if (root == NULL)
        return;
    //先序

    printf("%c", root->ch);
    Recursion(root->lchild);//递归到叶子结点的下一个结点 结束后才执行下一条递归语句
    //vector.push_back(root->ch);//如果有个数组就可以存储遍历的结果
    //右子树
    Recursion(root->rchild);
}

//创建一个自定义栈结点，就是栈中存放的数据类型
struct BiTreeStackNode {
    BinaryNode* node;
    int flag;
};

//结点产生
BiTreeStackNode* createBiTreeStackNode(BinaryNode* node, int flag)
{
    BiTreeStackNode *newnode = new BiTreeStackNode;
    newnode->node = node;
    newnode->flag = flag;
    return newnode;
}

void NonRecursion(BinaryNode * root)
{
    //初始化一个栈
    stack<BiTreeStackNode*> my_stack;
    //先把根节点压入栈
    my_stack.push(createBiTreeStackNode(root, MY_FALSE));

    //开始遍历
    while (!my_stack.empty())
    {
        //先把栈顶元素弹出来
        BiTreeStackNode* Stacknode = my_stack.top();
        my_stack.pop();
        if (Stacknode->node == NULL)//结点为空
        {
            continue;
        }
        if (Stacknode->flag == MY_TRUE)
        {
            cout<<Stacknode->node->ch;
        }
        else
        {

            my_stack.push(createBiTreeStackNode(Stacknode->node->rchild, MY_FALSE));
            my_stack.push(createBiTreeStackNode(Stacknode->node->lchild, MY_FALSE));
            my_stack.push(createBiTreeStackNode(Stacknode->node,MY_TRUE));

        }
    }
}



void createBinaryTree()
{
    //创建节点
    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);
    cout << endl;
    Recursion(&node1);

}
int main()
{
    createBinaryTree();
    system("pause");
    return 0;
    std::cout << "Hello World!\n";
}