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

前提・実現したいこと

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

該当のソースコード

C#
1        public Boolean checkPrime(int c)
2        {
3            Boolean a = true;
4            if (c <= 1) //0,1 is not prime
5            {
6                a = false;
7            }
8
9            double num = Math.Sqrt(c); //use root to reduce the step 
10            for (int i = 2; i <= num; i++)
11            {
12                if (c % i == 0)
13                {
14                    a = false;
15                    break;
16                }
17            }
18            return a;
19        }//End of checkPrime
20
21        public void outputPrimeNum(Node root)
22        {
23            Node temp = root;
24
25            if (temp == null)
26            {
27                return;
28            }
29
30
31            while (temp != null)
32            {
33                if (checkPrime(temp.num))
34                {
35                    Console.WriteLine(temp.num + " ");
36                    temp = temp.left;
37                }
38                else
39                {
40                    if(temp.left != null)
41                    {
42                        temp = temp.left;
43                    }
44                    else if(temp.left == null)
45                    {
46                        temp = root;
47                        break;
48                    }
49                }
50            }
51
52            while (temp != null)
53            {
54                if (checkPrime(temp.num))
55                {
56                    Console.WriteLine(temp.num + " ");
57                    temp = temp.right;
58                }
59                else
60                {
61                    if (temp.right != null)
62                    {
63                        temp = temp.right;
64                    }
65                    else if (temp.right == null && temp != null)
66                    {
67                        temp = temp.right;
68                    }
69                    else
70                    {
71                        break;
72                    }
73                }
74            }
75
76        }//End of outputPrimeNum

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

Zuishin

2021/10/21 00:59

探索のしかたまず root をスタックあるいはキューに入れます。ここではスタックとします。 ① スタックから一つ取り出し、そのノードを処理します。そして子ノードをすべてスタックに入れます。 ①に戻り、スタックが空になるまで繰り返します。

fana

2021/10/21 01:08

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

fruitpunch

2021/10/21 01:46

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

Zuishin

2021/10/21 01:50

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

fruitpunch

2021/10/21 01:54

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

行動規範の内容に同意します

回答2件

ベストアンサー

再帰による巡回:

C#
1class Node {
2    private int  value_;
3
4    public Node(int value) { value_ = value; }
5    public Node Left { get; set; }
6    public Node Right { get; set; }
7    public int  Value { get { return value_; } }
8}
9
10class foo {
11
12    // Nodeを辿る
13    static void walk(Node node) {
14        if ( node != null ) {
15            walk(node.Left);  // 左の子Nodeを辿る
16            System.Console.WriteLine(node.Value); // Valueをプリント
17            walk(node.Right); // 右の子Nodeを辿る
18        }
19    }
20
21    // おためし
22    static void Main() {
23        Node root = new Node(4);
24        root.Left = new Node(2);
25        root.Left.Left = new Node(1);
26        root.Left.Right = new Node(3);
27        root.Right = new Node(6);
28        root.Right.Left = new Node(5);
29        root.Right.Right = new Node(7);
30
31        walk(root);
32    }
33
34}