3.3.3

上次更新:2021-09-06
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

题目给出的序列就可以,如下(只有根结点的 2-3 树的高度是 0,以此类推):

S

ES

 |--E--|
A       S

 |--E--|
AC       S

 |--E--|
AC       HS

 |--ES--|
AC   H   X

 |--ES--|
AC   HM   X

SEACHXM 排序后是 ACEHMSX,符合条件的一种情况即为 AC 为左子结点,HM 为中间结点,X 为右侧结点,ES 为根节点。

也可以是其他的模式,总共有 2880 种符合条件的组合(result.txt),共三种模式,结果如下:

864
 |--CM--|
A   EH   SX

1152
 |--EM--|
AC   H   SX

864
 |--ES--|
AC   HM   X

可以观察到树的形状是没有变化的,只是键在各结点中的分布有些变化。

代码

using System;
using System.IO;
using BalancedSearchTree;

var input = "ACEHMSX";
var output = File.CreateText("result.txt");
var count = 0;
Dig(input, string.Empty);
Console.WriteLine(count);

void Dig(string source, string testCase)
{
    if (source.Length == 0)
    {
        var tree = new TwoThreeBst<char, int>();
        foreach (var c in testCase)
        {
            tree.Put(c, 1);
        }

        if (tree.Height() == 1)
        {
            count++;
            output.WriteLine(testCase);
            output.WriteLine(tree.ToString());
            output.WriteLine();
        } 
    }

    for (var i = 0; i < source.Length; i++)
    {
        Dig(source.Remove(i, 1), testCase + source[i]);
    }
}

另请参阅

BalancedSearchTree 库

上一题 下一题