//再帰の除去
#include <iostream>
#include <iterator>
#include <stack>
#include <boost/shared_ptr.hpp>
using namespace std;
template <typename T> struct tree;
template <typename T>
struct tree{
T d;
boost::shared_ptr<tree<T> > l;
boost::shared_ptr<tree<T> > r;
explicit tree(T in=0):d(in),l(),r(){}
};
typedef tree<char> PT;
typedef boost::shared_ptr<PT > ptree;
//元の関数(木構造をpreorderで走査して表示する)
void show_dfs_raw(ptree& p){
cout << p->d;
if(p->l)show_dfs_raw(p->l); //LからR
if(p->r)show_dfs_raw(p->r);
}
//末尾再帰呼び出しをループに展開(引数の破壊的変更になるため、引数を参照でなくした)
void show_dfs_raw1(ptree p){
l:
cout << p->d;
if(p->l)show_dfs_raw(p->l); //LからR
if(p->r){
p=p->r;
goto l;
}
}
stack<ptree> stc; //エミュレート用のスタックを準備した
//中央の呼び出しをgotoに変換
void show_dfs_raw2(ptree p){
l:
cout << p->d;
if(p->l){
stc.push(p); //関数呼び出しをエミュレート。関数呼び出し前の環境(引数)を保存
p=p->l;goto l;
}
r:
if(p->r){
p=p->r;
goto l;
}
if(!stc.empty()){ //保存したものがあれば飛ぶ
p=stc.top();
stc.pop();
goto r;
}
}
//ラベルrを消す
void show_dfs_raw3(ptree p){
l:
cout << p->d;
if(p->l){
stc.push(p); //関数呼び出しをエミュレート。関数呼び出し前の環境(引数)を保存
p=p->l;goto l;
}
if(!stc.empty()){
p=stc.top();
stc.pop();
if(p->r){
p=p->r;
goto l;
}
}
}
//ラベルlを消す
void show_dfs_raw4(ptree p){
//???
}
//スタックを使ってさらに簡略化
void show_dfs_raw5(ptree p){
stc.push(p);
while(!stc.empty()){
p=stc.top();
stc.pop();
cout << p->d;
if(p->r){
stc.push(p->r);
}
if(p->l){
stc.push(p->l);
}
}
}
#define QQ(a,ch) ptree a(new PT(ch));
//入力データの木構造のイメージ図
// a
// b c
// d e f g
int main(){
QQ(a,'a');
QQ(b,'b');
QQ(c,'c');
QQ(d,'d');
QQ(e,'e');
QQ(f,'f');
QQ(g,'g');
a->l=b;
a->r=c;
b->l=d;
b->r=e;
c->l=f;
c->r=g;
cout << "dfsr:";show_dfs_raw(a);cout << endl;
cout << "dfs1:";show_dfs_raw1(a);cout << endl;
while(!stc.empty()){stc.pop();}
cout << "dfs2:";show_dfs_raw2(a);cout << endl;
while(!stc.empty()){stc.pop();}
cout << "dfs3:";show_dfs_raw3(a);cout << endl;
while(!stc.empty()){stc.pop();}
// cout << "dfs4:";show_dfs_raw4(a);cout << endl;
while(!stc.empty()){stc.pop();}
cout << "dfs5:";show_dfs_raw5(a);cout << endl;
return 0;
}