SOURCE

// 根据当前节点的index获取所有子节点的index
var getAllChildrenIndexByParentIndex = function (nodes, index) {
    var indexs = [];
    for (var i = 0; index >= 0 && nodes[index].cTag && i < nodes[index].cTag.length; i++) {
        for (var j = 0; j < nodes.length; j++) {
            if (nodes[j].pTag[0] == nodes[index].cTag[i]) {
                indexs.push(j);
            }
        }
    }
    return indexs;
};

var getParentNodeIndexByChildIndex = function (nodes, cIndex) {
    for (var i = 0; cIndex >= 0 && i < nodes.length; i++) {
        var cTags = nodes[i].cTag;
        for (var j = 0; cTags && j < cTags.length; j++) {
            if (cTags[j] == nodes[cIndex].pTag[0]) {
                return i;
            }
        }
    }
    return -1;
};

// 初始化数据
var formatData = function (data) {
    data = data.n;
    var nodes = [];
    for (var i = 0; i < data.length; i++) {
        var tmpNode = {};
        tmpNode.index = i;
        if (data[i].c) {
            tmpNode.cTag = data[i].c;
        }
        tmpNode.pTag = [];
        tmpNode.pTag.push(data[i].p[0]);
        tmpNode.pTag.push(data[i].p[1]);
        nodes.push(tmpNode);
    }
    nodes[0].depth = nodes[0].yOffset = nodes[0].xOffset = 0;
    for (var i = 0; i < nodes.length; i++) {
        if (nodes[i].cTag) {
            for (var j = 0; j < nodes[i].cTag.length; j++) {
                var indexs = getAllChildrenIndexByParentIndex(nodes, i);
                var firstChild = nodes[indexs[0]];
                firstChild.xOffset = parseInt(nodes[i].xOffset) - 135 * (indexs.length - 1);
                firstChild.depth = parseInt(nodes[i].depth) + 1;
                firstChild.yOffset = parseInt(firstChild.depth) * 180;
                for (var k = 0; k < indexs.length; k++) {
                    // 设置depth、yOffset
                    nodes[indexs[k]].depth = firstChild.depth;
                    nodes[indexs[k]].yOffset = firstChild.yOffset;
                    // 设置xOffset
                    nodes[indexs[k]].xOffset = firstChild.xOffset + 270 * k;
                    // 设置rn
                    if (indexs.length > 1 && k < indexs.length - 1) {
                        nodes[indexs[k]].rn = nodes[indexs[k + 1]].pTag[0];
                    }
                    // 设置ln
                    if (indexs.length > 1 && k > 0) {
                        nodes[indexs[k]].ln = nodes[indexs[k - 1]].pTag[0];
                    }
                }
            }
        }
    }
    return nodes;
};

// 将数分层，保存对应节点的index
var getSortedLayers = function (nodes) {
    var layerMap = new Map();
    for (var i = 0; i < nodes.length; i++) {
        if (layerMap.has(nodes[i].depth)) {
            var tmpStr = layerMap.get(nodes[i].depth) + "," + i;
            layerMap.set(nodes[i].depth, tmpStr);
        } else {
            layerMap.set(nodes[i].depth, i + "");
        }
    }
    var layers = [];
    layerMap.forEach(function (value) {
        var layer = value.split(",");
        for (var i = 0; i < layer.length; i++) {
            layer[i] = parseInt(layer[i]);
        }
        layers.push(layer);
    });
    return layers;
};

// 查找所有子节点中，每一行最左边的节点，结果保存在firstLeftNodeMap中
var getAllChildDepth = function (nodes, node, firstLeftNodeMap) {
    if (node.cTag) {
        var childIndex = getAllChildrenIndexByParentIndex(nodes, node.index);
        var firstChild = nodes[childIndex[0]];
        if (!firstLeftNodeMap.has(firstChild.depth)) {
            firstLeftNodeMap.set(firstChild.depth, firstChild.index);
        }
        for (var i = 0; i < childIndex.length; i++) {
            getAllChildDepth(nodes, nodes[childIndex[i]], firstLeftNodeMap);
        }
    }
};

// 查找节点的平行节点的子节点，找出每一行最左边的节点,结果保存在firstLeftNodeMap中
var getAllBrotherDepth = function (nodes, node, firstLeftNodeMap) {
    var parentIndex = getParentNodeIndexByChildIndex(nodes, node.index);
    var brotherIndex = getAllChildrenIndexByParentIndex(nodes, parentIndex);
    if (brotherIndex.length > 1) {
        for (var i = 1; i < brotherIndex.length; i++) {
            getAllChildDepth(nodes, nodes[brotherIndex[i]], firstLeftNodeMap);
        }
    }
};

