树状图布局算法
2021-02-22 本文已影响0人
客昂康
TreeLayout.js：
var TreeLayout = {
//递归求左边界
f1:function(obj, array, depth){
if((typeof obj.child === "object") && (obj.child.length > 0)){
var x = obj.child[0].x;
if(typeof array[depth+1] === "undefined"){
array[depth+1] = x;
}else{
if(x < array[depth+1]){
array[depth+1] = x;
}
}
for(var i=0; i<obj.child.length; i++){
this.f1(obj.child[i], array, depth+1);
}
}
},
//递归求右边界
f2:function(obj, array, depth){
if((typeof obj.child === "object") && (obj.child.length > 0)){
var x = obj.child[obj.child.length-1].x;
if(typeof array[depth+1] === "undefined"){
array[depth+1] = x;
}else{
if(x > array[depth+1]){
array[depth+1] = x;
}
}
for(var i=0; i<obj.child.length; i++){
this.f2(obj.child[i], array, depth+1);
}
}
},
//求左边界，返回新的数组。
f3:function(obj){
var left = [];
left[0] = obj.x;
this.f1(obj, left, 0);
return left;
},
//求右边界，在旧数组上修改。
f4:function(obj, right){
right[0] = obj.x;
this.f2(obj, right, 0);
},
//通过左右边界计算偏移量
f5:function(right, left){
var number = left.length < right.length ? left.length : right.length;
var depth = left.length > right.length ? left.length : right.length;
var offset = right[0] - left[0];
for(var i=1; i<number; i++){
if(right[i]-left[i] > offset){
offset = right[i] - left[i];
}
}
return offset + 1 + (depth-1)*0.2;
},
//平移所有节点
f6:function(obj, offset){
obj.x += offset;
if((typeof obj.child === "object") && (obj.child.length > 0)){
for(var i=0; i<obj.child.length; i++){
this.f6(obj.child[i], offset);
}
}
},
//计算所有节点横向虚拟位置，稍后根据画布尺寸以及横竖要求计算所有节点真实位置。
f7:function(obj){
if((typeof obj.child === "object") && (obj.child.length > 0)){
var right = []; //右边界
for(var i=0; i<obj.child.length; i++){ //
this.f7(obj.child[i]); //
if(i>0){ //
this.f4(obj.child[i-1], right); //把前面所有子树当做整体，更新这个整体的右边界。
var left = this.f3(obj.child[i]); //取这个子树的左边界
var offset = this.f5(right, left); //左右边界比较，求这个子树的偏移量
this.f6(obj.child[i], offset); //整体移动这个子树
}
}
obj.x = (obj.child[0].x + obj.child[obj.child.length-1].x) / 2; //父节点在第一个子节点和最后一个子节点的中间。
}else{
obj.x = 0;
}
},
//计算总深度和总宽度
f8:function(obj){
var right = [];
this.f4(obj, right);
var maxW = right[0];
for(var i=1; i<right.length; i++){
if(maxW < right[i]){
maxW = right[i];
}
}
return [maxW, right.length-1];
},
//根据画布位置和尺寸以及横竖布局来确定所有节点的最终位置
f9:function(obj, depth, offsetX, offsetY, ratioW, ratioH, horizontal){
if(horizontal){
obj.y = Math.round(depth * ratioH + offsetY);
obj.x = Math.round(obj.x * ratioW + offsetX);
}else{
obj.y = Math.round(obj.x * ratioH + offsetY);
obj.x = Math.round(depth * ratioW + offsetX);
}
if((typeof obj.child === "object") && (obj.child.length > 0)){
for(var i=0; i<obj.child.length; i++){
this.f9(obj.child[i], depth+1, offsetX, offsetY, ratioW, ratioH, horizontal);
}
}
},
//横向布局
horizontal:function(obj, x, y, w, h){
this.f7(obj);
var size = this.f8(obj);
this.f9(obj, 0, x, y, w/size[0], h/size[1], true);
},
//竖向布局
vertical:function(obj, x, y, w, h){
this.f7(obj);
var size = this.f8(obj);
this.f9(obj, 0, x, y, w/size[1], h/size[0], false);
}
};
用法举例：
测试数据TreeData.js：
var treeData = {
name:"",
child:[
{
name:"",
child:[
{
name:"",
child:[
{
name:"",
child:[
{
name:"",
child:[
{name:""},
{name:""}
]
},
{
name:"",
child:[
{name:""}
]
},
{
name:"",
child:[
{name:""},
{name:""},
{name:""}
]
},
]
},
{
name:"",
child:[
{
name:"",
child:[
{name:""}
]
},
{
name:""
}
]
},
{
name:"",
child:[
{
name:"",
child:[
{name:""},
{name:""}
]
},
{
name:"",
child:[
{name:""},
{name:""},
{name:""}
]
}
]
}
]
},
{
name:"",
child:[
{
name:"",
child:[
{
name:"",
child:[
{name:""},
{name:""}
]
}
]
},
{
name:"",
child:[
{
name:"",
child:[
{name:""},
{name:""}
]
},
{
name:""
},
{
name:"",
child:[
{name:""}
]
},
]
},
{
name:"",
child:[
{
name:"",
child:[
{name:""}
]
},
{
name:"",
child:[
{name:""}
]
},
{
name:"",
child:[
{name:""},
{name:""},
{name:""},
{name:""}
]
},
]
}
]
}
]
},
{
name:"",
child:[
{name:""},
{
name:"",
child:[
{name:""},
{name:""},
{name:""},
{
name:"",
child:[
{name:""},
{name:""},
{
name:"",
child:[
{name:""}
]
}
]
}
]
},
{
name:""
},
{
name:"",
child:[
{name:""},
{
name:"",
child:[
{
name:"",
child:[
{name:""},
{name:""}
]
}
]
}
]
},
{
name:""
},
{
name:""
},
{
name:"",
child:[
{name:""},
{name:""},
{name:""},
{name:""}
]
},
{
name:""
}
]
},
{
name:"",
child:[
{
name:"",
child:[
{
name:"",
child:[
{
name:"",
child:[
{name:""},
{name:""},
{name:""},
{name:""}
]
},
{
name:"",
child:[
{name:""},
{name:""},
{name:""}
]
},
{
name:"",
child:[
{name:""},
{name:""}
]
},
]
},
{
name:"",
child:[
{
name:"",
child:[
{name:""}
]
},
{
name:""
},
{
name:""
},
]
},
{
name:"",
child:[
{
name:"",
child:[
{name:""}
]
},
{
name:"",
child:[
{name:""},
{name:""}
]
},
]
}
]
},
{
name:"",
child:[
{
name:"",
child:[
{
name:""
},
{
name:"",
child:[
{name:""},
{name:""}
]
},
{
name:""
},
]
},
{
name:"",
child:[
{
name:"",
child:[
{name:""},
{name:""}
]
},
{
name:"",
child:[
{name:""},
{name:""}
]
}
]
},
{
name:""
}
]
},
{
name:"",
child:[
{
name:"",
child:[
{
name:"",
child:[
{name:""},
{name:""}
]
},
{
name:"",
child:[
{name:""},
{name:""}
]
}
]
},
{
name:"",
child:[
{
name:"",
child:[
{name:""},
{name:""},
{name:""}
]
},
{
name:"",
child:[
{name:""},
{name:""}
]
},
{
name:""
}
]
},
{
name:"",
child:[
{
name:""
},
{
name:"",
child:[
{name:""}
]
},
{
name:""
}
]
}
]
},
{
name:"",
child:[
{
name:""
},
{
name:"",
child:[
{
name:"",
child:[
{name:""},
{name:""},
{name:""},
{name:""}
]
},
{
name:"",
child:[
{name:""},
{name:""}
]
},
{
name:"",
child:[
{name:""}
]
}
]
},
{
name:"",
child:[
{
name:"",
child:[
{name:""},
{name:""}
]
},
{
name:""
},
{
name:"",
child:[
{name:""},
{name:""}
]
}
]
}
]
}
]
}
]
};
测试程序test.html：
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>树状图布局算法测试</title>
<script src="TreeLayout.js"></script>
<script src="TreeData.js"></script>
<style>
body {
margin:0;
padding:0;
font:14px YaHei,'Microsoft YaHei',Arial,Helvetica,sans-serif;
}
#svgbox {
margin:0;
padding:0;
border:1px solid #f80;
}
</style>
</head>
<body>
<svg id="svgbox" width="1600" height="500"></svg>
</body>
<script>
var svgbox = document.getElementById("svgbox");
function drawNode(x, y){
var node = document.createElementNS("http://www.w3.org/2000/svg", "circle");
node.setAttribute("cx", x);
node.setAttribute("cy", y);
node.setAttribute("r", "7");
node.setAttribute("stroke", "#444");
node.setAttribute("stroke-width", "1.5");
node.setAttribute("fill", "#fff");
svgbox.appendChild(node);
}
function drawLine(x1, y1, x2, y2){
var line = document.createElementNS("http://www.w3.org/2000/svg", "line");
line.setAttribute("x1", x1);
line.setAttribute("y1", y1);
line.setAttribute("x2", x2);
line.setAttribute("y2", y2);
line.setAttribute("stroke", "#444");
line.setAttribute("stroke-width", "1.5");
svgbox.appendChild(line);
}
function drawTree(obj){
if(obj.child){
for(var i=0; i<obj.child.length; i++){
drawLine(obj.x, obj.y, obj.child[i].x, obj.child[i].y);
drawTree(obj.child[i]);
}
}
drawNode(obj.x, obj.y);
}
TreeLayout.horizontal(treeData, 50, 50, 1500, 400);
//TreeLayout.vertical(treeData, 50, 50, 400, 1500);
drawTree(treeData);
</script>
</html>
测试效果：
横向布局效果
