Morris
/*Morris遍历树:
*一；如果一个结点有左子树会到达此节点两次(第二次到达结点的时候左子树的所有结点都遍历完成),第一次遍历左子树最后
* 节点为nullptr，第二次遍历指向他自己
*二：否则到达一次(第一次到来和第二次到来一起 )
*当前节点cur
*1.如果cur没有左子树，cur向右移动:cur=cur->right
*2.如果cur有左结点，找左子树最右的结点记为mostRight
* 1>如果mostRight的右指针为nullptr，让其指向cur，cur向左移动:cur=cur->left
* 2>如果mostRight指向cur，让其指向nullptr，cur向右移动
*/
#include <iostream>
#include <algorithm>
#include <iterator>
#include <list>
using namespace std; typedef struct Tree
{
int value;
Tree *left,*right;
Tree()
{
value=;
left=right=nullptr;
}
}Tree;
void create_tree(Tree **root)
{
int n;
cin>>n;
if(n==)
*root=nullptr;
else
{
*root=new Tree();//*root中的内容就是地址
(*root)->value=n;
(*root)->left=nullptr;
(*root)->right=nullptr;
create_tree(&((*root)->left));
create_tree(&((*root)->right));
}
}
class Morris
{
public:
void morris_in(Tree *const root);//O(1)的空间复杂度遍历方法
void morris_pre(Tree *const root);
void morris_back(Tree *const root);
private:
void print_edge(Tree *const cur);
};
//先序中序只是选择时机的差别
void Morris::morris_pre(Tree *const root)
{
if(root==nullptr)
return; Tree *cur=root;
Tree *mostRight=nullptr;
while(cur!=nullptr)//当前节点不为nullptr继续遍历
{
mostRight=cur->left;
if(mostRight!=nullptr)//第二种情况：有左结点
{
//找当前节点左子树的最右结点
while(mostRight->right!=nullptr&&mostRight->right!=cur)
mostRight=mostRight->right; //<1>如果不指向当前节点(也就是指向nullptr,即第一次到来),就让它指向当前节点
if(mostRight->right!=cur)
{
mostRight->right=cur;
cout<<cur->value<<" ";
cur=cur->left;
continue;
}
else//<2>如果指向当前节点(也即第二次到来)把值置为nullptr
mostRight->right=nullptr;
}
else//一个结点没有左子树，第一次到来和第二次到来一起
cout<<cur->value<<" ";
//第一种情况：没有左结点向右走
cur=cur->right;
}
cout<<endl;
} //中序打印：如果一个节点有左子树，把左子树都处理完再打印自己
void Morris::morris_in(Tree *const root)
{
if(root==nullptr)
return; Tree *cur=root;
Tree *mostRight=nullptr;
while(cur!=nullptr)
{
mostRight=cur->left;
if(mostRight!=nullptr)
{
while(mostRight->right!=nullptr&&mostRight->right!=cur)
mostRight=mostRight->right; if(mostRight->right!=cur)
{
mostRight->right=cur;
cur=cur->left;
continue;
}
else
mostRight->right=nullptr;
}
//把打印时机放在最后一次来到此节点(如果结点没左子树第一次和第二次同时到来)
cout<<cur->value<<" "; //此节点要向右走，也就是左子树都处理完
cur=cur->right;
}
cout<<endl;
} //把打印时机放在第二次(该结点必须两次来到)来到该结点的时候,只关注能两次到来该节点的结点
//第二次到来时逆序打印左子树的右边界,打印完成之后在整个函数退出之前单独打印整个数的右边界
void Morris::morris_back(Tree *const root)
{
if(root==nullptr)
return; Tree *cur=root;
Tree *mostRight=nullptr;
while(cur!=nullptr)
{
mostRight=cur->left;
if(mostRight!=nullptr)//有左子树
{
while(mostRight->right!=nullptr&&mostRight->right!=cur)
mostRight=mostRight->right; if(mostRight->right!=cur)
{
mostRight->right=cur;
cur=cur->left;
continue;
}
else//第二次来到此节点
{
mostRight->right=nullptr;
print_edge(cur->left);
}
}
cur=cur->right;
}
print_edge(root);
cout<<endl;
}
void Morris::print_edge(Tree *const cur)
{
Tree *t=cur;
list<Tree *> list;
while(t!=nullptr)
{
list.push_back(t);
t=t->right;
}
list.reverse();
for(auto it=list.begin();it!=list.end();++it)
cout<<(*it)->value<<" ";
}
int main()
{
Tree *root=nullptr;
create_tree(&root); Morris ms;
ms.morris_pre(root); ms.morris_in(root); ms.morris_back(root);
return ;
}