标签: multiway-tree

许多数据结构使用称为"左子,右兄弟"表示的表示将多路树存储为二叉树.这是什么意思？你为什么要用它？

想象一下以下的树:

    A
   / \
  B   C
 / \   \
D   E   F

我正在寻找一种方法来查询例如F是否是A的后代(注意:F不需要是F 的直接后代),在这种情况下,这将是真的.只需要针对较大的潜在后代节点池测试有限数量的潜在父节点.

更新:在测试节点是否是潜在父池中节点的后代时,需要针对所有潜在父节点对其进行测试.

这是一个想法:

• 将多路树转换为trie,即将以下前缀分配给上述树中的每个节点:

   A = 1
   B = 11
   C = 12
   D = 111
   E = 112
   F = 121
  

  Run Code Online (Sandbox Code Playgroud)

• 然后,为每个可能的前缀大小保留一个位数组,并添加要测试的父节点,即如果将C添加到潜在的父节点池,请执行以下操作:

    1    2    3  <- Prefix length
  
  *[1]  [1]  ...
   [2] *[2]  ...
   [3]  [3]  ...
   [4]  [4]  ...
   ...  ...
  

  Run Code Online (Sandbox Code Playgroud)

• 当测试节点是否是潜在父节点的后代时,取其trie前缀,查找第一个"前缀数组"中的第一个字符(见上文),如果存在,则在第二个"前缀中查找第二个前缀字符数组"依此类推,即测试F导致:

   F = 1    2    1
  
     *[1]  [1]  ...
      [2] *[2]  ...
      [3]  [3]  ...
      [4]  [4]  ...
      ...  ...
  

  Run Code Online (Sandbox Code Playgroud)

  所以是的,F是C.的后代.

这个测试似乎是最坏的情况O(n),其中n …

有人知道我如何以美学上似乎合理的方式绘制多路树？信息:

• 或多或少100项
• 每个级别的项目数大致相同
• 10级
• 每个节点都有0(叶子)和6个孩子
• 每个节点都指定它自己的级别,无论它的根源如何.

我目前正在使用PIL,将每个"线"划分为img.size()[0]/节点数,并绘制线draw.line来表示边缘,但它完全搞砸了

我希望你能帮助我=],我要发布的任何信息.

更新:
我发现了更多关于我正在努力实现的例子:在MySQL中管理分层数据.我想在JavaScript中这样做,因为我正在构建一个应用程序,它接受层次结构中的注释,更具体的是reddit.com.如果您在chrome web浏览器上有Pretty JSON扩展,请转到reddit并单击线程注释,然后将.json添加到URL以查看我正在解析的内容.
我得到JSON数据就好了,它只是解析注释并添加适当的HTML来显示它的嵌套.
解决方案的想法？

老问题:
我正在研究一个程序,在编写代码之前,我需要找出逻辑.我正在接收树格式的数据,但是每个父节点可能有几个子节点,而我可以看到的唯一树就是树的重量或树,其中每个节点最多有两个子节点.所以我试图找出算法来评估树的每个节点,如下所示:

startingParent[15] // [# of children]
    child1[0]
    child2[5]
       child2ch1[4]
       ...
       child2ch5[7]
    child3[32]
    ...
    child15[4]

现在,当我试着写出我的算法是如何工作的时候我最终编写了嵌套for/while循环但是我最终为树的高度的每个级别编写了一个循环,对于动态数据和未知高度的树具有未知数量的每个节点的子节点不起作用.我知道在某些时候我学会了如何穿越这样的树,但它现在完全逃脱了我.任何人都知道如何在循环方面做到这一点？

我在实现非二叉树时遇到问题,其中根节点可以具有任意数量的子节点.基本上,我想了解一下如何使用它的一些想法,因为我确实编写了一些代码,但我仍然坚持下一步该做什么.顺便说一句,我根本不能使用任何Collections类.我只能使用系统.

using System;

namespace alternate_solution
{
 //            [root]
 //        /  /      \    \
 //    text  text  text  text

class Node//not of type TreeNode (since Node is different from TreeNode)
{
    public string data;
    public Node child;

    public Node(string data)
    {
        this.data = data;
        this.child = null;
    }

}

}

我们需要ADT具有搜索和排名功能.也就是说,除了STL map的接口外,还需要一个函数'int get_rank(key)'.

