自作二分木で四苦八苦しております。
とりあえずStackOverflowExceptionが怖いので、while()とスタックで表現できないかとやってたら、再帰関数の呼び出し位置も記憶しておくことが重要と認識。
とりまこんな方法でやってみた。
タプル便利やなー。
//行きがけ順
public void TraversePreOrder(Action<Node> action)
{
var stack = new Stack<(Node, bool, bool)>(100); //スタック
var node = Root; //まずはじめは根から
bool left = false; //左子ノードを通過したか
bool right = false; //右子ノードを通過したか
/*
//もし再帰で書いたらこうなるはず
public void func(Node n){
/*ノードの中身を見る*/ n.Action();
/*左子ノードへ行く*/ if(n.Left != null) { func(n.Left); }
/*右子ノードへ行く*/ if(n.Right != null) { func(n.Right); }
};
*/
//ブンブン回していく
while (node != null)
{
//左子ノードも右子ノードも通過してない
if(left == false && right == false)
{
//ノードの中身を見る
action(node);
}
//左子ノードへまいります
if (left == false && node.Left != null)
{
stack.Push((node, true, false)); //左子ノード通過フラグを立てておく
node = node.Left;
left = false; //ここらへんの初期化をわすれずに
right = false;
continue; //ここでいったん抜ける
}
//右子ノードへまいります
if (right == false && node.Right != null)
{
stack.Push((node, true, true)); //どっちも通過フラグ
node = node.Right;
left = false;
right = false;
continue;
}
if (stack.Count > 0)
{
(node, left, right) = stack.Pop(); //まだあんじゃん
}
else
{
node = null; //もうないです
}
}
}
//通りがけ順
public void TraverseInOrder(Action action)
{
var stack = new Stack<(Node, bool, bool)>(100);
var node = Root;
bool left = false;
bool right = false;
/*
public void func(Node n){
if(n.Left != null) { func(n.Left); }
n.Action();
if(n.Right != null) { func(n.Right); }
};
*/
while (node != null)
{
if (left == false && node.Left != null)
{
stack.Push((node, true, false));
node = node.Left;
left = false;
right = false;
continue;
}
//行きがけ順とちがって判定用フラグが減ってるのに注意
if (right == false)
{
action(node);
}
if (right == false && node.Right != null)
{
count++;
stack.Push((node, true, true));
node = node.Right;
left = false;
right = false;
continue;
}
if (stack.Count > 0)
{
(node, left, right) = stack.Pop();
}
else
{
node = null;
}
}
}
//帰りがけ順
public void TraversePostOrder(Action action)
{
var stack = new Stack<(Node, bool, bool)>(100);
var node = Root;
bool left = false;
bool right = false;
/*
public void func(Node n){
if(n.Left != null) { func(n.Left); }
if(n.Right != null) { func(n.Right); }
n.Action();
};
*/
while (node != null)
{
if (left == false && node.Left != null)
{
stack.Push((node, true, false));
node = node.Left;
left = false;
right = false;
continue;
}
if (right == false && node.Right != null)
{
count++;
stack.Push((node, true, true));
node = node.Right;
left = false;
right = false;
continue;
}
if (true)
{
action(node);
}
if (stack.Count > 0)
{
(node, left, right) = stack.Pop();
}
else
{
node = null;
}
}
}