绘制对称二进制B树

Question

我有一个小“工程”涉及绘制对称二元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; 
     } 
    } 

Answer 1

这里是一个绘图程序：

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)); 
    } 
} 

其结果是：

用法：

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>>() ; 

下面是树的dimesions：

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; } 

而且我writen我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-Tree中，在最后一行或倒数第二行都会达到最大宽度。

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

现在我第一设置山口值是最宽行中，由左到右（如果存在到最后一行中晃来晃去的孩子。）

然后我逐级向上移动并计算每个Col值作为Left和Right Child之间的中间值，始终注意水平节点。

请注意，我假设所有水平节点都是正确的孩子！如果这不是真的，你将不得不在各种适应在FlatTree和setCol例程..

Answer 2

我会通过将根节点（0,0）开始（其实并不重要，你在哪里开始）。调用这一点（parent_X，parent_Y）。然后选择一个开始宽度（比如说2 ^（你树中的层数），如果你知道你的树有多少层，否则就选择任意宽度）。

左边的孩子在位置（parent_X-width/2，parent_Y-1），右边的孩子在位置（parent_X + width/2，parent_Y-1）。然后将宽度更改为width = width/2。如果孩子碰巧是水平的，你可以忘记parent_Y-1部分并保留parent_Y。然后重复每个头节点的孩子。每次向下移动一层时，用宽度/ 2 - epsilon替换宽度。

希望这会有所帮助。