6

我正在尝试创建一个像节点图一样的树，就像这里的示例图像一样。我有以下代码：

    private void DrawNode(Graphics g, Node<T> node, float xOffset, float yOffset)
    {
        if (node == null)
        {
            return;
        }

        Bitmap bmp = (from b in _nodeBitmaps where b.Node.Value.Equals(node.Value) select b.Bitmap).FirstOrDefault();

        if (bmp != null)
        {
            g.DrawImage(bmp, xOffset, yOffset);

            DrawNode(g, node.LeftNode, xOffset - 30 , yOffset + 20);
            DrawNode(g, node.RightNode, xOffset + 30, yOffset + 20);
        }
    }

我的代码几乎可以工作了。我遇到的问题是一些节点重叠。在上图中，节点 25 和 66 重叠。我敢肯定，原因是因为它在数学上放置左节点和右节点的空间相等，因此父节点的右节点与相邻父节点的左节点重叠。我该如何解决这个问题？

更新：

这是我根据 dtb 的建议进行的代码更新：

            int nodeWidth = 0;
            int rightChildWidth = 0;

            if (node.IsLeafNode)
            {
                nodeWidth = bmp.Width + 50;
            }
            else
            {
                int leftChildWidth = 0;

                Bitmap bmpLeft = null;
                Bitmap bmpRight = null;

                if (node.LeftNode != null)
                {
                    bmpLeft =
                        (from b in _nodeBitmaps where b.Node.Value.Equals(node.LeftNode.Value) select b.Bitmap).
                            FirstOrDefault();
                    if (bmpLeft != null)
                        leftChildWidth = bmpLeft.Width;
                }
                if (node.RightNode != null)
                {
                    bmpRight =
                        (from b in _nodeBitmaps where b.Node.Value.Equals(node.RightNode.Value) select b.Bitmap).
                            FirstOrDefault();
                    if (bmpRight != null)
                        rightChildWidth = bmpRight.Width;
                }

                nodeWidth = leftChildWidth + 50 + rightChildWidth;
            }


            g.DrawImage(bmp, xOffset + (nodeWidth - bmp.Width) / 2, yOffset);

            if (node.LeftNode != null)
            {
                DrawNode(g, node.LeftNode, xOffset, yOffset + 20);
            }
            if (node.RightNode != null)
            {
                DrawNode(g, node.RightNode, xOffset + nodeWidth - rightChildWidth, yOffset + 20);
            }

这是此代码的屏幕截图：截屏

4

2 回答 2

5

为每个分配一个宽度node：

  • 叶子的宽度是图像的宽度，w。
  • 一个节点的宽度是它的左子节点的宽度+一个常数d+右子节点的宽度。

       插图

void CalculateWidth(Node<T> node)
{
    node.Width = 20;
    if (node.Left != null)
    {
        CalculateWidth(node.Left);
        node.Width += node.Left.Width;
    }
    if (node.Right != null)
    {
        CalculateWidth(node.Right);
        node.Width += node.Right.Width;
    }
    if (node.Width < bmp.Width)
    {
        node.Width = bmp.Width;
    }
}

从根节点 和 开始x = 0，在宽度的一半处绘制图像，偏移量为x。
然后计算x每个子节点的位置并递归：

void DrawNode(Graphics g, Node<T> node, double x, double y)
{
    g.DrawImage(x + (node.Width - bmp.Width) / 2, y, bmp);

    if (node.Left != null)
    {
        DrawNode(g, node.Left, x, y + 20);
    }
    if (node.Right != null)
    {
        DrawNode(g, node.Right, x + node.Width - node.Right.Width, y + 20);
    }
}

用法：

CalculateWidth(root);

DrawNode(g, root, 0, 0);
于 2012-04-11T00:22:23.127 回答
1

你说得对，它们会重叠。这是因为您在遍历树时向 xOffset 添加/减去一个固定值。在示例图片中，它实际上不是一个固定的偏移量：相反，它是相对于其垂直位置的对数指数。你走得越远，偏移量应该越小。

将 30s 替换为A * Math.Log(yOffset)，其中 A 是一些缩放值，您必须对其进行调整，直到它看起来正确为止。

编辑：还是指数？我无法很好地想象这些东西。你最终可能会想要A * Math.Exp(-B * yOffset)。（负面影响很大：这意味着它会随着 yOffset 变大而变小，这正是您想要的。）

A将像您的主线性比例因子一样，同时B将控制偏移变小的速度。

double A = some_number;
double B = some_other_number;
int offset = (int)(A * Math.Exp(-B * yOffset));
DrawNode(g, node.LeftNode, xOffset - offset , yOffset + 20);
DrawNode(g, node.RightNode, xOffset + offset, yOffset + 20);

更新：

double A = 75f;
double B = 0.05f;
int offset = (int)(A * Math.Exp(-B * (yOffset - 10)));
DrawNode(g, node.LeftNode, xOffset - offset, yOffset + 20);
DrawNode(g, node.RightNode, xOffset + offset, yOffset + 20);

调用：

DrawNode(e.Graphics, head, this.ClientSize.Width / 2, 10f);

Exp 中的- 10很重要：它是头部的初始 yOffset。它产生以下内容：

如果您想要精确的边距/填充控制，那么请务必使用 dtb 的方法，但我认为使用单个公式的 3 行额外的行与您将获得的数学解决方案一样优雅。

更新 2：

我还忘了一件事：我正在使用 base e = 2.7183，但你想要更接近 2 的值。从逻辑上讲，你会使用 2，但由于节点的宽度不为零，你可能需要更大的东西，比如 2.1。B您可以通过乘以更改基数Math.Log(new_base)：

double B = 0.05f * Math.Log(2.1);

我还应该解释一下我是如何得到 0.05f 的值的。基本上，树的每个级别都会增加yOffset20。yOffset如果我减去头部的初始值（在我的情况下是 10），那么我的前几个yOffsets 是 0、20、40、60 等。我希望每行的 x 偏移量减半；那是，

2 ^ (-0B) = 1
2 ^ (-20B) = 0.5
2 ^ (-40B) = 0.25

显然，B 需要为 1/20，即 0.05。我Math.Log(2.1)从关系中得到价值：

base ^ exponent == e ^ (ln(base) * exponent)

因此，使用 base 2.1，它看起来像这样：

于 2012-04-10T23:58:21.920 回答