这种功能的标准实现需要在自平衡搜索树的每个节点中支持和更新额外的整数字段(例如,在黑红树中,在STL映射/集合中使用).但似乎,STL map/set不这样做.

我们正在寻找一种基于标准容器(STL,Boost)的解决方案,它具有最佳的时间复杂度:查找/添加/删除元素需要O(log n)(如在STL map/set中),通过a计算排名key也需要O(log n).

通过元素的等级,我们指的是元素在地图/集合的所有元素的排序序列中的位置.

例.set = {0,4,6,7,8} rank(0)= 1,rank(4)= 2,rank(6)= 3,rank(7)= 4,rank(8)= 5.

在我们看来,在上述时间复杂性约束下,问题不能通过两个映射的组合来解决,一个按键排序,另一个按排序排序.

谢谢.

我们给出了具有N个节点(从0到N-1编号)和精确(N-1)双向边缘的图G(V,E).

图中的每条边具有正成本C(u,v)(边缘权重).

整个图形使得任何节点对之间存在唯一的路径.

我们还给出了一个节点号的列表L,在该列表中放置了炸弹.

我们的目标是从图形中损坏/移除边缘,使得在图形中损坏/移除边缘之后,炸弹之间没有连接 -

这是后损坏,有任何两弹一星之间没有路径.

损坏边缘的成本(u,v) = 边缘重量(u,v).

因此,我们必须损坏这些边缘,以便总损坏成本最小.

例:

Total Nodes=N=5 
Total Bomb=Size of List L=3

List L={2,4,0}//Thats is at node number 2,4 and 0 bomb is placed...

Total Edges =N-1=4 edges are::

u v Edge-Weight

2 1 8

1 0 5

2 4 5

1 3 4



In this case the answer is ::
Total Damaging cost =(Edge Weight …

我正在努力使Brian's Fold for Bianary Trees(http://lorgonblog.wordpress.com/2008/04/06/catamorphisms-part-two/)适用于Multiway树.

摘自Brian的博客:

数据结构:

type Tree<'a> =  
    | Node of (*data*)'a * (*left*)Tree<'a> * (*right*)Tree<'a>  
    | Leaf 

let tree7 = Node(4, Node(2, Node(1, Leaf, Leaf), Node(3, Leaf, Leaf)),  
                    Node(6, Node(5, Leaf, Leaf), Node(7, Leaf, Leaf)))

二叉树折叠功能

let FoldTree nodeF leafV tree =   
    let rec Loop t cont =   
        match t with   
        | Node(x,left,right) -> Loop left  (fun lacc ->    
                                Loop right (fun racc ->   
                                cont (nodeF x lacc racc)))   
        | Leaf -> cont leafV   
    Loop …

我想弄清楚当节点溢出时到底发生了什么.info:在我的b +树中,每个块有4个指针和3个数据部分.问题:我明白当有溢出时我们分成2个节点,在我的情况下每个都有2个键,并插入父节点的中间值,而不从儿子中删除(与b树不同).

但是我遇到了这种情况:

                                |21|30|50|

           |10|20|-|      |21|22|25|  |30|40|-| |50|60|80|  

我想首先插入键23我分裂| 21 | 22 | 25 | 成:| 21 | 22 | - | 和| 23 | 25 | - | 现在我需要将键23插入父| 21 | 30 | 50 | 巫婆导致另一个分裂.| 21 | 23 | - | 和| 30 | 50 | - | 但是指向30之前的指针在哪里？是否有可能这个指针和23之后的指针指向| 23 | 25 | - | ？

我想问一问，在插入新节点期间，是否有人知道一种存储从根节点到多路树的新节点的路径的有效方法。例如，如果我有以下树：

对于每个节点，我目前通过以下方式存储从根节点到根节点的路径的数组，方法是通过int为每个深度相同的子代分配一个唯一的ID：

Root node -> [1]

Depth 1, child 1 of root -> [1, 1]
Depth 1, child 2 of root -> [1, 2]

Depth 2, child 1 of parent 1 -> [1, 1, 1]
Depth 2, child 2 of parent 1 -> [1, 1, 2]
Depth 2, child 3 of parent 1 -> [1, 1, 3]
Depth 2, child 1 of parent 2 -> [1, 2, 4]
Depth 2, child 2 of parent 2 -> [1, 2, …