ALDS1_7_C: Tree Walk

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

// Q025 木の巡回 https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_7_C&lang=jp
class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("9");
            WillReturn.Add("0 1 4");
            WillReturn.Add("1 2 3");
            WillReturn.Add("2 -1 -1");
            WillReturn.Add("3 -1 -1");
            WillReturn.Add("4 5 8");
            WillReturn.Add("5 6 7");
            WillReturn.Add("6 -1 -1");
            WillReturn.Add("7 -1 -1");
            WillReturn.Add("8 -1 -1");
            //Preorder
            // 0 1 2 3 4 5 6 7 8
            //Inorder
            // 2 1 3 0 6 5 7 4 8
            //Postorder
            // 2 3 1 6 7 5 8 4 0
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct NodeInfoDef
    {
        internal int LeftNodeID;
        internal int RightNodeID;
    }

    static Dictionary<int, NodeInfoDef> mNodeInfoDict = new Dictionary<int, NodeInfoDef>();

    static void Main()
    {
        List<string> InputList = GetInputList();

        int[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(X => int.Parse(X)).ToArray();

        // 処理01 入力をDictに保存
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            NodeInfoDef WillAdd;
            WillAdd.LeftNodeID = wkArr[1];
            WillAdd.RightNodeID = wkArr[2];
            mNodeInfoDict.Add(wkArr[0], WillAdd);
        }

        // 処理02 木の根をO(n)で求める
        var ChildNodeSet = new HashSet<int>();
        foreach (var EachPair in mNodeInfoDict) {
            ChildNodeSet.Add(EachPair.Value.LeftNodeID);
            ChildNodeSet.Add(EachPair.Value.RightNodeID);
        }
        int RootNode = -1;
        foreach (int EachKey in mNodeInfoDict.Keys) {
            if (ChildNodeSet.Contains(EachKey) == false) {
                RootNode = EachKey;
            }
        }

        string WillOut = "";

        // 先行順巡回でDFS
        var PreorderNodeList = new List<int>();
        Preorder(RootNode, PreorderNodeList);
        Console.WriteLine("Preorder");
        WillOut = string.Join(" ",
            Array.ConvertAll(PreorderNodeList.ToArray(), pX => pX.ToString()));
        Console.WriteLine(" " + WillOut);

        // 中間順巡回でDFS
        var InorderNodeList = new List<int>();
        Inorder(RootNode, InorderNodeList);
        Console.WriteLine("Inorder");
        WillOut = string.Join(" ",
            Array.ConvertAll(InorderNodeList.ToArray(), pX => pX.ToString()));
        Console.WriteLine(" " + WillOut);

        // 後行順巡回でDFS
        var PostorderNodeList = new List<int>();
        Postorder(RootNode, PostorderNodeList);
        Console.WriteLine("Postorder");
        WillOut = string.Join(" ",
            Array.ConvertAll(PostorderNodeList.ToArray(), pX => pX.ToString()));
        Console.WriteLine(" " + WillOut);
    }

    // 先行順巡回でDFS
    static void Preorder(int pCurrNode, List<int> pPrintNodeList)
    {
        if (pCurrNode == -1) return;
        pPrintNodeList.Add(pCurrNode);
        Preorder(mNodeInfoDict[pCurrNode].LeftNodeID, pPrintNodeList);
        Preorder(mNodeInfoDict[pCurrNode].RightNodeID, pPrintNodeList);
    }

    // 中間順巡回でDFS
    static void Inorder(int pCurrNode, List<int> pPrintNodeList)
    {
        if (pCurrNode == -1) return;
        Inorder(mNodeInfoDict[pCurrNode].LeftNodeID, pPrintNodeList);
        pPrintNodeList.Add(pCurrNode);
        Inorder(mNodeInfoDict[pCurrNode].RightNodeID, pPrintNodeList);
    }

    // 後行順巡回でDFS
    static void Postorder(int pCurrNode, List<int> pPrintNodeList)
    {
        if (pCurrNode == -1) return;
        Postorder(mNodeInfoDict[pCurrNode].LeftNodeID, pPrintNodeList);
        Postorder(mNodeInfoDict[pCurrNode].RightNodeID, pPrintNodeList);
        pPrintNodeList.Add(pCurrNode);
    }
}

解説

疑似コードをC#で実装してます。