这是一个关于数据结构二叉树的遍历问题

Question

二叉树非递归中序遍历，思路是啥呢？
我想敲出代码来，但是想不通这种分叉的东西怎么写，也想不透怎么把根节点的位置顺序体现出来

Answer 1

拿 https://blog.csdn.net/qq_44556821/article/details/96423326 这个程序改了下。

#include <stack>
#include <iostream>
using namespace std;

class TreeNode {
private:
    char name_;
public:
    int State;//状态值
    TreeNode* leftNode;
    TreeNode* rightNode;    
public:
    TreeNode(char a):name_(a) { 
        State = 0;
        leftNode = NULL;
        rightNode = NULL;
    }
    char getName() {
        return name_;
    }
};

void MiddlePush(TreeNode& TreeTop);

int main(){
    //初始化树
    TreeNode node1('A');
    TreeNode node2('B');
    TreeNode node3('C');
    TreeNode node4('D');
    TreeNode node5('E');
    TreeNode node6('F');
    TreeNode node7('G');
    TreeNode node8('H');
    TreeNode node9('I');
    node1.leftNode = &node2;
    node1.rightNode = &node3;
    node2.leftNode = &node4;
    node2.rightNode = &node5;
    node3.rightNode = &node6;
    node4.leftNode = &node7;
    node4.rightNode = &node8;
    node6.leftNode = &node9;
    MiddlePush(node1);
}

void MiddlePush(TreeNode& TreeTop) {
    stack<TreeNode> STN;
    STN.push(TreeTop);
    while (STN.size()) {
        TreeNode Top = STN.top();   
        if (!Top.State) {       
            STN.pop();
            Top.State = 1;      
            STN.push(Top);
            if (Top.rightNode) {
                STN.pop();          
                STN.push(*Top.rightNode);   
                STN.push(Top);
            }
            if (Top.leftNode) {         
                STN.push(*Top.leftNode);
            }
        }
        else {
            cout << Top.getName() << ends;
            STN.pop();
        }   
    }
    cout << endl;
}