思路： 这次使用非递归法来遍历 中序遍历：左根右， ①所以在找到最左边的结点之前，我们一直找的是根左根左根左……直到我们找到最左边的子节点（假设其父节点是p） ②则这个时候应该一层一层的回找相关的右结点，这个时候就把当前结点转到p->right，继续进行①操作，直到找到最右边的结点
PS：中序遍历的顺序是左根右，但是我们这个地方借助栈操作，栈的特点是先进后出，所以先将根结点压入栈中再把左孩子结点压入栈中，这样出栈的时候刚好是先左后根
具体操作： （假设初始的时候根节点不为空，并申请一个栈Stack，这里用数组来代替，数组下标初始为-1） ①将根节点p放入栈中，然后判断其左孩子是否存在，存在则执行②，否则执行③；
②p->left存在，则p=p->left并将其放入栈中，执行①操作；
③此时p->left为空，所以，p需要倒退一步，这个时候，p的父节点就是Stack最后一个元素，p == Stack[top]，同时打印（或保存）p，然后从栈中剔除这个元素，再然后让p=p->right，执行①操作；
④如果仅仅上述三步则绝对不行，因为如果存在某结点的左子树存在而右子树不存在的情况，则遍历到这个右子树的时候程序就会终止，所以需要对①添加额外的限制条件，即(top!=-1 || p!=NULL)，也就是判断终止的标志是Stack为空，且结点已经遍历完了（假设p为该树的最右边的结点，则最后一次循环的时候p=p->right，此时p==NULL，且这个时候Stack中的元素已经全部完成打印/保存）
（最好动手画画图）
#include<iostream> #include<cstdlib> #include<vector> #include<stack> using namespace std; typedef struct TreeNode { int val; TreeNode *left; TreeNode *right; } TreeNode,*SearchTree; SearchTree MakeEmpty(SearchTree T) { if(T!=NULL) { MakeEmpty(T->left); MakeEmpty(T->right); free(T); } T = NULL; return T; } SearchTree Insert(int val,SearchTree T) { if(T==NULL) { T = (SearchTree)malloc(sizeof(TreeNode)); if(T==NULL) { printf("MALLOC ERROR\n"); exit(1); } T->val = val; T->left = T->right = NULL; } else { if(T->val>val) T->left = Insert(val,T->left); else if(T->val<val) T->right = Insert(val,T->right); } return T; } void InOrderTraversal(SearchTree T) { if(T==NULL) return ; InOrderTraversal(T->left); printf("%d ",T->val); InOrderTraversal(T->right); } class Solution { public: vector<int> inorderTraversal(TreeNode* root) { TreeNode* Stack[100]; int top = -1; vector<int> v; if(root!=NULL) { TreeNode *p = root; /** 中序遍历的顺序是根左右，所以只有p为树的最右结点 且p->right==NULL、栈为空的时候才算是遍历结束 */ while(top!=-1 || p!=NULL) { /** 这个循环是不断的寻找左子树根节点 如果左子树仍然存在左孩子，就继续向左寻找 */ while(p!=NULL) { Stack[++top] = p; p = p->left; } /** 如果出现跳出上面的while循环了，则说明这棵树 最左边的结点已经遍历完了，此时栈中的元素应该是 根左根左根左……，那么下面的if判断就是来进行遍历相关 的右子树 */ if(top!=-1) { p = Stack[top]; v.push_back(Stack[top--]->val); p = p->right; } } } return v; } }; int main() { Solution s; vector<int> v; SearchTree T = NULL; T = Insert(1,T); T = Insert(2,T); T = Insert(3,T); T = Insert(0,T); InOrderTraversal(T); cout<<endl; v = s.inorderTraversal(T); cout<<endl; vector<int>::iterator it; for(it = v.begin();it!=v.end();it++) { cout<<*it<<" "; } return 0; }