0

I have to structure certain data and tree data structure suited the requirement.
I have to assign certain number to each node in such a manner that I can trace back the parent from its number. I am planning to use hashtable to store these numbers as keys, so there cannot be any duplicate value.

e.g.

parent - 000001
  child1 - 000011
    innerchild1 - 000111 (level 2, get 2 bits from right and we can reach parent)
    innerchild2 - 000211
  child2 - 000021
    innerchild1 - 000121
    innerchild2 - 000221

Depending on the level, I can mask certain bits and I can uniquely identify the parent. But if my tree grows wider(i.e. more parents, numbers will duplicate) How to overcome this problem?

4

4 回答 4

0

我认为“定义明确”的数字作为键还不够好。

您需要根据您的要求设计一个树结构，或者至少设计一个 Node 类来更轻松地获取 parentId/parent Node。

例如

Node{
 id, #could be string, number, unique
 actualNode # you node value
 parentId (or Node parentNode )
}

如果您出于某种原因坚持使用哈希表，您仍然可以使用 node.id 作为键。有多种方法可以生成唯一的字符串、数字。例如当前的纳秒...

于 2012-06-11T12:29:34.720 回答
0

我建议您使用数字 1-9 的数字。

为什么没有-0？前导 0 的 9 位数字在没有前导 0 的情况下看起来像 8 位，会导致错误。

因此，直到任何父母最多有 9 个孩子，这个结构就足够了。

数字 0 - 共同根
1-9 - 第一个孩子
11-19 - 第一个孩子的第二代孩子......
等等

如果您的节点超过 9 位，请使用 100 基算术。（允许的数字为 10-99）。99个孩子够吗？如果没有，请使用 100-999。

于 2012-06-11T12:09:13.663 回答
0

可以使用嵌套集树哟解决问题。请参考下面的书。这是一本了不起的书，其中还包含有关嵌套集树的文本。

http://www.elsevier.com/wps/find/bookdescription.cws_home/702605/description

于 2012-06-11T12:09:20.247 回答
0

您为节点分配“特殊”数字的方法听起来很糟糕——可能会导致大量的工作、可扩展性限制以及最重要的是......错误。

如果您需要知道父节点是什么，请将对父节点的引用存储在节点的字段中！

于 2012-06-11T12:14:50.620 回答