标签: tree

当我需要在哈希表或平衡二叉树之间进行选择以实现集合或关联数组时,我应该考虑哪些因素？

我正在尝试提高应用程序的性能.我有一个调用树形式的性能信息,具有以下节点类:

public class Node
{
    public string Name; // method name
    public decimal Time; // time spent in method
    public List<Node> Children;
}

我想打印出树,这样我就能看到节点之间的线条 - 就像这个问题一样.我可以在C#中使用什么算法来做到这一点？

编辑:显然我需要使用递归 - 但我的尝试继续将行放在错误的位置.我要求的是一种特定的算法,它将以一种很好的方式打印树 - 有关何时打印垂直线以及何时打印水平线的详细信息.

编辑:仅使用字符串的副本来缩进节点是不够的.我不是在找

A
|-B
|-|-C
|-|-D
|-|-|-E
|-F
|-|-G

它一定要是

A
+-B
| +-C
| +-D
|   +-E
+-F
  +-G

或者类似的东西,只要树形结构可见.请注意,C和D的缩进与G不同 - 我不能只使用重复的字符串来缩进节点.

在javascript中是否有用于操作树的好库？为了清楚起见,我在数据结构中寻找树而不是显示模型.

我正在编写一个使用树数据结构的应用程序.我用C++编写它,现在我想用C#编写它.我使用指针来实现树数据结构.C#中还有一个指针吗？使用它安全吗？

我熟悉Java Collection Framework,它包含基本的接口:Collection和Map.我想知道为什么框架不包含作为基本集合的树和图形的结构.两者都可以视为子类型Collection.

顺便说一句,我知道TreeSet是由Red-Black Tree底层实现的.但是,TreeSet它不是树而是a Set,因此框架中没有真正的树.

我正在努力为一个介绍级别的CS课程设置一个问题集,并提出一个问题,从表面上看,似乎很简单:

您将获得一份包含父母姓名,出生日期和死亡日期的人员名单.你有兴趣找出谁在他们一生中的某个时刻是父母,祖父母,曾祖父母等等.设计一个算法,用这个信息作为一个整数来标记每个人(0表示这个人从来没有过孩子,1表示该人是父母,2表示该人是祖父母,等等.)

为简单起见,您可以假设族图是DAG,其无向版本是树.

这里有趣的挑战是你不能只看树的形状来确定这些信息.例如,我有8位曾祖父母,但由于我们出生时没有一个人活着,在他们的一生中,他们中没有一个是伟大的曾祖父母.

我能解决这个问题的最佳算法是在时间O(n ²)中运行,其中n是人数.这个想法很简单 - 从每个人开始一个DFS,找到在该人死亡日期之前出生的家谱中最远的后代.但是,我很确定这不是问题的最佳解决方案.例如,如果图形只是两个父母及其n个孩子,那么问题可以在O(n)中平凡地解决.我希望的是一些算法要么胜过O(n ²),要么运行时参数化在图形的形状上,这使得它对于宽图形来说很快,在最坏的情况下优雅地降低到O(n ²)案件.

我想用d3.js来构建一个谱系树.

我发现的所有例子都展示了有机树木.

有没有像样式这样的血统的例子吗？

我刚刚在我的项目中遇到了一个场景,我需要比较不同的树对象与已知实例的相等性,并且考虑到在任意树上运行的某种散列算法将非常有用.

以下面的树为例:

        O
       / \
      /   \
     O     O
    /|\    |
   / | \   |
  O  O  O  O
          / \
         /   \
        O     O

其中每个O表示树的节点,是一个任意对象,具有相关的哈希函数.所以问题简化为:给定树结构节点的哈希码和已知结构,什么是计算整个树的(相对)无冲突哈希码的不错算法？

关于散列函数属性的一些注意事项:

• 散列函数应该取决于树中每个节点的哈希码及其位置.
• 重新排序节点的子节点应明显更改生成的哈希码.
• 反映树的任何部分应明显更改生成的哈希代码

如果它有帮助,我在我的项目中使用C#4.0,虽然我主要是寻找理论解决方案,所以伪代码,描述或其他命令式语言的代码都可以.

UPDATE

嗯,这是我自己提出的解决方案.这里的几个答案对它有很大帮助.

每个节点(子树/叶节点)具有以下散列函数:

public override int GetHashCode()
{
    int hashCode = unchecked((this.Symbol.GetHashCode() * 31 +
        this.Value.GetHashCode()));
    for (int i = 0; i < this.Children.Count; i++)
        hashCode = unchecked(hashCode * 31 + this.Children[i].GetHashCode());
    return hashCode;
}

正如我所看到的,这个方法的好处是,哈希码可以被缓存,只有当节点或其后代之一发生变化时才会重新计算.(感谢vatine和Jason Orendorff指出这一点).

无论如何,如果人们可以在这里评论我建议的解决方案,我将不胜感激 - 如果它做得很好,那么很好,否则任何可能的改进都会受到欢迎.

我正在编写一个由Tree和TreeNode组合而成的数据树结构.树将包含数据的根和顶级操作.我正在使用UI库以窗体形式呈现树,我可以将树绑定到TreeView.

我需要在DB中保存这个树和节点.保存树并获得以下功能的最佳方法是什么:

1. 直观的实施.
2. 轻松绑定.很容易从树移动到DB结构并返回(如果有的话)

我有两个想法.第一种是将数据序列化为表格中的单行.第二种是保存在表中,但是当移动到数据实体时,我将在更改的节点上松开表上的行状态.

有任何想法吗？

我正在编写一个利用二叉搜索树来存储数据的程序.在以前的程序(无关)中,我能够使用Java SE6提供的实现来实现链表.二元搜索树有类似的东西,还是我需要"从头开始"？