ALDS1_8_B: Binary Search Tree II

問題へのリンク

C#のソース

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

// Q028 二分探索木：検索 https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_8_B&lang=jp
class Program
{
    static string InputPattern = "InputX";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("10");
            WillReturn.Add("insert 30");
            WillReturn.Add("insert 88");
            WillReturn.Add("insert 12");
            WillReturn.Add("insert 1");
            WillReturn.Add("insert 20");
            WillReturn.Add("find 12");
            WillReturn.Add("insert 17");
            WillReturn.Add("insert 25");
            WillReturn.Add("find 16");
            WillReturn.Add("print");
            //yes
            //no
            // 1 12 17 20 25 30 88
            // 30 12 1 20 17 25 88
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct NodeInfo
    {
        internal int? ParentNode;
        internal int? LeftNode;
        internal int? RightNode;
    }

    static int? mRootNode = null;
    static Dictionary<int?, NodeInfo> mTreeDict = new Dictionary<int?, NodeInfo>();

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

        foreach (string EachStr in InputList.Skip(1)) {
            string[] SplitArr = EachStr.Split(' ');

            if (SplitArr[0] == "insert") {
                Insert(int.Parse(SplitArr[1]));
            }
            if (SplitArr[0] == "find") {
                int? FindResult = Find(int.Parse(SplitArr[1]));
                Console.WriteLine(FindResult == null ? "no" : "yes");
            }
            if (SplitArr[0] == "print") {
                var InorderNodeList = new List<int?>();
                Inorder(mRootNode, InorderNodeList);
                foreach (int? EachInt in InorderNodeList) {
                    Console.Write(" {0}", EachInt);
                }
                Console.WriteLine();

                var PreorderNodeList = new List<int?>();
                Preorder(mRootNode, PreorderNodeList);
                foreach (int? EachInt in PreorderNodeList) {
                    Console.Write(" {0}", EachInt);
                }
                Console.WriteLine();
            }
        }
    }

    // Insert処理
    static void Insert(int? pZ)
    {
        int? ParentNode = null; // 親ノード
        int? CurrNode = mRootNode;
        while (CurrNode != null) {
            ParentNode = CurrNode; // 親ノードを設定
            if (pZ < CurrNode) {
                CurrNode = mTreeDict[CurrNode].LeftNode; // 左ノードへ移動
            }
            else {
                CurrNode = mTreeDict[CurrNode].RightNode; // 右ノードへ移動
            }
        }
        NodeInfo WillAdd;
        WillAdd.ParentNode = ParentNode;
        WillAdd.LeftNode = null;
        WillAdd.RightNode = null;
        mTreeDict[pZ] = WillAdd;

        if (ParentNode == null) { // T が空の場合
            mRootNode = pZ;
        }
        else if (pZ < ParentNode) {
            NodeInfo wkTreeDict = mTreeDict[ParentNode];
            wkTreeDict.LeftNode = pZ;
            mTreeDict[ParentNode] = wkTreeDict;
        }
        else {
            NodeInfo wkTreeDict = mTreeDict[ParentNode];
            wkTreeDict.RightNode = pZ;
            mTreeDict[ParentNode] = wkTreeDict;
        }
    }

    // 中間順巡回でDFS
    static void Inorder(int? pCurrNode, List<int?> pPrintNodeList)
    {
        if (pCurrNode == null) return;
        Inorder(mTreeDict[pCurrNode].LeftNode, pPrintNodeList);
        pPrintNodeList.Add(pCurrNode);
        Inorder(mTreeDict[pCurrNode].RightNode, pPrintNodeList);
    }

    // 先行順巡回でDFS
    static void Preorder(int? pCurrNode, List<int?> pPrintNodeList)
    {
        if (pCurrNode == null) return;
        pPrintNodeList.Add(pCurrNode);
        Preorder(mTreeDict[pCurrNode].LeftNode, pPrintNodeList);
        Preorder(mTreeDict[pCurrNode].RightNode, pPrintNodeList);
    }

    static int? Find(int? SearchVal)
    {
        int? CurrNode = mRootNode;
        while (CurrNode != null && CurrNode != SearchVal) {
            if (SearchVal < CurrNode) {
                CurrNode = mTreeDict[CurrNode].LeftNode;
            }
            else {
                CurrNode = mTreeDict[CurrNode].RightNode;
            }
        }
        return CurrNode;
    }
}

解説

Dictionaryで二分探索木を管理し、
再帰で、中間順巡回と先行順巡回で深さ優先探索してます。