对于二叉树的三种遍历方式（先序、中序、后序），用递归和非递归（栈）的方式实现，对于后序遍历用队列实现。
四种遍历方式的概念
二叉树
先序遍历（中->左->右）：1->2->4->5->3->6->7
中序遍历（左->中->右）：4->2->5->1->6->3->7
后序遍历（左->右->中）：4->5->2->6->7->3->1
层序遍历（从上到下，从左到右）：1->2->3->4->5->6->7
树结构体
struct TreeNode{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x): val(x), left(NULL), right(NULL) {}
};
先序遍历
递归
递归调用先序函数，将输出值的语句放在遍历子节点之前。
void PreOrder(TreeNode *root){
if (root){
cout<<root->val<<endl; //对节点值的操作
PreOrder(root->left);
PreOrder(root->right);
}
return;
}
非递归1
用栈来模拟递归函数的调用，先将根节点压栈，当栈不空的时候，访问并弹出栈顶元素，再将其右节点、左节点按顺序压栈，这样栈的输出就变成左节点、右节点，重复访问并弹出栈顶元素，直到栈空。栈中存储的都是将要遍历的节点，已遍历的节点都被弹出。
void PreOrder1(TreeNode *root){
if (!root) return;
stack<TreeNode*> s;
s.push(root);
TreeNode *temp;
while(!s.empty()){
temp=s.top();
cout<<temp->val<<endl; //对节点值的操作
s.pop();
if (temp->right) { //将右节点压栈
s.push(temp->right);
}
if (temp->left) { //将左节点压栈
s.push(temp->left);
}
}
return;
}
非递归2
主要不同点在于，在将每个节点压栈的同时输出节点的值，这样向左搜索到最左节点，最左节点出栈，栈顶元素为其父节点，再将右节点压栈。这样能确保每个根节点都被访问过，只需要再访问它的左右节点。
void PreOrder2(TreeNode *root){
if (!root) return;
stack<TreeNode*> s;
TreeNode *temp=root;
while(temp || !s.empty()){
if (temp){ //节点存在则压栈，同时操作其值，再遍历其左节点（往左搜索）
s.push(temp);
cout<<temp<<endl;
temp=temp->left;
}else{ //节点不存在（找到最左），则弹出栈顶元素，遍历它的右节点
temp=s.top();
s.pop();
temp=temp->right;
}
}
}
中序遍历
递归
递归调用中序函数，将输出值的语句放在遍历左右节点之间。
void InOrder(TreeNode *root){
if (root){
InOrder(root->left);
cout<<root->val<<endl; //对节点值的操作
InOrder(root->right);
}
return;
}
非递归
同样用栈来做，先将左节点都找到并入栈，找到最左节点后，操作它的值，弹出栈顶元素，再遍历它根节点的右节点。这样能确保每个节点的左节点都被访问过，只需要再访问它的根节点和右兄弟节点就好了。和先序遍历相比，只是把输出节点值的语句放到了出栈的时候。
void InOrder(TreeNode *root){
if (!root) return;
stack<TreeNode*> s;
TreeNode *temp=root;
while(temp || !s.empty()){
if (temp){ //节点存在则压栈，再遍历其左节点（往左搜索）
s.push(temp);
temp=temp->left;
}else{ //节点不存在则（找到最左），操作根节点的值，再遍历其右节点（
temp=s.top();
cout<<temp->val<<endl;
s.pop();
temp=temp->right;
}
}
return;
}
后序遍历
递归
递归调用后序函数，将输出值的语句放在遍历左右节点之后。
void PostOrder(TreeNode *root){
if (root){
PostOrder(root->left);
PostOrder(root->right);
cout<<root->val<<endl; //对节点值的操作
}
return;
}
非递归1
从根节点开始，先入栈，再将其右节点、左节点入栈，注意入栈后就将其对应节点的指针设为空，相当于标记为左右节点都遍历过，只需要最后遍历这个根节点。这样出栈的顺序就变成左右中，而且把每个节点的父子关系都拆散了！
void PostOrder1 (TreeNode *root){
if (!root) return;
stack<TreeNode*> s;
s.push(root);
TreeNode *temp;
while(!s.empty()){
temp=s.top();
if (!temp->left && !temp->right){ //栈顶元素是“叶子节点”，说明左右都访问过，或者说明它是真的叶子节点
cout<<temp->val;
s.pop();
}else{ //如果节点的左右有节点，就把它们入栈，再拆散关系
if (temp->right){
s.push(temp->right);
temp->right=nullptr;
}
if (temp->left){
s.push(temp->left);
temp->left=nullptr;
}
}
}
return;
}
非递归2
这种方法比较取巧，后序是左右中，先得到中右左的遍历结果，再将这个结果翻转，就得到了正确的后序。代码在先序非递归遍历上做了小的改动，把左右节点的顺序调换一下。
void PostOrder2(TreeNode *root){
if (!root) return;
vector<int> res;
stack<TreeNode*> s;
TreeNode *temp=root;
while(temp || !s.empty()){
if (temp){
s.push(temp);
res.push_back(temp->val);
temp=temp->right;
}else{
temp=s.top();
s.pop();
temp=temp->left;
}
}
reverse(res.begin(), res.end()); //将中右左变成左右中
}
层序遍历
不需要分层，连续输出
层序遍历需要借助队列来实现，当不需要区别遍历到的节点属于那个层时，用一个队列操作就够了。先把根节点入队，当队中有元素时，反复进行一个操作：将队前元素输出，将其左右节点分别入队（如果左右节点不为空的话），直到清空队列。
void LevelOrder1(TreeNode *root){
if (!root) return;
queue<TreeNode*> q;
q.push(root);
TreeNode *temp;
while(!q.empty()){
temp=q.front();
cout<<temp->val<<endl; //操作这个数
q.pop();
if (temp->left){
q.push(temp->left);
}
if (temp->right){
q.push(temp->right);
}
}
return;
}
需要按层的顺序输出
按层的顺序输出时，可以用两个队列来实现，分别存储当前层和下一层的所有节点。先将根节点存入第一个队列，再将第一个队列中元素全部取出，取出的同时把它们的左右节点放入第二个队列；再去处理第二个队列，同样将所有元素取出，它们的左右节点放入第一个队列，这样来回倒，直到最后一层遍历结束，两个队全部为空时退出循环。
void LevelOrder2(TreeNode* root){
if (!root) return;
queue<TreeNode*> q1, q2;
vector<vector<int>> res; //用二维数组保存遍历结果
TreeNode *temp;
vector<int> levelout; //层遍历数组
q1.push(root);
while(!q1.empty() || !q2.empty()){
while(!q1.empty()){ //把当前层所有节点取出来，把它们的左右节点放到另一个队列里
temp=q1.front();
levelout.push_back(temp->val);
q1.pop();
if (temp->left) q2.push(temp->left);
if (temp->right) q2.push(temp->right);
}
res.push_back(levelout);
levelout.clear(); //当前层遍历结束，清空层遍历数组
while(!q2.empty()){ //一样的操作，
temp=q2.front();
res[level].push_back(temp->val);
q2.pop();
if (temp->left) q1.push(temp->left);
if (temp->right) q1.push(temp->right);
}
res.push_back(levelout);
levelout.clear(); //当前层遍历结束，清空层遍历数组
}
return;
}
上述遍历也可以用一个队列实现，在将根节点入队之后，再将一个空指针nullptr也入队，标志着一层遍历的结束。当出队元素为空指针时，说明当前层已经访问结束，也就说明当前层的左右节点都入队完毕，也就是下一层的节点全部在队里，这时再将一个空指针入队，标记下一层结束的位置。
void LevelOrder3(TreeNode* root){
if (!root) return;
queue<TreeNode*> q;
vector<vector<int>> res; //用二维数组保存遍历结果
TreeNode *temp;
vector<int> levelout; //层遍历数组
q1.push(root);
q1.push(nullptr); //第一层结束
while(!q1.empty()){
temp=q.front();
q.pop();
if (temp){
levelout.push_back(temp->val);
if (temp->left) q2.push(temp->left);
if (temp->right) q2.push(temp->right);
}else{
if (!q.empty()){
q.push(nullptr); //下一层入队结束
}
res.push_back(levelout);
levelout.clear(); //当前层遍历结束，清空层遍历数组
}
}
return;
}
参考
1、https://www.jianshu.com/p/9f148caf2535
2、https://blog.csdn.net/weixin_40457801/article/details/90349144
网友评论