实现二叉树 - 数据结构，trie

Question

二叉树。原理是可以理解的，但是就数组或关联数组而言，它们到底是什么样子的？

如果我可用的数据结构是：

AssociativeArray={tag:value,tag:value,tag:value} 
(of course, each tag is unique)

和

Array=[value,value,value] 
(where the value can be any data type including array)

例子：

DictOfWords={greeting:"hello",sound:"music",sleep:"dream",words:["hello","music","dream"]}
listOfWords=["hello","music","dream",DictOfWords]

由其中一个或两个构建的二叉树会是什么样子？

此外，从这些数据结构构建的 Trie for Word Search 的数据结构是什么样子的？

trie的节点会是什么样子？它是关联数组还是线性数组或两者的某种组合？我从这篇文章中了解到"Trie 每个字符包含一个节点"

那么顶级结构会是这样的：

trie={a：{}，b：{}

，c：{}...}

或

trie={a：[]，

b：[]，c：{}...}

或

trie=["a"，"b"，"c"...]

Answer 1

Try和Binary Trees通常不被认为是数组或关联数组。 它们被认为是节点的集合，通常作为结构实现。 例如，二叉树往往看起来像

struct BTreeNode
{
    value_type value;
    BTreeNode* left;
    BTreeNode* right;
};

和尝试往往看起来像

struct TrieNode
{
    char_type  letter;
    associative_array<char_type, TrieNode*> children;
};

现在，如果您只想用数组和关联数组对此进行建模，那么问题将是：您打算如何处理它们？ 如果您需要做的就是将数据存储在树/trie 结构中，那么您有很多选择。 但是，如果您真的想使用 BTree 作为 BTree 或将 Trie 用作 Trie，我们必须确保您用于将结构转换为数组/关联数组的任何转换都有效。 最简单的一种：将每个结构视为具有恒定条目数的关联数组

    4
   / 
  2   5
 /    
1   3   6

通常会按

BTreeNode oneNode(1, null, null);
BTreeNode threeNode(3, null, null);
BTreeNode twoNode(2, oneNode, threeNode);
BTreeNode sixNode(6, null, null);
BTreeNode fiveNode(5, null, sixNode);
BTreeNode fourNode(4, twoNode, fiveNode);

您可以将这些结构进行一对一转换为关联数组，并获得

fourNode = {   value: 4,
               left: {
                   value: 2,
                   left: {
                       value: 1
                   },
                   right: {
                       value: 3
                   }
               },
               right: {
                   value: 5,
                   right: {
                       value:6
                   }
              }
          }

与数组的转换相当，但阅读起来不太明显

存储"abc"abd"abe"ace"的类似trie创建了一个trie结构，看起来像

    a
   / 
  b    c
/ |    

中德·

执行与上述相同的从结构到值的转换，您可以得到

trie =  {
            letter: 'a',
            children: {
                'b': {
                    letter: 'b'
                    children: {
                        'c': { letter: 'c' },
                        'd': { letter: 'd' },
                        'e': { letter: 'e' }
                    }
                'c': {
                    letter: 'c'
                    children: {
                        'e': { letter: 'e' }
                    }
            }
       }

然而，坚持我最初的评论，"就数组或关联数组而言，它们到底是什么样子的？"是无法回答的。 它们实际上根本没有实现为数组或关联数组，因此"真正看起来像"不能与"数组或关联数组"一起使用。 从它们真正构建的节点结构的角度来考虑它们，您将走得更远。

例如，有一个自平衡二叉树的想法。 如果您将这些结构视为一堆链接在一起的节点，则这些结构非常容易理解。 如果你试图从数组/关联数组的角度来考虑一个自平衡二叉树，你会有很多麻烦，因为它们往往有一个指向其父级的指针，这会产生看起来非常混乱的关联数组。

struct SelfBalancingBTreeNode
{
    value_type value;
    SelfBalancingBTreeNode* parent;
    SelfBalancingBTreeNode* left;
    SelfBalancingBTreeNode* right;
};

要对此进行建模，您需要具有非常有趣的关联数组结构

leftNode = { value: 1, parent: null, left: null, right: null}
parentNode = value: 2, parent: null, left: leftNode, right: null}
leftNode['parent'] = parentNode

这会产生使用关联数组时通常不会想到的循环

Answer 2

二叉树：

     1
   /   
  2     3
 /    / 
4   5 6   7

可以表示为：

[1, 2, 3, 4, 5, 6, 7]

因此，索引 i 的子节点位于索引 2i 和 2i+1 处。

或者它可以表示为：

{1:[2,3], 2:[4,5], 3:[6,7]}

引用某处的根。

特里：

      1
  a /    b
   2     3
a /  b
 4   5

可以表示为：

{1:{a:2, b:3},
 2:{a:4, b:5},
 3:{},
 4:{},
 5:{}
}