C# と VB.NET の質問掲示板

　以下はC#で書いた二分木のクラスです。
　https://lets-csharp.com/binary-search-tree-cs/
を参考にしましたが、とりあえず挿入と表示だけです。

public class Node
{
    public Node(string key)
    {
        Key = key;
    }

    public string Key = null;
    public Node Left = null;
    public Node Right = null;
}

public class BinarySearchTree
{
    public Node Root
    {
        private set;
        get;
    }

    //挿入
    public void Insert(string value)
    {
        if (Root == null)
        {
            Root = new Node(value);
            return;
        }

        Node cur = Root;

        while (true)
        {
            int comparison = string.Compare(cur.Key, value);
            if (comparison == 0)
            {
                // 値が既に存在する場合、挿入せず終了
                MessageBox.Show($"値 '{value}' は既に存在します。", "エラー",
                       MessageBoxButtons.OK, MessageBoxIcon.Error);
                return;
            }
            else if (comparison > 0)
            {
                if (cur.Left == null) // 左部分木に移動
                {
                    cur.Left = new Node(value);
                    return;
                }
                cur = cur.Left;
            }
            else
            {
                if (cur.Right == null) // 右部分木に移動
                {
                    cur.Right = new Node(value);
                    return;
                }
                cur = cur.Right;
            }
        }
    }

    // 木を文字列として出力 ⇒ここを変更したい
    public override string ToString()
    {
        return ToString(Root, 0);
    }

    private string ToString(Node node, int depth)
    {
        if (node == null) return "";

        // 左部分木を再帰的に文字列化
        string left = ToString(node.Left, depth + 1);

        // 現在のノードを空白でインデント
        string current = new string(' ', depth * 4) + node.Key + Environment.NewLine;

        // 右部分木を再帰的に文字列化
        string right = ToString(node.Right, depth + 1);

        return right + current + left;
    }
}

ボタンで次のように実行する。
public partial class Form1 : Form
{
    BinarySearchTree bst = new BinarySearchTree();

    private void BtnTest_Click(object sender, EventArgs e)
    {
        var StrList = new List<string>();

        StrList.Add("Sayaka");
        StrList.Add("Kayoko");
        StrList.Add("Natsuko");
        StrList.Add("Miwako");
        StrList.Add("Ranko");
        StrList.Add("Yayoi");
        StrList.Add("Asuka");
        StrList.Add("Reika");
        StrList.Add("Chisato");
        StrList.Add("Wakana");
        foreach (string str in StrList)
            bst.Insert(str);
        // 出力用テキストボックスに表示
        TextBoxOut.Text = bst.ToString();
    }
}

　出力用テキストボックスに次のように表示されます。
    Yayoi
        Wakana
Sayaka
                Reika
            Ranko
        Natsuko
            Miwako
    Kayoko
            Chisato
        Asuka

　親子関係を明確にするために、各項目の行間を開け、罫線を使って次のように表示したい。
　string ToString() をどのように修正したらいいでしょうか？

      ┌Yayoi
      │  │     ← 項目間は1行明けるので '│' を追加
      │  └Wakana
      │
Sayaka┤
      │
      │                      ┌Reika
      │                      │
      │               ┌Ranko┘
      │               │
      │      ┌Natsuko┤
      │      │       │
      │      │       └Miwako
      │      │
      └Kayoko┤
              │
              └Asuka

　ChatGpt 先生に相談しながら以下のようなコードをいろいろ試しているのですが、うまくいきません。

public override string ToString()
{
    return ToString(Root, "", true);
}

private string ToString(Node node, string prefix, bool isLeft)
{
    if (node == null) return "";

    // 自身の文字列を構築
    var currentLine = prefix;
    if (!string.IsNullOrEmpty(prefix))
    {
        currentLine += isLeft ? "└" : "┌";
    }
    currentLine += node.Key + Environment.NewLine;

    // 左右の子を再帰的に文字列化
    string left = ToString(node.Left, prefix + (isLeft ? "    " : "│   "), true);
    string right = ToString(node.Right, prefix + (isLeft ? "    " : "│   "), false);

    return right + currentLine + left;
}

■No103462 (星は昴 さん) に返信

ひとまず…
Wakana の表示の部分は(２番目の表示部分)
       ┌Yayoi┐
       │     │
       │     └Wakana

と、ほかの右要素と同じ形にしたほうが良いでしょう。具体的には、
Ranko -> Reika の逆表現パターンですね。

kikuさんが提示している形もありますが、もっとすっきりと
コンソールの tree コマンドのような形のほうが楽かもしれません。

Sayaka
 ├Yayoi
 │ └Wakana
 └Kayoko
   ├Natsuko
   │ ├Ranko
   │ │ └Reika
   │ └Miwako
   └Asuka

表示が Form なので、思い切って別解。

ツリー状で見せたいのなら、ツリー表現を行うための
TreeView コントロールで表示するのはどうでしょうか？

コンソールでは表示できませんが、
開閉もできるので見た目の表示要素はかなり上がると思います。

・TreeView コントロール
https://learn.microsoft.com/ja-jp/dotnet/api/system.windows.forms.treeview?WT.mc_id=DT-MVP-32182&view=netframework-4.8

■No103468 (星は昴 さん) に返信
> ■No103465 (とっちゃん さん) に返信
> 　回答まことにありがとうございます。

ご要望通りできちゃいました。

        public override string ToString()
        {
            return ToString(Root, "");
        }

        private string ToString(Node node, string depth)
        {
            if (node == null) return "";

            //右部分木
            string right = ToString(node.Right, depth + "R");

            //右空行
            string rightspace = "";
            if(node.Right != null)
            {
                rightspace = SpaceIndent(depth + "R") + Environment.NewLine;
            }

            //現在ノード
            string current = Indent(depth) + node.Key + Environment.NewLine;

            //左空行
            string leftspace = "";
            if(node.Left != null)
            {
                leftspace = SpaceIndent(depth + "L") + Environment.NewLine;
            }

            //左部分木
            string left = ToString(node.Left, depth + "L");

            //合成
            return right + rightspace + current + leftspace + left;
        }

        private string Indent(string depth)
        {
            string indent = string.Empty;
            for (int i = 0; i < depth.Length; i++)
            {
                if (i < depth.Length - 1)
                {
                    if (depth[i] == depth[i + 1])
                    {
                        indent = indent + "　";
                    }
                    else
                    {
                        indent = indent + "│";
                    }
                }

                if (i == depth.Length - 1)
                {
                    if (depth[i] == 'R')
                    {
                        indent = indent + "┌";
                    }
                    else
                    {
                        indent = indent + "└";
                    }
                }
            }
            return indent;
        }

        private string SpaceIndent(string depth)
        {
            string indent = string.Empty;
            for (int i = 0; i < depth.Length; i++)
            {
                if (i < depth.Length - 1)
                {
                    if (depth[i] == depth[i + 1])
                    {
                        indent = indent + "　";
                    }
                    else
                    {
                        indent = indent + "│";
                    }
                }

                if (i == depth.Length - 1)
                {
                    if (depth[i] == 'R')
                    {
                        indent = indent + "│";
                    }
                    else
                    {
                        indent = indent + "│";
                    }
                }
            }
            return indent;
        }

結果
┌Yayoi		R
││		RL
│└Wakana	RL
│		R
Sayaka		
│		L
│　　┌Reika	LRRR
│　　│	LRRR
│　┌Ranko	LRR
│　│		LRR
│┌Natsuko	LR
│││		LRL
││└Miwako	LRL
││		LR
└Kayoko	L
　│		LL
　└Wakana	LL