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

わんくま同盟

ASP.NET、C++/CLI、Java 何でもどうぞ

C# と VB.NET の入門サイト


■103462 / )  二分木のクラス
□投稿者/ 星は昴 (10回)-(2024/11/28(Thu) 14:00:39)

分類:[C#] 

 以下は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;
}

返信 編集キー/


管理者用

- Child Tree -