3.3.3

3.3.3 #

解答 #

题目给出的序列就可以，如下（只有根结点的 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 库