1

我有一个小“项目”，其中涉及绘制对称二叉 B 树，如下所示：阿达德

但我想不出一种方法来正确计算每个节点的位置（x，y）。我现在这样做的方式，随着树的高度增长，一些节点往往会被其他节点重叠。

谁能告诉我如何计算节点的位置？

我正在使用 C#，这是我现在拥有的代表节点的类：

class SBBTreeNode<T> where T : IComparable {

        public SBBTreeNode(T item) {
            Data = item;
            Left = null;
            Right = null;
        }

        public T Data { get; private set; }
        public SBBTreeNode<T> Left;
        public SBBTreeNode<T> Right;
        public bool IsHorizontal { get; set; } //Is this node horizontal?

        public bool IsLeaf() {
            return Left == null && Right == null;
        }
    }
4

2 回答 2

2

这是一个绘图例程：

void drawTree(Graphics G)
{
    if (flatTree.Count <= 0) return;
    if (maxItemsPerRow <= 0) return;
    if (maxLevels <= 0) return;
    int width = (int)G.VisibleClipBounds.Width / (maxItemsPerRow + 2);
    int height = (int)G.VisibleClipBounds.Height / (maxLevels + 2);
    int side = width / 4;
    int textOffsetX = 3;
    int textOffsetY = 5;
    int graphOffsetY = 50;
    Size squaresize = new Size(side * 2, side * 2);

    foreach (SBBTreeNode<string> node in flatTree)
    {
        Point P0 = new Point(node.Col * width, node.Row * height + graphOffsetY);
        Point textPt = new Point(node.Col * width  + textOffsetX, 
                                    node.Row * height + textOffsetY + graphOffsetY);
        Point midPt = new Point(node.Col * width + side, 
                                node.Row * height + side + graphOffsetY);

        if (node.Left != null)
            G.DrawLine(Pens.Black, midPt, 
                new Point(node.Left.Col * width + side, 
                          node.Left.Row * height + side + graphOffsetY));
        if (node.Right != null)
            G.DrawLine(Pens.Black, midPt, 
                new Point(node.Right.Col * width + side, 
                          node.Right.Row * height + side + graphOffsetY));

        G.FillEllipse(Brushes.Beige, new Rectangle(P0, squaresize));
        G.DrawString(node.Data, Font, Brushes.Black, textPt);
        G.DrawEllipse(Pens.Black, new Rectangle(P0, squaresize));
    }
}

及其结果：

b树

用法： 

flatTree  = FlatTree();
setRows();
setCols();
panel_tree.Invalidate();

现在对于导致此的各种部分：

drawTree 例程显然是由 Panel 的 Paint 事件触发的。

我使用了一些类级别的变量：

这是我在测试中构建的树；请注意，为了使事情变得更简单，我已将您的泛型类型转储T为string：

Dictionary<string, SBBTreeNode<string> > tree
        = new Dictionary<string, SBBTreeNode<string>>();

这是树的一个平面遍历副本，即它的元素按级别从左到右排序：

List<SBBTreeNode<string>> flatTree = new List<SBBTreeNode<string>>() ;

这是树的尺寸：

int maxItemsPerRow = 0;
int maxLevels = 0;

这是使用队列创建扁平树的方式：

List<SBBTreeNode<string>> FlatTree()
{
    List<SBBTreeNode<string>> flatTree = new List<SBBTreeNode<string>>();
    Queue<SBBTreeNode<string>> queue = new Queue<SBBTreeNode<string>>();

    queue.Enqueue((SBBTreeNode<string>)(tree[tree.Keys.First()]));
    flatNode(queue, flatTree);
    return flatTree;
}

这是按顺序获取节点的递归调用：

void flatNode(Queue<SBBTreeNode<string>> queue, List<SBBTreeNode<string>>flatTree)
{
    if (queue.Count == 0) return;

    SBBTreeNode<string> node = queue.Dequeue();
    if (!node.IsHorizontal) flatTree.Add(node);
    if (node.Left != null) { queue.Enqueue(node.Left); }
    if (node.Left != null && node.Left.Right != null && node.Left.Right.IsHorizontal) 
        queue.Enqueue(node.Left.Right);
    if (node.Right != null) 
    { 
        if (node.Right.IsHorizontal) flatTree.Add(node.Right);   
        else queue.Enqueue(node.Right); 
    }
    flatNode(queue, flatTree);
}

