花式遍历二叉树

左神介绍的遍历二叉树的花式方法

#include<iostream>
#include<stack>
#include<queue>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
/*
struct Command{
//
flag
false 遍历其子节点，
true 访问当前节点
bool flag;
TreeNode* node;
Command(bool flag, TreeNode* node) : flag(flag), node(node){}
};
void preOrder(TreeNode* root){
if(!root) return ;
stack<Command> sta;
sta.push(Command(false, root));
while(!sta.empty()){
Command com = sta.top();
sta.pop();
if(com.flag)
// 访问当前节点
cout << com.node->val << ' ';
else {
// 后序
if(com.node->right) sta.push(Command(fal***.node->right));
// 中序
if(com.node->left) sta.push(Command(fal***.node->left));
// 前序
sta.push(Command(true, com.node));
}
}
}
*/
void preOrder(TreeNode* root){
if(!root) return ;
//
false 遍历其子节点，
true 访问当前节点
stack<pair<bool, TreeNode*>> sta;
sta.push({false, root});
while(!sta.empty()){
pair<bool, TreeNode*> tem = sta.top();
sta.pop();
if(tem.first)
// 访问当前节点
cout << tem.second->val << ' ';
else {
// 后序 sta.push({true, tem.second});
if(tem.second->right) sta.push({false, tem.second->right});
// 中序 sta.push({true, tem.second});
if(tem.second->left) sta.push({false, tem.second->left});
// 前序
sta.push({true, tem.second});
}
}
}
/*
void preOrder(TreeNode* root){
if(!root) return ;
/*
// 递归版本， 简单
cout<<root->val<<' ';
preOrder(root->left);
preOrder(root->right);
/
stack<TreeNode*> sta;
TreeNode* cur = root;
while(cur || sta.size()){
// 访问当前节点，并压到栈里
if(cur){
sta.push(cur);
cout<<cur->val<<' ';
cur = cur->left;
}else{
// 当前为空时，弹出最后一个访问其右子树
cur = sta.top();
sta.pop();
cur = cur->right;
}
}
/*
// 先压右子树，后压左子树
stack<TreeNode*> sta;
sta.push(root);
while(sta.size()){
root = sta.top();
cout<<root->val<<' ';
sta.pop();
if(root->right) sta.push(root->right);
if(root->left) sta.push(root->left);
}
/
cout<<endl;
}
*/
void inOrder(TreeNode* root){
if(!root) return ;
/*
// 递归版本， 简单
inOrder(root->left);
cout<<root->val<<' ';
inOrder(root->right);
*/
/*
stack<TreeNode*> sta;
TreeNode* cur = root;
while(cur || sta.size()){
// 把当前节点以及其左子树并压到栈里
while(cur){
sta.push(cur);
cur = cur->left;
}
// 当前为空时，弹出最后一个访问，并访问其右子树
cur = sta.top();
cout<<cur->val<<' ';
sta.pop();
cur = cur->right;
}*/
// Morris遍历 中序
// 把为空的右指针尽量用上，降低空间复杂度
while(root){
if(root->left){
TreeNode* tem = root->left;
while(tem->right && tem->right != root)
tem = tem->right;
// 还没有加过链接时，加上链接，方便回溯
if(!tem->right){
tem->right = root;
root = root->left;
continue;
}
// 已经回溯过，删除链接，恢复树的原状，并访问根节点
tem->right = NULL;
}
// 访问当前节点
cout<<root->val<<' ';
root = root->right;
}
cout<<endl;
}
void postOrder(TreeNode* root){
if(!root) return ;
/*
// 递归版本， 简单
postOrder(root->left);
postOrder(root->right);
cout<<root->val<<' ';
*/
stack<TreeNode*> sta;
TreeNode* cur = root;
TreeNode* pre = NULL;
while(cur){
sta.push(cur);
cur = cur->left;
}
while(sta.size()){
cur = sta.top();
// 没有右子树，或者前一个访问的节点为其右子树
if( !cur->right || cur->right== pre){
cout<<cur->val<<' ';
pre = cur;
sta.pop();
}else{
cur = cur->right;
while(cur){
sta.push(cur);
cur = cur->left;
}
}
}
/*
// 两个栈， 采用前序的思想 根右左 然后经过另外一个栈，变成左右根
stack<TreeNode*> sta;
stack<TreeNode*> stb;
sta.push(root);
while(sta.size()){
root = sta.top();
stb.push(root);
sta.pop();
if(root->left) sta.push(root->left);
if(root->right) sta.push(root->right);
}
while(stb.size()){
cout<<stb.top()->val<<' ';
stb.pop();
}
*/
/*
// 左神，一个栈，然后判断
stack<TreeNode*> sta;
TreeNode* pre = NULL;
sta.push(root);
while(sta.size()){
root = sta.top();
if(root->left && root->left != pre && root->right != pre)
sta.push(root->left);
else if(root->right && root->right != pre)
sta.push(root->right);
else {
cout<<root->val<<' ';
pre = root;
sta.pop();
}
}*/
/*
// 先加右子树再加左子树的骚操作
stack<TreeNode*> sta;
TreeNode* pre = NULL;
sta.push(root);
while(sta.size()){
root = sta.top();
if( (!root->left && !root->right) || (pre && root->left == pre || root->right == pre)){
cout<<root->val<<' ';
pre = root;
sta.pop();
}else{
if(root->right) sta.push(root->right);
if(root->left) sta.push(root->left);
}
}
*/
cout<<endl;
}
void levelOrder(TreeNode* root){
if(!root) return ;
queue<TreeNode*> que;
que.push(root);
// 层次遍历，最简单
while(que.size()){
int len = que.size();
while(len--){
TreeNode* cur = que.front();
que.pop();
cout<<cur->val<<' ';
if(cur->left)que.push(cur->left);
if(cur->right)que.push(cur->right);
}
}
cout<<endl;
}
int main(){
TreeNode* root = new TreeNode(5);
root->left = new TreeNode(3);
root->right = new TreeNode(6);
root->left->right = new TreeNode(7);
root->right->left = new TreeNode(10);
root->right->right = new TreeNode(13);
preOrder(root);
return 0;
}

最后

以上就是英勇唇彩为你收集整理的花式遍历二叉树的全部内容，希望文章能够帮你解决花式遍历二叉树所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。