二分探索木の巡回について

Question

前提・実現したいこと

C#で二分探索木の中にある素数を全部アウトプットするプログラムを書きたいですが、左の葉まで行ったら根に戻って右の葉に向かわせる考え方でやろうとしていますが、左部分木の右の葉と右部分木の左の葉に行き届いてないことに気づきました。どうすれば左部分木の右の葉に移動できるかのところで躓いています。

該当のソースコード

        public Boolean checkPrime(int c)
        {
            Boolean a = true;
            if (c <= 1) //0,1 is not prime
            {
                a = false;
            }

            double num = Math.Sqrt(c); //use root to reduce the step 
            for (int i = 2; i <= num; i++)
            {
                if (c % i == 0)
                {
                    a = false;
                    break;
                }
            }
            return a;
        }//End of checkPrime

        public void outputPrimeNum(Node root)
        {
            Node temp = root;

            if (temp == null)
            {
                return;
            }


            while (temp != null)
            {
                if (checkPrime(temp.num))
                {
                    Console.WriteLine(temp.num + " ");
                    temp = temp.left;
                }
                else
                {
                    if(temp.left != null)
                    {
                        temp = temp.left;
                    }
                    else if(temp.left == null)
                    {
                        temp = root;
                        break;
                    }
                }
            }

            while (temp != null)
            {
                if (checkPrime(temp.num))
                {
                    Console.WriteLine(temp.num + " ");
                    temp = temp.right;
                }
                else
                {
                    if (temp.right != null)
                    {
                        temp = temp.right;
                    }
                    else if (temp.right == null && temp != null)
                    {
                        temp = temp.right;
                    }
                    else
                    {
                        break;
                    }
                }
            }

        }//End of outputPrimeNum

すごい初心者の質問で申し訳無いですが、何かアドバイスをいただけるとうれしいです。

Comments

[Zuishin]

探索のしかた

まず root をスタックあるいはキューに入れます。
ここではスタックとします。

①
スタックから一つ取り出し、そのノードを処理します。
そして子ノードをすべてスタックに入れます。
①に戻り、スタックが空になるまで繰り返します。

[fana]

まずは質問タイトルにある単語をそのまま用いて
「二分探索木 巡回」とかで検索してみた方が早いのでは．

[fruitpunch]

Zuishinさん
いいアドバイスありがとうございます。
キューでトライしてみます！

[Zuishin]

キューを使う場合、幅優先探索になります。スタックを使うと、深さ優先探索になります。
目的によって使い分けてください。

[fruitpunch]

Zuishinさん
なるほど！
DFSの場合はスタック　
わかりやすい説明ありがとうございます！

Answer 1

再帰による巡回:

class Node {
    private int  value_;

    public Node(int value) { value_ = value; }
    public Node Left { get; set; }
    public Node Right { get; set; }
    public int  Value { get { return value_; } }
}

class foo {

    // Nodeを辿る
    static void walk(Node node) {
        if ( node != null ) {
            walk(node.Left);  // 左の子Nodeを辿る
            System.Console.WriteLine(node.Value); // Valueをプリント
            walk(node.Right); // 右の子Nodeを辿る
        }
    }

    // おためし
    static void Main() {
        Node root = new Node(4);
        root.Left = new Node(2);
        root.Left.Left = new Node(1);
        root.Left.Right = new Node(3);
        root.Right = new Node(6);
        root.Right.Left = new Node(5);
        root.Right.Right = new Node(7);

        walk(root);
    }

}

Comments

[fruitpunch]

回答ありがとうございます！！
再帰処理を用いたDFSでできるだけ深い方へ処理
をすすめていき，葉に到達したら手前に戻ることを繰り
返すということですね！
いい勉強になりました！
ありがとうございます！！

Answer 2

紙にその二分木の図を書いてみて、あなたがおっしゃるような探索をする場合にどう言う手順で行うのか、を考えてみましょう
その手順をきっちり言語化し、それをコードに落とし込んでいきましょう

Comments

[fruitpunch]

アドバイスありがとうございます。
葉から節に戻るところがうまくコードでかけなくて躓いていましたが、キューを使ってもう一度やってみます。
ありがとうございます。