最后我们可以设置每个节点的（虚拟）坐标：

void setCols()
{
    List<SBBTreeNode<string>> FT = flatTree;
    int levelMax   = FT.Last().Row;
    int LMaxCount = FT.Count(n => n.Row == levelMax);
    int LMaxCount1 = FT.Count(n => n.Row == levelMax-1);
    if (LMaxCount1 > LMaxCount)
      { LMaxCount = LMaxCount1; levelMax = levelMax - 1; }

    int c = 1;
    foreach (SBBTreeNode<string> node in FT) if (node.Row == levelMax)
        {
            node.Col = ++c;
            if (node.Left != null) node.Left.Col = c - 1;
            if (node.Right != null) node.Right.Col = c + 1;
        }

    List<SBBTreeNode<string>> Exceptions = new List<SBBTreeNode<string>>();

    for (int n = FT.Count- 1; n >= 0; n--)
    {
       SBBTreeNode<string> node = FT[n];
       if (node.Row < levelMax)
       {
          if (node.IsHorizontal) node.Col = node.Left.Col + 1;
          else if ((node.Left == null) | (node.Right == null)) {Exceptions.Add(node);}
          else node.Col = (node.Left.Col + node.Right.Col) / 2;
       }
    }
    // partially filled nodes will need extra attention
    foreach (SBBTreeNode<string> node in Exceptions) 
                                 textBox1.Text += "\r\n >>>" + node.Data;
    maxLevels = levelMax;
    maxItemsPerRow =  LMaxCount;
}

请注意，我没有编写部分填充节点的特殊情况，只是将它们添加到异常列表中；你必须决定如何处理这些，即它们是否可以发生以及它们应该在哪里绘制。

好了，差不多了。我们还需要做两件事：

我冒昧地向您的节点类添加了两个坐标字段：

public int Row { get; set; }
public int Col { get; set; }

而且我已经编写了我的 AddNode 例程，以便每个节点的级别都在那里设置。

您肯定会想要/需要以不同的方式进行操作。一个简单的 SetRows 例程很简单，尤其是当您使用 flatTree 进行横向处理时：

void setRows()
{
    foreach (SBBTreeNode<string> node in flatTree)
    {
        if (node.Left != null)  node.Left.Row = node.Row + 1;
        if (node.Right != null) node.Right.Row = 
                                node.Row + 1 - (node.Right.IsHorizontal ? 1:0);
    }
}

解释：

除了我用于绘图的 flatTree 之外，解决方案的核心是 SetCols 例程。

在平衡的 B 树中，最大宽度在最后一行或倒数第二行达到。

在这里，我计算该行中的节点数。这给了我整个树的宽度，maxItemsPerRow。该例程还将高度设置为 maxLevels

现在我首先在最宽的行中设置 Col 值，从左到右（如果存在于最后一行中悬空的孩子）。

然后我逐级向上移动并将每个 Col 值计算为左右子节点之间的中间值，始终注意水平节点。

请注意，我假设所有水平节点都是正确的孩子！如果不是这样，您将不得不在 FlatTree 和 setCol 例程中进行各种调整。

于 2014-10-28T15:48:10.067 回答
1

我首先将根节点放在 (0,0) 处（从哪里开始并不重要）。将此点称为（parent_X，parent_Y）。然后选择一个起始宽度（比如 2^（树中的层数），如果你知道你的树有多少层，否则，只需选择任何宽度）。

左孩子在位置 (parent_X-width/2, parent_Y-1)，右孩子在位置 (parent_X+width/2, parent_Y-1)。然后将宽度更改为宽度 = 宽度/2。如果孩子恰好是水平的，您可以忘记 parent_Y-1 部分并保留 parent_Y。然后在头节点的每个子节点上重复。每次向下移动一个级别，将宽度替换为 width/2 - epsilon。

希望这可以帮助。

于 2014-10-27T18:48:51.857 回答