绘制B树的算法

Question

绘制B树的算法

3

我正在寻找一种在C# WinForms用户控件中绘制B树的算法。我想知道是否有一些简单的算法可以用于在链接节点之间绘制线条，因为这是我的主要问题。为了绘制节点，我已经使用了Knuth算法，因为它简单且只需要一次中序遍历，并且我只需要一次遍历。我真的很感激任何资源，因为我只找到了一个需要遍历两次并需要对节点类进行大量修改的资源，而我希望避免这种情况。

我找到的唯一资源（如上所述）是http://www.cs.unc.edu/techreports/89-034.pdf，但这完全没有让我信服。

我已经有了中序遍历算法：

public void Traverse(BTree<TKey, TValue>.TraverseFunction function, ref int depth, ref int xPos)
    {
        depth++;

        int i = 0;
        for (i = 0; i < elements.Count; i++)
        {
            if (!isLeaf)
                children[i].Traverse(function, ref depth, ref xPos);

            function.Invoke(elements[i].Key, elements[i].Value, ref depth, ref xPos);
            xPos++;
        }

        if (!isLeaf)
            children[children.Count - 1].Traverse(function, ref depth, ref xPos);

        depth--;
    }

与TraverseFuction委托相匹配的绘制方法：

 private void traverseFunction(int key, string value, ref int depth, ref int xPos)
    {
        float x, y;

        x = xPos * (horizontalSpacing + horizontalSize);
        y = depth * (verticalSpacing + verticalSize);

        RectangleF rect = new RectangleF(x, y, horizontalSize, verticalSize);

        if(g.VisibleClipBounds.IntersectsWith(rect))
        {
            if(depth != treeHeight)
            {
                g.FillRectangle(Brushes.Black, x, y, horizontalSize, verticalSize);
                g.DrawString(key.ToString(), SystemFonts.DefaultFont, Brushes.Gold, x + 2, y + 2);
            }
            else
            {
                g.FillRectangle(Brushes.Red, x, y, horizontalSize, verticalSize);
                g.DrawString(key.ToString(), SystemFonts.DefaultFont, Brushes.White, x + 2, y + 2);
            }
        }

        Console.WriteLine(key + " : " + depth);
    }

它在绘制事件中传递给Tree的遍历方法，该方法在根上调用first方法。

问题是在链接节点（实际上是键）之间绘制线条。

我可以使用全局变量（控制范围）。我希望避免多次迭代和在另一个类中存储点-节点，但如果不可能，我会“去做”。

@EDIT

我决定采用这里的算法：

http://billmill.org/pymag-trees/（最底部的算法），但我无法理解它，我尝试将其转换为C＃，但卡住了。

vol = vol.left()
vor = vor.right()

由于没有解释Left()和Right()的作用，所以我认为它们返回最近的左兄弟和右兄弟，但我认为这可能不是正确的，因为当它不应该时它会给我null（从而退出应用程序）。

@EDIT 2

我已经解决了，left()基本上就是上面算法中的nextLeft()。

def nextleft(tree):
if tree.thread:   return tree.thread
if tree.children: return tree.children[0]
else:             return None

尽管我已经实现了这个算法，但我希望能得到任何“更快”的算法，因为我不真正需要那么复杂的算法，而且它也不会显示键，只会显示节点。

- pzaj

1

展示一下你目前尝试过的内容。 - Christian Kiewiet

@ChristianKiewiet 添加了代码。 - pzaj

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Good Night Nerd Pride · Accepted Answer

在函数式编程中，您需要“折叠”树：处理每个节点时，将前一个节点的结果作为处理的一部分输入。因此，请尝试在遍历节点时将父节点的位置传递给其子节点。这样，您就可以从子节点绘制一条连接到父节点的线条，而无需遍历两次。

我更改了Traverse()以接受Func:

public void Traverse<TResult>(
    Func<KeyValuePair<TKey, TValue>, TResult, int, int, TResult> traverser, 
    TResult parentResult,
    ref int depth, 
    ref int xPos)
{
    depth++;

    int i = 0;
    for (i = 0; i < elements.Count; i++)
    {
        // Traverse this node first.
        var traverseResult = traverser.Invoke(elements[i], parentResult, depth, xPos);

        // Now traverse children and pass result of own traversal.
        if (!isLeaf)
            children[i].Traverse(traverser, traverseResult, ref depth, ref xPos);

        xPos++;
    }

    if (!isLeaf)
        children[children.Count - 1].Traverse(function, traverseResult, ref depth, ref xPos);

    depth--;
}

您的 traverse 函数使用 parentPosition 来绘制一条线，并且在最后必须返回当前节点的 x 和 y 值：

private Point traverseFunction(KeyValuePair<TKey, TValue> element, Point parentPosition, int depth, int xPos)
{
    float x, y;

    x = xPos * (horizontalSpacing + horizontalSize);
    y = depth * (verticalSpacing + verticalSize);

    RectangleF rect = new RectangleF(x, y, horizontalSize, verticalSize);

    if(g.VisibleClipBounds.IntersectsWith(rect))
    {
        if(depth != treeHeight)
        {
            g.FillRectangle(Brushes.Black, x, y, horizontalSize, verticalSize);
            g.DrawString(element.Key.ToString(), SystemFonts.DefaultFont, Brushes.Gold, x + 2, y + 2);
        }
        else
        {
            g.FillRectangle(Brushes.Red, x, y, horizontalSize, verticalSize);
            g.DrawString(element.Key.ToString(), SystemFonts.DefaultFont, Brushes.White, x + 2, y + 2);
        }

        // Use the parent node's position to draw a line.
        g.DrawLine(new Pen(Color.Black, 3), parentPosition, new Point(x, y));
    }

    Console.WriteLine(key + " : " + depth);
    return new Point(x, y);
}