木構造クラスを作ってみた

はじめに

AtCoderで遊んでいる時、木構造で表せそうな問題の遭遇したので作ってみた。
結果的には時間がかかりすぎるので使わなかったけど、頑張ったので供養する。

設計

クラスは2つ。木そのものを操作してノードを追加したり検索したりするTreeと、ノードに関するデータを保持したり返したりするNode。
Treeの方にはオーバーロードしているメソッドがいくつかあるが、
これは引数を指定しなかった場合、自動的に根ノードから検索などの操作ができるようにするため。

具体的なコード

まずは木のクラスであるTree、次にノードのクラスNodeを示す。

木のクラス

internal class Tree<T>
{
    private Node<T> _root;

    public Tree(string name, T value)
    {
        _root = new Node<T>(name, value);
    }

    /// 子ノードの名前と値、親ノードの名前から子を追加する
    public void CreateChild(string childName, T childValue, T parentTarget)
    {
        Node<T> parent = Find(_root, parentTarget); // 値で親を探す
        if (parent is null) return;
        Node<T> child = new Node<T>(childName, childValue);
        parent.AddChild(child);
    }

    /// 名前から子を探して削除
    public void RemoveChild(T targetName)
    {
        Node<T> node = Find(_root, targetName);
        node?.Remove();
    }
    
    /// 子の検索メソッドの窓口
    public Node<T> Find(Node<T> startNode, T targetName)
    {
        var result = FindDuration(startNode, targetName);
        if(result is null) throw new KeyNotFoundException($"{targetName}は見つかりませんでした");
        return result;
    }
    public Node<T> Find(T targetName) => Find(_root, targetName);

    /// 子の検索メソッドの実体
    private static Node<T> FindDuration(Node<T> startNode, T targetName)
    {
        if (EqualityComparer<T>.Default.Equals(startNode.GetNodeValue(), targetName))
            return startNode;

        foreach (var child in startNode.GetChildren())
        {
            var result = FindDuration(child, targetName);
            if (result != null) return result;
        }
        return null;
    }

    /// 子が何代目かを探るメソッドの窓口
    public int? WhatNumber(Node<T> startNode, T targetName)
    {
        if (startNode is null) return null;
        return WhatNumberSearch(startNode, targetName, 0);
    }
    public int? WhatNumber(T targetName) => WhatNumber(_root, targetName);

    /// 子が何代目かを探るメソッドの実体
    private int? WhatNumberSearch(Node<T> startNode, T targetName, int generationNum)
    {
        if (EqualityComparer<T>.Default.Equals(startNode.GetNodeValue(), targetName))
            return generationNum;

        foreach (var child in startNode.GetChildren())
        {
            var result = WhatNumberSearch(child, targetName, generationNum + 1);
            if (result != null) return result;
        }
        return null;
    }

    /// 深さ優先探索により木構造をインデントを使って描画する
    public void TraversePreOrder(Node<T> node, int depth = 0)
    {
        Console.WriteLine(new string(' ', depth * 2) + node.GetNodeValue());
        foreach (var child in node.GetChildren())
            TraversePreOrder(child, depth + 1);
    }

    public void TraversePreOrder() => TraversePreOrder(_root, 0);
}

続いてノードの情報を保持するNodeクラス。

ノードのクラス

    internal class Node<T>
    {
        private string _name; // このノードの名前
        private T _value; // このノードが持つデータ
        private Node<T> _parent;
        private List<Node<T>> _children = new List<Node<T>>();

        public Node(string name, T value)
        {
            _name = name;
            _value = value;
        }

        public T GetNodeValue() => _value;
        public string GetNodeName() => _name;

        public Node<T> GetParent() => _parent;

        public List<Node<T>> GetChildren() => _children;

        private void AddParent(Node<T> parentNode)
        { 
            _parent = parentNode;
        }

        internal void AddChild(Node<T> childNode)
        {
            childNode.AddParent(this);
            _children.Add(childNode);
        }

        public void Remove()
        {
            this.GetParent()?.GetChildren().Remove(this);
            _parent = null;
            _children.Clear();
        }

        public override string ToString()
        {
            return $"名前：{_name}, 値{_value}";
        }
    }

使用例

使用例

internal class Program
{
    static void Main(string[] args)
    {
        // 木構造の生成
        Tree<string> tree = new Tree<string>("CEO", "CEO");

        // 子を追加
        tree.CreateChild("CTO", "CTO", "CEO");
        tree.CreateChild("CFO", "CFO", "CEO");
        tree.CreateChild("DevA", "DevA", "CTO");
        tree.CreateChild("DevB", "DevB", "CTO");
        tree.CreateChild("analyst", "analyst", "CFO");
        tree.CreateChild("mobA-1", "mobA-1", "DevA");
        tree.CreateChild("mobA-2", "mobA-2", "DevA");
        tree.CreateChild("mobB", "mobB", "DevB");

        // 深さ優先探索による全要素走査
        tree.TraversePreOrder();

        Console.WriteLine();

        // 特定のノードから下に探索を行う
        try
        {
            Console.WriteLine(tree.Find("analyst").ToString());
            Console.WriteLine(tree.Find("mobA-1").ToString());
            Console.WriteLine(tree.Find("mobC")?.ToString());  // 例外がスローされる
        }
        catch
        {
            Console.WriteLine("見つかりませんでした。\n");
        }


        // 何代目かを探る
            Console.WriteLine(tree.WhatNumber("CEO"));
            Console.WriteLine(tree.WhatNumber("DevB"));
            Console.WriteLine(tree.WhatNumber("mobC")); // nullになる

        // 子を削除
        tree.RemoveChild("mobA-2");
        tree.TraversePreOrder();
    }
}

出力はこんな感じになる

工夫が必要だった点

• なるべくプロパティを使わないこと。直接Nodeの情報にアクセスさせず、メソッドから引き出すように心掛けた
• WhatNumberメソッドを窓口と実体に分けたこと。元々は世代を表すnumberをユーザーが触れる状態で、バグの元になる状態だった。それを触らせないように分離した
• 子の追加や親の追加の処理をどちらに持たせるのかという点。元々Nodeに持たせていたものを直接呼ぶ形にしていた。しかし、Treeを通じて行う方が自然かと思ったので、名前を指定して追加できるようにした

反省点

• 再起処理と例外で混乱した点。TreeのFindメソッドは元々1つにしていたが、存在しないノードを探すと上手く動かなかった（今も結局上手い処理ができずにtry～catchで動かしているけど...）。もっとスマートに「見つからなかった」と通知できる仕組みを思いつけばよいのだけど
• 木構造なのだから木構造で解こう、と考えすぎたこと。元々の問題は深さの情報だけあれば解けるものだったので、わざわざ木構造を作らなくても配列さえあれば圧倒的に短いコードで解くことができた