javascript - 在 Canvas 中绘制二叉树时节点重叠

Question

我正在尝试在 Canvas 上绘制二叉树。从服务器端发送表单数据。数据是:插入树的文本、x 轴上的位置、y 轴上的位置。

当我说“x轴和y轴位置”时，我指的是二叉树中节点的排列，我将尝试用图形示例尽可能清楚地解释:

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

这是:根在位置(0,0)，左子节点在位置(-1,1)(深度增加，但宽度减小。)，右子节点(1,1)等等。问题是，在某些位置，不同父节点的两个节点会重合，其中一个会与另一个重叠。

我以这种方式拥有组件，因为在服务器端，在遍历二叉树时形成对(当我走进当前节点的子节点时，我将 1 与该对的第二个组件相加；如果 child 在左边，那么我在第一个分量中剩余 1，但如果 child 在右边，我将 1 与第一个分量相加)。

我的 Canvas 代码是:

                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);

所以，问题是:我能做些什么来解决这个问题？即绘制不重叠的树。

PS:

• 我不需要库，因为我的项目是用 C++ 编写的(使用 Qt)，因此库无法工作。
• 在此示例中，我显式插入节点，即，我调用了两次 _tree.drawNode ("Node", 0,2) 方法，很明显，节点将重叠。我的意思是，我想制定一个内部方法来在这些情况下调整我的树(我不知道哪些输入将来自服务器端)。
• 如果有帮助，我可以先验地确定这棵树将有多少片叶子。

Answer 1

这有点hacky，但这似乎有效。然而，节点可能会部分重叠，具体取决于 stepX 大小和每行的节点数量。

而不是像你解释的那样使用相对定位。

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

我使用绝对定位，如下:

            (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);
    });
});

编辑:我现在发现这并没有达到分割效果，很难继续分割很多行，每次文本空间都会减半。