二叉树中序遍历非递归

//二叉树中序遍历非递归算法

#include <iostream>
#include<stack>
using namespace std;
struct BinaryNode {
    int val;
    BinaryNode* lchild;
    BinaryNode* rchild;
};

void DFSmid(BinaryNode* root)
{
    //空树
    if (root == NULL)
        return;
    stack< BinaryNode*> s;
    while (root != NULL || !s.empty())
    {
        if(root != NULL)
        {
            s.push(root);
            root = root->lchild;
        }
        else
        {
            root = s.top();//弹出栈顶元素
            s.pop();
            cout << root->val << ' ';
            root = root->rchild;
        }
    }
}

void recursionPre(BinaryNode *root)
{
    if (root == NULL) return;
    recursionPre(root->lchild);
    cout << root->val;
    recursionPre(root->rchild);
}
void createBinaryTree()
{
    //创建节点
    BinaryNode node1 = { 1,NULL,NULL };
    BinaryNode node2 = { 2,NULL,NULL };
    BinaryNode node3 = { 3,NULL,NULL };
    BinaryNode node4 = { 4,NULL,NULL };
    BinaryNode node5 = { 5,NULL,NULL };
    BinaryNode node6 = { 6,NULL,NULL };
    BinaryNode node7 = { 7,NULL,NULL };
    //    BinaryNode node8 = { 'H',NULL,NULL };
        //建立结点关系
    node1.lchild = &node2;
    node1.rchild = &node3;
    node2.lchild = &node4;
    node2.rchild = &node5;
    node3.lchild = &node6;
    node3.rchild = &node7;

    recursionPre(&node1);
    cout << endl;

    DFSmid(&node1);


}
int main()
{
    createBinaryTree();
    system("pause");
    return 0;
}