Рисование двоичного симметричного B-Tree

Question

У меня есть маленький «проект», который включает в себя рисунок Симметричного Binary B-дерева, как этот:

Но я не могу понять способ правильно вычислить положение (х, y) каждого узла. То, как Im делает это прямо сейчас, поскольку высота дерева растет, некоторые узлы имеют тенденцию перекрываться другими.

Может ли кто-нибудь дать мне некоторое представление о том, как я могу рассчитать положение узла?

Im использованием 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, очевидно, запускается из события Paint Panel.

I использует несколько переменных уровня класса:

Это дерево я построю в моих тестах; Пожалуйста, обратите внимание, что, чтобы сделать вещи немного проще, я бросил свой общий тип 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; 

Это как создается плоское дерево, используя Queue:

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-Tree максимальная ширина достигается либо в последней, либо во второй-последней строке.

Здесь я подсчитываю количество узлов в этой строке. Это дает мне ширину всего дерева, maxItemsPerRow. Процедура также устанавливает высоту как maxLevels

Теперь я первый набор Коль значения в этом широком ряду, слева направо (если присутствует в оборванных детей в последней строке.)

Тогда I переместитесь вверх по уровню на уровень и вычислите каждое значение Col как среднее между левым и правым дочерними элементами, всегда наблюдая за горизонтальными узлами.

Обратите внимание, что я предполагаю, что все горизонтальные узлы являются правильными детьми! Если это не так, вам нужно будет сделать различные адаптации как в процедурах 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). Затем измените ширину на ширину = ширина/2. Если ребенок оказывается горизонтальным, вы можете просто забыть родительскую_-1 часть и сохранить parent_Y. Затем просто повторяйте на каждом из детей головного узла. Каждый раз, когда вы опускаетесь на уровень, замените ширину на ширину/2 - эпсилон.

Надеюсь, это поможет.