Графическое дерево двоичного поиска - расстояние между узлами - PullRequest
Новая
       1

Графическое дерево двоичного поиска - расстояние между узлами

0 голосов
/ 04 марта 2011

Мне трудно вычислить расстояние между узлами в двоичном дереве поиска для моего назначения.У меня реализован графический интерфейс, в котором я могу вручную создать дерево или создать его путем импорта текстового файла, а также других функций и т. Д.

В классе узла двоичного дерева поиска есть методы получения и установки для X и Yкоординаты, которые я должен использовать.Теперь у меня все работает, но это код, который я нашел в интернете.См. эту ссылку , например.

Дело в том, что я не хочу использовать этот код, потому что

  1. Это не моеи
  2. Он не использует предоставленные методы получения и установки.

Мне сказали, что для получения правильного расстояния:

Координата X пропорциональна номеру заказа, в котором узел обрабатывается в ходе обхода по порядку.

Координата Y связана с глубинойузла.

У меня есть метод getHeight(), который работает, и я предполагаю, что это то же самое, что и получение глубины.

Я надеюсь, что кто-то может помочь мне или указать мне направильное направление.

ОБНОВЛЕНИЕ

Для координат Y? 

int index = -1;
BinaryTreeNode nodes[];
int[] levels;

public void build(BinaryTreeNode node, int level)
{
    if (node != null)
    {
        build(node.getLeftNode(), level+1);
        index++;
        nodes[index] = node;
        levels[index] = level;
        build(node.getRightNode(), level+1);
    }
}

Ответы [ 2 ]

0 голосов
/ 04 марта 2011

Ось Y проста. Разложите уровни на 100 пикселей, и все готово.

Ось X сложнее.

Предположим, у вас есть 1 узел (листовой узел). Нужно, скажем, 40 пикселей (потому что 40 пикселей - это размер круга)

Предположим, у вас есть узел с двумя дочерними листами. Общая ширина = 40 * 2 + SPACING. (скажем, SPACING = 20) = 100.

Предположим, у вас есть узел третьего уровня. каждый из дочерних элементов равен 100 пикселям, поэтому 100 * 2 + SPACING = 220.

Узел 4-го уровня: 220 * 2 + 20 = 460.

узел n-го уровня: 40 * 2 ^ (n-1) + (2 ^ (n-1) - 1) * 20 = РАЗМЕР * 2 ^ (n-1) + SPACING * (2 ^ (n- 1) - 1)

0 голосов
/ 04 марта 2011

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

int y = 0;
Parent parent = child.getParent();
while(parent != null) {
   y += 10; // spacing
   y += parent.getHeight();

   parent = parent.getParent(); // next iteration
}

Однако это не очень практичный подход.Скорее, вы должны повторять уровень за уровнем - начните с верхнего узла, затем с первых двух потомков, затем с 4 внуками и так далее.Например: добавьте верхний узел в список, просмотрите список и создайте новый список для всех их дочерних элементов, затем установите новый список на старый и продолжайте в цикле while, пока список не станет пустым.

Теперь для x-позиции это более сложно, так как хороший макет зависит от количества узлов на этом конкретном уровне.Если узел три всегда является двоичным и сбалансированным, то есть 2 степени n узлов на уровень.Если нет, вы должны сначала проверить, сколько узлов на уровень.Когда закончите, просто разделите ширину экрана на количество узлов и расположите их по порядку, добавляя к координате x по мере продвижения.

РЕДАКТИРОВАТЬ: я предпочитаю такой подход: 

class BinaryTreeNode {

    BinaryTreeNode left;
    BinaryTreeNode right;

    int x;
    int y;
}

public void position(BinaryTreeNode root, int nodeHeight, int nodeWidth, int screenWidth, int screenHeight) {

    List<BinaryTreeNode> nodes = new ArrayList<BinaryTreeNode>();

    nodes.add(root);

    int level = 0;
    while(!nodes.isEmpty()) {

        // we know now the number of nodes and the level
        int y = level * nodeHeight;

        // the x position depends on the number of nodes:
        int widthPerNode = screenWidth / nodes.size();

        int x = 0; // start at leftmost

        // now have (fixed) y position and starting point for x (leftmost)
        for(BinaryTreeNode node : nodes) { // for loop iterates in-order
            node.y = y;
            node.x = x; // TODO: center node within available space

            x += widthPerNode;
        }

        // this level is complete, store all children in a list
        List<BinaryTreeNode> childNodes = new ArrayList<BinaryTreeNode>();
        for(BinaryTreeNode node : nodes) { // for loop iterates in-order
            if(node.left != null) {
                childNodes.add(node.left);
            }
            if(node.right != null) {
                childNodes.add(node.right);
            }
        }

        // continue to next level using the collected children as the new parents
        nodes = childNodes;

        level++;
    }

    // TODO: insert insets between nodes
    // TODO: insert stop criteria for y outside screen
    // TODO: insert stop criteria for x outside screen
    // TODO: getters and setters

}

Кроме того, вы можете изменить этот метод, чтобы он возвращал вам узлы, которые должны быть нарисованы, если это не входит в ваш метод paint ().

...