二叉树的所有遍历（递归，非递归，层序，morris)

1.二叉树的递归遍历每个节点会遍历三次（只是打印时机不同，就分为了前，中，后 序遍历

例如：

1.递归遍历

代码如下

void PrintPre(TreeNode* root)
{if (root == nullptr)return;cout <<root->val << " ";PrintPre(root->left);PrintPre(root->right);
}
void PrintMid(TreeNode* root)
{if (root == nullptr)return;PrintMid(root->left);cout << root->val << " ";PrintMid(root->right);
}
void PrintBehaind(TreeNode* root)
{if (root == nullptr)return;PrintBehaind(root->left);PrintBehaind(root->right);cout << root->val << " ";
}

这里递归不在啰嗦。

2，非递归（用栈实现）

前序

void StackPre(TreeNode* root)  //前序
{if (root == nullptr)return;stack<TreeNode*> st;st.push(root);while (!st.empty()){TreeNode* tmp = st.top();cout << tmp->val << " ";st.pop();if (tmp->right != nullptr)   //先压右孩子st.push(tmp->right);if (tmp->left != nullptr)    //在压左孩子st.push(tmp->left);}
}

中序

void StackMid(TreeNode* root) //中序
{if (root == nullptr)return;stack<TreeNode*> st;while (!st.empty() || root != nullptr){while (root != nullptr){st.push(root);root = root->left;}root = st.top();cout << root->val << " ";st.pop();root = root->right;}
}

 后序

void StackBehind(TreeNode* root)
{if (root == nullptr)return;stack<TreeNode*> st, ret;st.push(root);while (!st.empty()){TreeNode* tmp = st.top();ret.push(tmp);st.pop();if (tmp->left)st.push(tmp->left);if (tmp->right)st.push(tmp->right);}while (!ret.empty()){cout << ret.top()->val << " ";ret.pop();}
}

3，层序遍历

层序

void LayerPrint(TreeNode* root)
{queue<TreeNode*> q;q.push(root);while (!q.empty()){TreeNode* tmp = q.front();cout << tmp->val << " ";q.pop();if (tmp->left != nullptr)q.push(tmp->left);if (tmp->right != nullptr)q.push(tmp->right);}
}

相信上面对大家都没有什么挑战，接下来我看一下Morris遍历

4.morris遍历

只要有左子树的节点都会遍历两次

void morris(TreeNode* root)
{TreeNode* cur = root;TreeNode* MostRight = nullptr;while (cur != nullptr){cout << cur->val << " ";MostRight = cur->left;if (MostRight != nullptr)    //这里是找左子树的最右节点{while (MostRight->right != nullptr && MostRight->right!= cur){MostRight = MostRight-> right;}if (MostRight->right == nullptr)   //下面的逻辑是判断是第一次找到的左节点的最有节点，还是第二次找到的左子树的最有节点{ MostRight->right = cur;cur = cur->left;continue;         //这是morris遍历的灵魂}else{MostRight->right = nullptr;}}cur = cur->right;}
}

morris改前序遍历，只要弄清楚morris的遍历方式，改前序和中序都很简单，前序是只出现一次的节点打印，出现两次的节点打印第一次

前序

void morris(TreeNode* root)
{TreeNode* cur = root;TreeNode* MostRight = nullptr;while (cur != nullptr){MostRight = cur->left;if (MostRight != nullptr){while (MostRight->right != nullptr && MostRight->right!= cur){MostRight = MostRight-> right;}if (MostRight->right == nullptr){cout << cur->val << " ";MostRight->right = cur;cur = cur->left;continue;}else{MostRight->right = nullptr;}}else{cout << cur->val <<" ";}cur = cur->right;}
}

中序

void morris(TreeNode* root)
{TreeNode* cur = root;TreeNode* MostRight = nullptr;while (cur != nullptr){MostRight = cur->left;if (MostRight != nullptr){while (MostRight->right != nullptr && MostRight->right!= cur){MostRight = MostRight-> right;}if (MostRight->right == nullptr){MostRight->right = cur;cur = cur->left;continue;}else{MostRight->right = nullptr;}}cout << cur->val <<" ";cur = cur->right;}
}

后序需要逆序打印前面的节点，又要把二叉树的有边界逆序，逆序操作后，在逆序回来，当然也可不去破坏原二叉树，可以用递归打印类似单链表的方式

void printEdge(TreeNode* head)  //逆序打印右边界
{if (head == nullptr) return;printEdge(head->_right);cout << head->_val << " ";
}
void morris(TreeNode* root)
{if (root == nullptr)return;TreeNode* cur = root;TreeNode* MostRight = nullptr;while (cur != nullptr){MostRight = cur->_left;if (MostRight != nullptr){while (MostRight->_right != nullptr && MostRight->_right != cur){MostRight = MostRight->_right;}if (MostRight->_right == nullptr){MostRight->_right = cur;cur = cur->_left;continue;}else{MostRight->_right = nullptr;printEdge(cur->_left);}}cur = cur->_right;}printEdge(root);
}