Как сделать чтобы вершины двоичного дерева не накладывались друг на друга?

Question

[Денис Машанов]

Всем добрый день(вечер). У меня возникла такая проблема и догадаться не могу как решить. Есть у меня двоичное дерево, если корень и его 1-ая левая и 1-ая правая вершина выводится норм(без наложений), то если например у 1-ой левой будет правая вершина, а у 1-ой правой будет левая вершина, это эти вершины друг на друга накладывается. Как сделать нормальное расстояние между вершинами, чтобы они никогда не накладывались, помогите пожалуйста.

Answer 1

[Денис Машанов]

int x = dots[index].X - (20 + (1 << (maxDepth - currentNode.depth)));
int y = dots[index].Y + 60;

или так

int x = dots[index].X - (20 * (1 << (maxDepth - currentNode.Left.depth)));
int y = dots[index].Y + 60;

Answer 2

[Станислав Макаров]

Как посчитать координаты для дерева?

Comments

[Денис Машанов]

Увы, но там нет конкретного ответа, а лишь намёки, которые увы мне не подходят.

[Станислав Макаров]

Денис Машанов

Поэтому решите задачу определения того, сколько места должны занимать дочерние узлы, включая все их дочерние узлы и т.д. Эту задачу можно решить алгоритмом ПВГ-обхода дерева, управляя стеком вершин вручную или же пользуясь рекурсивными вызовами процедуры обхода.

Это по-вашему не конкретный ответ?

[Денис Машанов]

Станислав Макаров, Да про это я знал, я хотел посмотреть как это другие реализовали чтобы не сооружать велосипед и не терять время.

[Денис Машанов]

Станислав Макаров, В итоге для каждой вершины добавил новый параметр "глубина", и да же так как-то криво выходит (со слиянием или криво), я может что не так делаю?

//пока не конец левого поддерева
if (currentNode.Left != null)
{
         int x = dots[index].X - 30 * currentNode.depth;
         int y = dots[index].Y + 40 * currentNode.depth;
         string name = currentNode.Element.ToString() + "&" + currentNode.Left.Element.ToString();
         dots.Add(new Vector2(currentNode.Left.Element, x, y)); // позиция левого элемента дерева
         GetGrafTree(currentNode.Left); // следующий левый элемент 
}
//пока не конец правого поддерева
if (currentNode.Right != null)
{
         int x = dots[index].X + 30 * currentNode.depth;
         int y = dots[index].Y + 40 * currentNode.depth;
         string name = currentNode.Element.ToString() + "&" + currentNode.Right.Element.ToString();
         dots.Add(new Vector2(currentNode.Right.Element, x, y)); // позиция правого элемента дерева
         GetGrafTree(currentNode.Right); // следующий правый элемент 
}

[Денис Машанов]

Петр, Помогите пожалуйста решить выше представленную проблему

[Станислав Макаров]

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

[Денис Машанов]

Станислав Макаров, Нет, не сбалансированно, дело в том что когда используем обход, то мы имеем ссылку на предыдущую вершину, а у предыдущей вершины есть координата, зная в какой мы вошли узел у вершины в то направление и устанавливаем новые координаты координаты, а всё начинается с 1 вершины у который статические координаты изначально.
Вот полный код

private static List<Vector2> GetGrafTree(Node<double> currentNode)
        {
            if (currentNode.depth == 1)
                dots.Add(new Vector2(currentNode.Element, (Program.getForm.Width / 2), 10, 1)); // добавить корень дерева
            int index = dots.FindLastIndex(elem => (elem.Value == currentNode.Element)); // находим вышестоящий элемент
            //пока не конец левого поддерева
            if (currentNode.Left != null)
            {
                int x = dots[index].X - (30 * currentNode.depth);
                int y = dots[index].Y + 40;
                string name = currentNode.Element.ToString() + "&" + currentNode.Left.Element.ToString();
                //lines.Add(new Line(name, dots[index].X+5, dots[index].Y+25, x+15, y));
                dots.Add(new Vector2(currentNode.Left.Element, x, y, currentNode.Left.depth)); // позиция левого элемента дерева
                GetGrafTree(currentNode.Left); // следующий левый элемент 
            }
            //пока не конец правого поддерева
            if (currentNode.Right != null)
            {
                int x = dots[index].X + (30 * currentNode.depth);
                int y = dots[index].Y + 40;
                string name = currentNode.Element.ToString() + "&" + currentNode.Right.Element.ToString();
                //lines.Add(new Line(name, dots[index].X+25, dots[index].Y+25, x+15, y));
                dots.Add(new Vector2(currentNode.Right.Element, x, y, currentNode.Right.depth)); // позиция правого элемента дерева
                GetGrafTree(currentNode.Right); // следующий правый элемент 
            }
            return dots;
        }