自作二分木で四苦八苦しております。

とりあえず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;
                }
            }
        }