需要使用栈，算法如下：
1 若根节点为空，判断栈顶是否为空，非空出栈访问右子树。 为空则结束 向左走，如果左子树非空，则根节点入栈，访问左子树 如果左子树为空，打印，判断右子树2 右子树非空，访问右子树，重复1 （该步骤其实可以省略） 右子树为空，出栈，打印，访问根节点的右子树重复1
#include<iostream> #include<string> #include<stack> using namespace std; class TreeNode { public: TreeNode() { LChild = NULL; RChild = NULL; ch = '0'; } TreeNode(TreeNode * l, TreeNode * r, char c) { LChild = l; RChild = r; ch = c; } public: TreeNode *LChild; TreeNode *RChild; char ch; }; //2 树的中序非递归遍历 // 1一直向左走，找到中序遍历的起点 // 2如果有右子树，重复步骤1 // 3没有右子树，弹出栈顶元素 //******** void InOrder_no_re(TreeNode* root, stack<TreeNode*> &s) { TreeNode* tmp; //若根节点为空，判断栈顶是否为空，非空出栈打印后访问右子树。 为空则结束 if (root == NULL) { if (s.empty() == true) { return; } else { tmp = s.top(); s.pop(); cout << tmp->ch << " "; InOrder_no_re(tmp->RChild, s); } } //向左走，如果左子树非空，则根节点入栈，访问左子树 if (root->LChild != NULL) { s.push(root); InOrder_no_re(root->LChild, s); } // 如果左子树为空，打印，判断右子树 else { cout << root->ch << " "; // 右子树非空，访问右子树 if (root->RChild != NULL) { InOrder_no_re(root->RChild, s); } // 右子树为空，非空出栈，访问根节点的右子树 else { if (s.empty() == true) { return; } else { tmp = s.top(); s.pop(); cout << tmp->ch << " "; InOrder_no_re(tmp->RChild, s); } } } } int main() { TreeNode d(NULL, NULL, 'D'), e(NULL, NULL, 'E'), h(NULL, NULL, 'H'), c(&d, &e, 'C'), g(&h, NULL, 'G'), b(NULL, &c, 'B'), f(NULL, &g, 'F'), a(&b, &f, 'A'); //2 树的非递归中序遍历 BDCEAFHG stack<TreeNode*> s1; InOrder_no_re(&a, s1); system("pause"); }