0

二叉树。原理是可以理解的，但就数组或关联数组而言，它们真正看起来像什么？

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

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 的数据结构是什么样的？

trie 的节点会是什么样子？它是关联阵列还是线性阵列或两者的某种组合？我从这篇文章中了解到“一个树每个字符拥有一个节点”

顶层结构也会是这样的：

特里={a:{},b:{},c:{}...}

或者

特里={a:[],b:[],c:{}...}

或者

特里=["a","b","c"...]

4

2 回答 2

2

二叉树：

     1
   /   \
  2     3
 / \   / \
4   5 6   7

可以表示为：

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

i因此 index的子节点位于 index2i和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:{}
}
于 2013-09-15T19:34:34.570 回答
2

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

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

尝试看起来像

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

现在，如果您只想使用数组和关联数组对此进行建模，那么问题将是：您打算用它们做什么？如果您需要做的只是将数据存储在树/特里结构中，那么您有很多选择。但是，如果您真的想将 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”的可比较特里树创建的特里树结构看起来像

    a
   / \
  b    c
/ | \   \

cdee

像上面一样从结构到值进行相同的转换，你得到

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

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

于 2013-09-15T23:52:06.773 回答