是否可以生成在三元搜索樹中可找到的所有可能的術語？

Question

從我對三元搜索樹的理解來看，它們在可以找到和找到的項目中是反向確定性的（對於正確的術語不確定）。我的意思是，如果你爲貓創建一棵三元樹貓,自行車,軸並且你給某人三元樹，他應該能夠從它中扣除這三個詞。

這是正確的嗎？我想問，因爲我有一個三元樹結構，包含像ISMAP，SELECTED和COMPACT（實際上，HTML 4的屬性）的單詞，我不知道是否可以得到存儲在那個項目的完整列表樹（原始文檔不見了）。該結構是這樣的：

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, 
}; 

Answer 1

我覺得算法是這樣的

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) 

然後，

printOutWords(ternaryTree, "") 

啓動它，我不知道如何將數組解碼，但如果你可以實施這些操作，我認爲這是這樣的。

好的，這裏有一些基於簡單數組表示的C＃代碼。我使用的樹從該維基百科文章

http://en.wikipedia.org/wiki/Ternary_search_tree

I表示它作爲一個陣列，其中根是元素0，然後將其孩子們1，2，3 1的孩子是4,5,6和等等。 '\ 0'用來表示沒有更多的孩子。該算法與上述相同。

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, ""); 
     } 
    } 
} 

這將打印

cute 
cup 
at 
as 
he 
us 
i 

Answer 2

的數據結構是不準確的三元樹由於第三分支是隱式的（即，當前條目之後的下一條目）。這有點像在二叉樹結構中實現的trie。每4個數字對應一個像struct { char letter, Loff, Roff, flag}這樣的結構。例如，條目0 = 72,5,77,0是字母'H'，左偏移5，右偏移77，標誌0（可能意思不是終端）。在左偏移之後，在＃0之後的5個條目我們有67,12,40,0這是C, 12, 40, 0; ＃5之後的12個條目，65,0,0,0是A,0,0,0。它和接下來的5個條目（65,67,84,73,79,78）顯然對應於字符串ACTION。在右偏移之後，在＃0之後的77個條目中，我們有78,8,48,0, 79,36,0,0, 83,30,55,0, 72,0,0,0, 65,...或N，O和S分支的條目，然後是沒有明確分支的H，A，D，E條目，以製作NOSHADE。

當您沿着樹葉走向樹葉時，向當前字符串中添加字母（如在樹中的遍歷中），並且當您返回時（離開樹葉）從當前字符串的末尾刪除字母。