问题描述:

I'm trying to draw a binary tree on canvas. From the server side form data is sent. The data are: text to insert the tree, position on the x axis position on the y axis.

When I say "the x axis and y axis position", I mean the arrangement of nodes in a binary tree, I'll try to explain as clearly as possible with a graphic example:

 (0,0)

/ \

(-1,1) (1,1)

/ \ / \

(-2,2) (0,2) (0,2) (2,2)

This is: the root is in the position (0,0), the left child in the position (-1,1) (increases in depth, but decreases in width.), the right child (1,1) and so on. The problem is that in some position, two nodes of diferent parent will coincide and one of them will overlap the other.

I am having the components in this way because, in the server side, the pairs are formed while the binary tree is traversed (when I walk into a child of the current node I sum 1 to the second component of the pair; if the child is in the left, then I residue 1 in the first component, but if the child is in the right, I sum 1 to the first component).

My canvas code is:

 var TreeDrawer = (function(){

var _depth = 20

, _breadth = 15

, _rootX = width/2

, _rootY = 50

;

var _context = getContext("2d");

_context.textAlign = "center";

_context.fillStyle = "black";

_context.font = "16px Verdana";

var _getX = function (x) {

return _rootX + (x * 80);

}

var _getY = function(y) {

return _rootY + (y * 50);

}

var _drawText = function(partialText, x, y) {

console.log(x, y);

_context.fillText(partialText, x, y);

}

return {

drawRoot: function (value) {

_drawText(value, _rootX, _rootY);

},

drawNode: function(value, x, y) {

_drawText(value, _getX(x), _getY(y));

}

}

});

var _tree = new TreeDrawer();

_tree.drawRoot("Raíz");

_tree.drawNode("Nodo", -1, 1);

_tree.drawNode("Nodo", 1, 1);

_tree.drawNode("Nodo", -2, 2);

_tree.drawNode("Nodo", 0, 2);

_tree.drawNode("Nodo", 2, 2);

_tree.drawNode("Nodo", 0, 2);

So, the question is: what I can do to solve this problem ?, ie plot the tree without overlapping.

PS:

  • I do not want libraries because my project is written in C++ (using Qt), so the libraries will not work.
  • In this example I am inserting nodes explicitly, ie, I'm calling twice the _tree.drawNode ("Node", 0,2) method and it is obvious that the nodes are going to overlap. What I mean is, I want to make an internal method to adjust my tree in these situations (I do not know which will be the inputs coming from the server side).
  • If it helps, I can determine a priori how many leaves will have the tree.

网友答案:

It's a little hacky, but this seems to work. Nodes may overlap partially depending on the stepX size and the amount of nodes per row however.

Instead of using relative positioning, like you explained.

            (0,0)
            /   \
       (-1,1)     (1,1)
       /    \     /   \
   (-2,2) (0,2) (0,2) (2,2)

I'm using absolute positioning, as follows:

            (0,0)
            /   \
       (0,1)     (1,1)
       /    \     /   \
   (0,2) (1,2) (2,2) (3,2)

var TreeDrawer = (function(){
    var _depth = 15
    , _breadth = 16
    , _rootX = canvas.width/2
    , _rootY = 59
    ;

    _context.textAlign = "center";
    _context.fillStyle = "black";
    _context.font = "16px Verdana";

    var _drawText = function(partialText, x, y) {
        _context.fillText(partialText, x, y);
    }

    return {
        drawRoot: function (value) {
            _drawText(value, _rootX, _rootY);
        },
        drawNode: function(value, row, position) {
            var stepX = 56;
            var stepY = 32;
            // subtract half from x for symmetry
            var half = (Math.pow(2, row) * stepX) / 2;
            var x = _rootX + (stepX / 2) + (stepX * position) - half;
            var y = _rootY + (stepY * row);
            _drawText(value, x, y);
        }
    }
});

var _tree = TreeDrawer();
var root = "Raiz";
var rows = [
    new Array(2).fill("nodo"), 
    new Array(4).fill("nodo"), 
    new Array(8).fill("nodo"),
    new Array(16).fill("nodo")];

_tree.drawRoot(root);
rows.forEach(function (row, rowIndex) {
    row.forEach(function (node, index) {
        // the root is row zero, so I add 1 for the normal nodes.
        _tree.drawNode(node, rowIndex + 1, index);
    });
});

Edit: I just now see that this is not achieving the splitting effect, it would be hardto keep on splitting for many rows, thetext space is halving each time.

相关阅读:
Top