Traversal
注意stack弹出的顺序决定是如何遍历
先序
思路
- 取二叉树根节点入栈
pop栈顶数据Top- 先入
Top右，再入Top左
重复2、3步骤，直到栈为空
实现
void PreOrderUnRecur(Node* root) { if(root != null) { stack<Node*> cons; cons.push(root); while(!cons.empty()) { Node* Top = cons.top(); cons.pop(); cout << Top->value << " "; if(Top->right) cons.push(Top->right); if(Top->left) cons.push(Top->left); } } }
后序
思路
使用两个栈 cons 、help
- 根节点入栈
cons pop数据Top到help- 先入
Top左，再入Top右，均入cons
重复步骤2、3，直到cons没有数据，依次拿出help中的数据
实现
void PostOrderUnRecur(Node* root) { if(root != null) { stack<Node*> cons; stack<Node*> help; cons.push(root); while(!cons.empty()) { Node* Top = cons.top(); cons.pop(); help.push(Top); if(Top->left) cons.push(Top->left); if(Top->right) cons.push(Top->right); } while(!help.empty()) { Node* val = help.top(); help.pop(); cont << val->value << " "; } } }
总结
栈入数据的顺序是和弹出时的顺序是相反的。
弹出的顺序即决定是先序遍历还是后续遍历。
先序遍历 -- -- 头左右 -- -- 要求入栈顺序：头右左
后序遍历 -- -- 左右头 -- -- 要求入栈顺序：头左右 -- -- 得到出栈顺序：头右左 -- -- help反转出栈顺序
中序
思路
首先根节点的所有左节点入栈
pop节点Top，把Top节点的右子树的左节点入栈
重复上面的步骤，直到栈为空
实现
void InOrderUnRecur(Node* root) { if(root != nullptr) { stack<Node*> cons; Node* cur = root; while(!cons.empty() || cur != nullptr) { if(cur == nullptr) { Node* Top = cons.top(); cons.pop(); cout << Top->value <<" "; cur = Top->right; } else { cons.push(cur); cur = cur->left; } } } }
总结
对于一个节点Node和它的左节点LNode、右节点RNode，出栈的顺序： LNode -> Node -> RNode，也可以说是处理这个节点的顺序
