先序遍历：
/* 先序遍历的非递归思想：借助一个栈来保存遍历的序列，以此来访问右子节点 */ #include <stack> struct TreeNode{ int val; TreeNode * left; TreeNode * right; }; void preorderTravelsal(TreeNode* root){ if(!root)return;//边界条件判断，如果树空 stack<TreeNode*>sta; while(root || !sta.empty()){ while(root){ cout<<root->val<<endl; sta.push(root); root=root->left; } if(!sta.empty()){ root=sta.top(); sta.pop(); root=root->right; } } }
12345678910111213141516171819202122232425中序遍历
/* 思想中序遍历的非递归形式和先序遍历基本一样，只是输出的顺序不一样，中序遍历先输出左节点，在输出根，最后输出右节点； */ #include <stack> struct TreeNode{ int val; TreeNode* left; TreeNode* right; }; void inorderTravelsal(TreeNode* root){ if(!root)return; stack<TreeNode*>sta; while(root || !sta.empty()){ while(root){ sta.push(root); root=root->left; } if(!sta.empty()){ root=sta.top(); cout<<root->val<<endl; sta.pop(); root=root->right; } } }
12345678910111213141516171819202122232425后序遍历
/* 思路：后序遍历稍微复杂点，它必须记录是否结点的左右子节点都访问完，才能访问根节点 */ #include <stack> struct TreeNode{ int val; TreeNode* left; TreeNode* right; }; void postorderTravelsal(TreeNode* root){ if(!root)return; stack<TreeNode*>sta; TreeNode curr=root;//当前节点 TreeNode pre=NULL;//刚刚访问的节点 while(curr||!sta.empty()){ while(curr){ sta.push(curr) curr=curr->left; } curr=sta.top();//栈首元素，最左元素 //只有当最左节点的右子节点为空或者访问过了，才能访问该节点 if(curr->right==NULL || curr->right==pre){ cout<<curr->val<<endl; pre=curr; sta.pop(); curr=NULL; } else curr=curr->right; } }
123456789101112131415161718192021222324252627282930
