在 canvas 中绘制二叉树时节点重叠

Question

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

当我说"the x axis and y axis position"时，我指的是二叉树中节点的排列方式，我会尽量用图例来解释清楚：

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

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

我以这种方式拥有组件，因为在服务器端，对是在遍历二叉树时形成的（当我走进当前节点的 child 时，我将 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

有点老套，但这似乎行得通。然而，节点可能会部分重叠，具体取决于 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);
    });
});

编辑：我现在才看到这并没有实现拆分效果，很难继续拆分很多行，文本 space 每次都减半。

在 canvas 中绘制二叉树时节点重叠

Nodes overlapping while drawing a binary tree in canvas

html

javascript

tree

canvas