// 递归平移节点本身、节点平行节点右边的节点，父节点、父节点平行节点右边节点……
var moveParentRight = function (nodes, node, distance, layers) {
    var depth = node.depth;
    var layerIndexs = layers[depth];
    // node所在层的序号
    var index = layerIndexs.indexOf(node.index);
    // node所在行右移
    for (var i = index; i < layerIndexs.length; i++) {
        nodes[layerIndexs[i]].xOffset = parseInt(nodes[layerIndexs[i]].xOffset) + distance;
    }
    var pNodeIndex = getParentNodeIndexByChildIndex(nodes, node.index);
    // 平移节点本身以及所有父节点、父节点平行节点
    if (pNodeIndex != -1) {
        moveParentRight(nodes, nodes[pNodeIndex], distance, layers);
    }
};

// 当前节点的所有兄弟节点的子节点、子节点的子节点右移
var moveAllChildrenRight = function (nodes, node, distance, layers) {
    var firstLeftNodeMap = new Map();
    getAllChildDepth(nodes, node, firstLeftNodeMap);
    getAllBrotherDepth(nodes, node, firstLeftNodeMap);
    firstLeftNodeMap.forEach(function(value,key){
        var depth = parseInt(key);
        var layer = layers[depth];
        var index = parseInt(firstLeftNodeMap.get(key));
        var layerIndex = layer.indexOf(index);
        for (var i = layerIndex; i < layer.length; i++) {
            nodes[layer[i]].xOffset = nodes[layer[i]].xOffset + distance;
        }
    });
};

var getleftSpace = function (nodes, nodeIndex, layer) {
    var layerIndex = layer.indexOf(nodeIndex);
    if (layerIndex == 0) {
        return Math.pow(10, 4);
    } else {
        return nodes[layer[layerIndex]].xOffset - nodes[layer[layerIndex - 1]].xOffset;
    }
};

var amendAlign = function (nodes, layers) {
    for (var i = 0; i < layers.length; i++) {
        var layer = layers[i];
        for (var j = 0; layer && j < layer.length; j++) {
            if (nodes[layer[j]].cTag && nodes[layer[j]].cTag.length > 1) {
                var childrenIndexs = getAllChildrenIndexByParentIndex(nodes, layer[j]);
                var firstChildIndex = childrenIndexs[0];
                var lastChildIndex = childrenIndexs[childrenIndexs.length-1];
                var tmpXoffset = (nodes[lastChildIndex].xOffset + nodes[firstChildIndex].xOffset)/2;
                var distance = nodes[layer[i]].xOffset - tmpXoffset;
                if (distance > 0 && distance < getleftSpace(nodes, layer[j], layer)) {
                    nodes[layer[j]].xOffset = tmpXoffset;
                }
            }
        }
    }
};

var amendXoffset = function (nodes) {
    var layers = getSortedLayers(nodes);
    var minXoffset = 0;
    for (var i = layers.length - 1; i >= 0; i--) {
        var layer = layers[i];
        // 比较每一行最左边的节点的xOffset，获取整个树最左边的xOffset
        minXoffset = Math.min(parseInt(nodes[layer[0]].xOffset), minXoffset);
        for (var j = 0; j < layer.length - 1; j++) {
            var distance = nodes[layer[j + 1]].xOffset - nodes[layer[j]].xOffset;
            if (distance < 270) {
                distance = 270 - distance;
                // 平行节点及父节点右移
                moveParentRight(nodes, nodes[layer[j + 1]], distance, layers);
                // 子节点及平行节点右移
                moveAllChildrenRight(nodes, nodes[layer[j + 1]], distance, layers);
            }
        }
    }
    if (minXoffset < 0) {
        nodes.forEach(function (node) {
            node.xOffset = parseInt(node.xOffset) + Math.abs(minXoffset);
        });
    }
    amendAlign(nodes,layers);
};

var getResponse = function (data) {
    var nodes = formatData(data);
    var response = {};
    amendXoffset(nodes);
    for (var i = 0; i < nodes.length; i++) {
        var tmpObject = {};
        tmpObject.p = [nodes[i].xOffset, nodes[i].yOffset, 250, 120];
        if (nodes[i].ln) {
            tmpObject.ln = nodes[i].ln;
        }
        if (nodes[i].rn) {
            tmpObject.rn = nodes[i].rn;
        }
        response[nodes[i].pTag[0]] = tmpObject;
    }
    return response;
};