繪製對稱二進制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替換寬度。

希望這會有所幫助。