ALDS1_9_A: Complete Binary Tree

問題へのリンク

C#のソース

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

// Q030 完全二分木 https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_9_A&lang=jp
class Program
{
    static string InputPattern = "InputX";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("5");
            WillReturn.Add("7 8 1 2 3");
            //node 1: key = 7, left key = 8, right key = 1,
            //node 2: key = 8, parent key = 7, left key = 2, right key = 3,
            //node 3: key = 1, parent key = 7,
            //node 4: key = 2, parent key = 8,
            //node 5: key = 3, parent key = 8,
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        int[] wkArr = InputList[1].Split(' ').Select(X => int.Parse(X)).ToArray();

        var HeapDict = new Dictionary<int, int>();
        for (int I = 0; I <= wkArr.GetUpperBound(0); I++) {
            HeapDict[I + 1] = wkArr[I];
        }
        int NodeID = 1;
        foreach (var EachPair in HeapDict.OrderBy(pX => pX.Key)) {
            var sb = new System.Text.StringBuilder();
            sb.AppendFormat("node {0}: key = {1}, ", NodeID++, EachPair.Value);

            int ParentKey = EachPair.Key / 2;
            int LeftKey = EachPair.Key * 2;
            int RightKey = EachPair.Key * 2 + 1;

            if (HeapDict.ContainsKey(ParentKey)) {
                sb.AppendFormat("parent key = {0}, ", HeapDict[ParentKey]);
            }
            if (HeapDict.ContainsKey(LeftKey)) {
                sb.AppendFormat("left key = {0}, ", HeapDict[LeftKey]);
            }
            if (HeapDict.ContainsKey(RightKey)) {
                sb.AppendFormat("right key = {0}, ", HeapDict[RightKey]);
            }
            Console.WriteLine(sb.ToString());
        }
    }
}

解説

Dictionaryでヒープのノードを管理してます。