From what I understand of ternary search trees, they are inverse deterministic in the items that can be sought and found (not sure about correct terms). What I mean, if you create a ternary tree for cat, bicycle, axis and you give someone the ternary tree, he should be able to deduct those three words from it.
Is this correct?
I'm asking, because I have a ternary tree structure that contains words like ISMAP, SELECTED and COMPACT (indeed, attributes of HTML 4) and I wonder if I could get the complete list of items that is stored in that tree (original documentation is gone). The structure looks like this:
internal static byte [] htmlAttributes = {
72,5,77,0, 82,0,0,0, 69,0,0,0, 70,0,0,0, 0,0,0,1, 67,12,40,0, 79,7,0,0,
77,31,0,0, 80,0,0,0, 65,0,0,0, 67,0,0,0, 84,0,0,0, 0,0,0,2, 73,11,18,0,
84,0,0,0, 69,0,0,0, 0,0,0,1, 65,0,0,0, 67,0,0,0, 84,0,0,0, 73,0,0,0,
79,0,0,0, 78,0,0,0, 0,0,0,1, 72,0,0,0, 69,0,0,0, 67,0,0,0, 75,0,0,0,
69,0,0,0, 68,0,0,0, 0,0,0,2, 76,0,0,0, 65,0,0,0, 83,0,0,0, 83,0,0,0,
73,0,0,0, 68,0,0,0, 0,0,0,1, 68,0,0,0, 69,0,0,0, 66,0,0,0, 65,0,0,0,
83,0,0,0, 69,0,0,0, 0,0,0,1, 68,0,28,0, 69,7,15,0, 67,0,22,0, 76,0,0,0,
65,0,0,0, 82,0,0,0, 69,0,0,0, 0,0,0,2, 65,0,0,0, 84,0,0,0, 65,0,0,0,
0,0,1,1, 83,0,0,0, 82,0,0,0, 67,0,0,0, 0,0,0,1, 73,0,0,0, 83,0,0,0,
65,0,0,0, 66,0,0,0, 76,0,0,0, 69,0,0,0, 68,0,0,0, 0,0,0,2, 70,0,0,0,
69,0,0,0, 82,0,0,0, 0,0,0,2, 70,0,0,0, 79,0,0,0, 82,0,0,0, 0,0,0,1,
78,8,48,0, 79,36,0,0, 83,30,55,0, 72,0,0,0, 65,0,0,0, 68,0,0,0, 69,0,0,0,
0,0,0,2, 77,9,0,0, 85,0,0,0, 76,0,0,0, 84,0,0,0, 73,0,0,0, 80,0,0,0,
76,0,0,0, 69,0,0,0, 0,0,0,2, 73,0,6,0, 83,0,0,0, 77,0,0,0, 65,0,0,0,
80,0,0,0, 0,0,0,2, 76,0,0,0, 79,0,0,0, 78,0,0,0, 71,0,0,0, 68,0,0,0,
69,0,0,0, 83,0,0,0, 67,0,0,0, 0,0,0,1, 72,0,9,0, 82,0,0,0, 69,0,0,0,
70,0,0,0, 0,0,0,2, 65,0,0,0, 77,0,0,0, 69,0,0,0, 0,0,0,1, 82,0,0,0,
69,0,0,0, 83,0,0,0, 73,0,0,0, 90,0,0,0, 69,0,0,0, 0,0,0,2, 82,14,22,0,
69,0,0,0, 65,0,0,0, 68,0,0,0, 79,0,0,0, 78,0,0,0, 76,0,0,0, 89,0,0,0,
0,0,0,2, 87,0,0,0, 82,0,0,0, 65,0,0,0, 80,0,0,0, 0,0,0,2, 80,0,0,0,
82,0,0,0, 79,0,0,0, 70,0,0,0, 73,0,0,0, 76,0,0,0, 69,0,0,0, 0,0,0,1,
83,0,12,0, 82,3,0,0, 67,0,0,0, 0,0,0,1, 69,0,0,0, 76,0,0,0, 69,0,0,0,
67,0,0,0, 84,0,0,0, 69,0,0,0, 68,0,0,0, 0,0,0,2, 85,0,0,0, 83,0,0,0,
69,0,0,0, 77,0,0,0, 65,0,0,0, 80,0,0,0, 0,0,0,1,
};
I think the algorithm is something like this
printOutWords(root, wordSoFar)
if (!root.hasMiddle)
print wordSoFar + root.char
if (root.hasMiddle)
printOutWords(root.middle, wordSoFar + root.char)
if (root.hasLeft)
printOutWords(root.left, wordSoFar)
if (root.hasRight)
printOutWords(root.right, wordSoFar)
Then, start it with
printOutWords(ternaryTree, "")
I don't know how to decode your array, but if you can implement these operations, I think it's something like this.
Ok, here is some C# code that works based on a simple array representation. I used the tree from this wikipedia article
http://en.wikipedia.org/wiki/Ternary_search_tree
I represented it as an array where the root is element 0, and then its kids are 1, 2, 3. 1's kids are 4,5,6 and so on. '\0' is used to represent that there is no more kid. The algorithm is the same as above.
using System;
using System.Text;
namespace TreeDecode
{
class Program
{
// http://en.wikipedia.org/wiki/Ternary_search_tree
//The figure below shows a ternary search tree with the strings "as", "at", "cup", "cute", "he", "i" and "us":
internal static char[] searchTree = {
'c',
'a', 'u', 'h',
'\0', 't', '\0', '\0', 't', '\0', '\0', 'e', 'u',
'\0','\0','\0', 's','\0','\0','\0','\0','\0', '\0','\0','\0', 'p','e','\0', '\0','\0','\0', '\0','\0','\0', '\0','\0','\0', 'i','s','\0',
};
static void printOutWords(char[] tree, int root, string wordSoFar) {
if (!HasMiddle(tree, root))
Console.WriteLine(wordSoFar + CharAt(tree, root));
if (HasMiddle(tree, root))
printOutWords(tree, MiddleKid(root), wordSoFar + CharAt(tree, root));
if (HasLeft(tree, root))
printOutWords(tree, LeftKid(root), wordSoFar);
if (HasRight(tree, root))
printOutWords(tree, RightKid(root), wordSoFar);
}
private static int RightKid(int root)
{
return root * 3 + 3;
}
private static bool HasRight(char[] tree, int root)
{
int rightIndex = RightKid(root);
return (rightIndex < tree.Length && tree[rightIndex] != 0);
}
private static int LeftKid(int root)
{
return root * 3 + 1;
}
private static bool HasLeft(char[] tree, int root)
{
int leftIndex = LeftKid(root);
return (leftIndex < tree.Length && tree[leftIndex] != 0);
}
private static int MiddleKid(int root)
{
return root * 3 + 2;
}
private static bool HasMiddle(char[] tree, int root)
{
int middleIndex = MiddleKid(root);
return (middleIndex < tree.Length && tree[middleIndex] != 0);
}
private static int NumKids(char[] tree, int root)
{
return (HasMiddle(tree, root) ? 1 : 0) + (HasRight(tree, root) ? 1 : 0) + (HasLeft(tree, root) ? 1 : 0);
}
private static string CharAt(char[] tree, int root)
{
return new String(tree[root], 1);
}
static void Main(string[] args)
{
printOutWords(searchTree, 0, "");
}
}
}
This prints
cute
cup
at
as
he
us
i