二叉树排序算法
2017-05-31 本文已影响0人
简单的名字吧
QQ图片20170531140512.png
真的是写了好久
其中算法绕死人~
不过静下心来好好地一步一步研究，然后写出来还是非常有成就感滴O(∩_∩)O~~
接下来把代码记录下来以便自己后来再回顾~
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8">
</head>
<style type="text/css">
.OrgBox{
font-size:12px;
padding:5px 5px 5px 5px;
clear:left;
float:left;
text-align:center;
position:absolute;
}
.OrgBox div{
color:#FFA500;
font-weight:800;
}
</style>
<script type="text/javascript">
function offset(node){
var x = node.offsetLeft;
var y = node.offsetTop;
var w = node.offsetWidth;
var h = node.offsetHeight;
var parent = node.offsetParent;
while (parent != null){
x += parent.offsetLeft;
y += parent.offsetTop;
parent = parent.offsetParent;
}
if(w==0){
w+=parseInt(node.currentStyle.width);
w+=parseInt(node.currentStyle.paddingRight);
w+=parseInt(node.currentStyle.paddingLeft);
w+=parseInt(node.currentStyle.borderWidth) * 2;
}
if(h==0){
h+=parseInt(node.currentStyle.height);
h+=parseInt(node.currentStyle.paddingTop);
h+=parseInt(node.currentStyle.paddingBottom);
h+=parseInt(node.currentStyle.borderWidth) * 2;
}
return {x: x, y: y, w: w, h: h};
}
function OrgNode(){
this.Text=null;
this.Link=null;
this.Description=null;
this.BoxWidth=null;
this.BoxHeight=null;
this.parentNode=null;
this.NodeGroupId=null; //同一层的级别序号,从零开始
this.NodeOrderId=null; //同一级中的序号,从零开始
this.TopLine=null;
this.BottomLine=null;
this.Depth=null;
this.Top=null;
this.Left=null;
this.Type=null;
this.Nodes=[];
this.customParam=[]; //节点自定义参数
var This=this;
this.Nodes.Add=function(OrgNode_){
OrgNode_.parentNode=This;
This.Nodes[This.Nodes.length]=OrgNode_;
}
this.Box=null;
this.Templet=null;
this.Id="OrgNode_"+ GetRandomId(20);
this.inIt= function(parent){
if(this.inIted==true)return;
var tempDiv=document.createElement("DIV");
parent.appendChild(tempDiv);
var tempHTML=this.Templet;
tempHTML=tempHTML.replace("{Id}", this.Id);
tempHTML=tempHTML.replace("{Text}", this.Text);
for(var Param_ in this.customParam){
tempHTML=tempHTML.replace("{"+ Param_ +"}", this.customParam[Param_]);
}
tempDiv.innerHTML=tempHTML;
this.Box=document.getElementById(this.Id);
if(this.BoxWidth!=null){
if(offset(this.Box).w < this.BoxWidth){
this.Box.style.width=this.BoxWidth +"px";
if(offset(this.Box).w > this.BoxWidth){
this.Box.style.width=(this.BoxWidth - (offset(this.Box).w - this.BoxWidth)) +"px";
}
}
}
if(this.BoxHeight!=null){
if(offset(this.Box).h < this.BoxHeight){
this.Box.style.height=this.BoxHeight +"px";
if(offset(this.Box).h > this.BoxHeight){
this.Box.style.height=(this.BoxHeight - (offset(this.Box).h - this.BoxHeight)) +"px";
}
}
}
this.Width=offset(this.Box).w;
this.Height=offset(this.Box).h;
this.inIted=true;
}
function GetRandomId(n_){
var litter="abcdefghijklmnopqrstuvwxyz"
litter+=litter.toUpperCase()
litter+="1234567890";
var idRnd="";
for(var i=1; i<=n_; i++){
idRnd+=litter.substr((0 + Math.round(Math.random() * (litter.length - 0))), 1)
}
return idRnd;
}
}
function OrgShow(OrgNode_){
this.parent=document.body;
this.LineSize=2;
this.LineColor="#000000";
this.IntervalWidth=100;
this.IntervalHeight=50;
this.Top=0;
this.Left=0;
this.Depth=0;
this.Nodes=[];
this.DepthGroup=[]; //this.DepthGroup[n].Nodes 层深节点集合
//this.DepthGroup[n].NodeGroups[m] 层深节点按上层分类集合 this.DepthGroup[n].NodeGroups[m][k]层深节点
var This=this;
this.BoxWidth=null;
this.BoxHeight=null;
this.BoxTemplet=null;
this.ShowType=null;
this.Run=function(){
BoxInit(OrgNode_, this.parent);
GetDepth(OrgNode_);
SetDepthsHeight()//设置层深高度
//***************************
for(var n=1; n<=this.Depth; n++){//设置顶距离
var tempTop=this.Top + GetDepthHeightToRoot(n);
var tempNodes=this.DepthGroup[n].Nodes;
for(var m=0; m<tempNodes.length; m++){
tempNodes[m].Top=tempTop;
}
}
//***************************
for(var n=this.Depth; n>=1; n--){//设置左距离
var DepthNodes=this.DepthGroup[n].Nodes;
if(n==this.Depth){
for(var m=0; m<DepthNodes.length; m++){
if(m==0){
DepthNodes[m].Left=0;
}else{
DepthNodes[m].Left=DepthNodes[m-1].Left + DepthNodes[m-1].Width + this.IntervalWidth;
}
}
}else{
for(var m=0; m<DepthNodes.length; m++){
if(DepthNodes[m].Nodes.length!=0){
var tempNodeLeft_=DepthNodes[m].Nodes[0].Left + (GetGroupWidthByNode(DepthNodes[m].Nodes[0]) / 2);
tempNodeLeft_-=(DepthNodes[m].Width / 2);
DepthNodes[m].Left = tempNodeLeft_;
}
}
for(var m=0; m<DepthNodes.length; m++){
if(DepthNodes[m].Left==null){
SetLeftByDepthNode(DepthNodes, m, "LTR");
}
}
}
}
SetDepthGroupWidth();//设置群组宽度
var MaxLeftValue=this.Nodes[0].Left;
for(var n=1; n<this.Nodes.length; n++){//取得最小左距离
if(MaxLeftValue>this.Nodes[n].Left){
MaxLeftValue=this.Nodes[n].Left;
}
}
MaxLeftValue=(-MaxLeftValue) + this.Left;
for(var n=0; n<this.Nodes.length; n++){//重新设置距离
this.Nodes[n].Left+=MaxLeftValue;
this.Nodes[n].Box.style.left=this.Nodes[n].Left + "px"
this.Nodes[n].Box.style.top=this.Nodes[n].Top + "px"
}
//***************************
for(var n=1; n<=this.Depth; n++){//设置竖线条
var tempNodes=this.DepthGroup[n].Nodes;
for(var m=0; m<tempNodes.length; m++){
if(n!=this.Depth){//设置底线条
if(tempNodes[m].Nodes.length!=0){
var tempLineLeft=tempNodes[m].Left + (tempNodes[m].Width / 2);
var tempLineHeight=((this.IntervalHeight - this.LineSize) / 2);
tempLineHeight+=(this.DepthGroup[n].Height - tempNodes[m].Height);
var tempLineTop=tempNodes[m].Top + tempNodes[m].Height;
var tempBottomLine=new CreateLine(2, tempLineTop, tempLineLeft, tempLineHeight, this.LineSize, this.LineColor, "LineBottom_"+ tempNodes[m].Id, this.parent);
tempNodes[m].BottomLine=tempBottomLine.Line;
}
}
if(n!=1){//设置顶线条
var tempLineLeft=tempNodes[m].Left + (tempNodes[m].Width / 2);
var tempLineHeight=((this.IntervalHeight - this.LineSize) / 2);
var tempLineTop=tempNodes[m].Top - tempLineHeight;
if(this.DepthGroup[tempNodes[m].Depth].NodeGroups[tempNodes[m].NodeGroupId].length==1){//如果只有一个节点
var tempBottomLineHeight=parseFloat(tempNodes[m].parentNode.BottomLine.style.height) + this.LineSize;
tempNodes[m].parentNode.BottomLine.style.height=(tempLineHeight + tempBottomLineHeight)+"px";
}else{
var temptopLine=new CreateLine(2, tempLineTop, tempLineLeft, tempLineHeight, this.LineSize, this.LineColor, "LineTop_"+ tempNodes[m].Id, this.parent);
tempNodes[m].TopLine=temptopLine.Line;
}
}
}
}
for(var n=2; n<=this.Depth; n++){//设置横线条
var tempNodeGroups_=this.DepthGroup[n].NodeGroups;
for(var m=0; m<tempNodeGroups_.length; m++){
if(tempNodeGroups_[m].length!=1){
var tempLineWidth=tempNodeGroups_[m].Width - (tempNodeGroups_[m][0].Width / 2) + this.LineSize;
tempLineWidth-=(tempNodeGroups_[m][tempNodeGroups_[m].length-1].Width / 2);
var tempLineTop=tempNodeGroups_[m][0].Top - ((this.IntervalHeight - this.LineSize) / 2) - this.LineSize;
var tempLineLeft=tempNodeGroups_[m][0].Left + (tempNodeGroups_[m][0].Width / 2);
var tempGroupLine=new CreateLine(1, tempLineTop, tempLineLeft, tempLineWidth, this.LineSize, this.LineColor, "LineGroup_"+ tempNodeGroups_[m][0].Id, this.parent);
}
}
}
}
function GetGroupWidthByNode(Node_){//根据群组中任一节点，取得群组宽度
var tempNodesGroup_=This.DepthGroup[Node_.Depth].NodeGroups[Node_.NodeGroupId];
var tempGroupWidth_=tempNodesGroup_[tempNodesGroup_.length-1].Left - tempNodesGroup_[0].Left;
tempGroupWidth_+=tempNodesGroup_[tempNodesGroup_.length-1].Width
return tempGroupWidth_;
}
function SetLeftByDepthNode(DepthNodes_, NodeId, Type){
if(Type=="LTR"&&NodeId==DepthNodes_.length-1){
SetLeftByDepthNode(DepthNodes_, NodeId, "RTL");
return;
}
if(Type=="RTL"&&NodeId==0){
SetLeftByDepthNode(DepthNodes_, NodeId, "LTR");
return;
}
var FindIndex=null;
if(Type=="LTR"){
for(var r_=NodeId+1; r_<DepthNodes_.length; r_++){
if(DepthNodes_[r_].Left!=null){
FindIndex=r_;
break;
}
}
if(FindIndex==null){
SetLeftByDepthNode(DepthNodes_, NodeId, "RTL");
return;
}else{
for(var r_=FindIndex-1; r_>=NodeId; r_--){
DepthNodes_[r_].Left=DepthNodes_[r_+1].Left - This.IntervalWidth - DepthNodes_[r_].Width;
}
}
}
if(Type=="RTL"){
for(var r_=NodeId-1; r_>=0; r_--){
if(DepthNodes_[r_].Left!=null){
FindIndex=r_;
break;
}
}
if(FindIndex==null){
SetLeftByDepthNode(DepthNodes_, NodeId, "LTR");
return;
}else{
for(var r_=FindIndex+1; r_<=NodeId; r_++){
DepthNodes_[r_].Left=DepthNodes_[r_-1].Left + This.IntervalWidth + DepthNodes_[r_-1].Width;
}
}
}
}
function GetDepthHeightToRoot(DepthId){//取得距离顶层的高度
var tempHeight_=0;
for(var x_=DepthId; x_>=1; x_--){
tempHeight_+=This.DepthGroup[x_].Height;
}
tempHeight_+=This.IntervalHeight * (DepthId - 1);
tempHeight_-=This.DepthGroup[DepthId].Height;
return tempHeight_;
}
function SetLeftPosByChildNode(Node_, ChildNode_){//根据下级节点位置设置节点位置
var tempNodeGroups=This.DepthGroup[ChildNode_.Depth].NodeGroups[ChildNode_.NodeGroupId];
var tempNodeLeft;
if(tempNodeGroups.length==1){
tempNodeLeft=((ChildNode_.Width / 2) + ChildNode_.Left) - (Node_.Width / 2);
}else{
tempNodeLeft=GetFirstLeftPos(ChildNode_) + (tempNodeGroups.Width / 2) - (Node_.Width / 2);
}
Node_.Left=tempNodeLeft;
}
function GetFirstLeftPos(Node_){//根据节点位置取得同一级中首个节点位置
if(Node_.NodeOrderId==0){//Node_为首节点
return Node_.Left;
}
var tempWidth=0;
for(var k_=0; k_<=Node_.NodeOrderId; k_++){
var tempGroupsNode=This.DepthGroup[Node_.Depth].NodeGroups[Node_.NodeGroupId][k_];
tempWidth+=tempGroupsNode.Width;
}
tempWidth+=(Node_.NodeOrderId * This.IntervalWidth);
return ((Node_.Left - tempWidth) + (Node_.Width / 2));
}
function ChildNodesWidth(OrgObj){//取得层宽
var ReWidth=0;
for(var s_=0; s_<OrgObj.Nodes.length; s_++){
ReWidth+=OrgObj.Nodes[s_].Width;
}
ReWidth+=(OrgObj.Nodes.length-1) * This.IntervalWidth;
return ReWidth;
}
function SetDepthGroupWidth(){//设置层深宽度
for(var n_=1; n_<=This.Depth; n_++){
var tempNodeGroups=This.DepthGroup[n_].NodeGroups;
for(var m_=0; m_<tempNodeGroups.length; m_++){
tempNodeGroups[m_].Width=GetGroupWidthByNode(tempNodeGroups[m_][0]);
}
}
}
function SetDepthsHeight(){//设置层深高度
for(var n_=1; n_<=This.Depth; n_++){
var tempNodes_=This.DepthGroup[n_].Nodes;
var MaxHeight=0;
for(var m_=0; m_<tempNodes_.length; m_++){
if(tempNodes_[m_].Height>MaxHeight){
MaxHeight=tempNodes_[m_].Height;
}
}
This.DepthGroup[n_].Height=MaxHeight;
}
}
function GetDepth(OrgObj){//取得层深,层群集
This.Nodes[This.Nodes.length]=OrgObj;
OrgObj.Depth=(This.Depth==0)?This.Depth+1:OrgObj.parentNode.Depth+1;
This.Depth=(OrgObj.Depth>This.Depth)?OrgObj.Depth:This.Depth;
if(typeof(This.DepthGroup[OrgObj.Depth])!="object"){
This.DepthGroup[OrgObj.Depth]=[];
This.DepthGroup[OrgObj.Depth].Nodes=[];
This.DepthGroup[OrgObj.Depth].NodeGroups=[];
}
This.DepthGroup[OrgObj.Depth].Nodes[This.DepthGroup[OrgObj.Depth].Nodes.length]=OrgObj;
if(OrgObj.Depth==1){
This.DepthGroup[OrgObj.Depth].NodeGroups[0]=[];
This.DepthGroup[OrgObj.Depth].NodeGroups[0][0]=OrgObj;
OrgObj.NodeGroupId=0;
OrgObj.NodeOrderId=0;
}else{
if(This.DepthGroup[OrgObj.Depth].NodeGroups.length==0){
This.DepthGroup[OrgObj.Depth].NodeGroups[0]=[];
This.DepthGroup[OrgObj.Depth].NodeGroups[0][0]=OrgObj;
OrgObj.NodeGroupId=0;
OrgObj.NodeOrderId=0;
}else{
var GroupsLength=This.DepthGroup[OrgObj.Depth].NodeGroups.length;
var GroupNodesLength=This.DepthGroup[OrgObj.Depth].NodeGroups[GroupsLength-1].length;
if(OrgObj.parentNode==This.DepthGroup[OrgObj.Depth].NodeGroups[GroupsLength-1][GroupNodesLength-1].parentNode){
This.DepthGroup[OrgObj.Depth].NodeGroups[GroupsLength-1][GroupNodesLength]=OrgObj;
OrgObj.NodeGroupId=GroupsLength-1;
OrgObj.NodeOrderId=GroupNodesLength;
}else{
if(typeof(This.DepthGroup[OrgObj.Depth].NodeGroups[GroupsLength])!="object"){
This.DepthGroup[OrgObj.Depth].NodeGroups[GroupsLength]=[];
}
GroupNodesLength=This.DepthGroup[OrgObj.Depth].NodeGroups[GroupsLength].length;
This.DepthGroup[OrgObj.Depth].NodeGroups[GroupsLength][GroupNodesLength]=OrgObj;
OrgObj.NodeGroupId=GroupsLength;
OrgObj.NodeOrderId=GroupNodesLength;
}
}
}
if(OrgObj.Nodes.length!=0){
for(var n=0; n<OrgObj.Nodes.length; n++){
GetDepth(OrgObj.Nodes[n]);
}
}
}
function BoxInit(OrgObj_, Parent_){//节点初始化
OrgObj_.Templet=GetBoxTemplet();
OrgObj_.BoxWidth=This.BoxWidth;
OrgObj_.BoxHeight=This.BoxHeight;
OrgObj_.inIt(Parent_);
if(OrgObj_.Nodes.length!=0){
for(var n=0; n<OrgObj_.Nodes.length; n++){
BoxInit(OrgObj_.Nodes[n], Parent_);
}
}
}
function GetBoxTemplet(){//取得节点模板
if(This.BoxTemplet!=null)return This.BoxTemplet;
var TempletStr="<div id=\"{Id}\" style=\"font-size:12px;padding:5px 5px 5px 5px;border:thin solid blue;background-color:lightgrey; clear:left;float:left;text-align:center;position:absolute;"
TempletStr+="\"></div>";
return TempletStr;
}
function CreateLine(type_, top_, left_, long_, size_, color_, id_, parent_){
this.Type=type_;
top_=top_+"";
left_=left_+"";
long_=long_+"";
this.Top=(top_.substr(top_.length-2).toLowerCase()!="px")?top_+"px":top_;
this.Left=(left_.substr(left_.length-2).toLowerCase()!="px")?left_+"px":left_;
this.Long=(long_.substr(long_.length-2).toLowerCase()!="px")?long_+"px":long_;
this.Size=(size_==undefined)?"1px":size_+"";
this.Id=(id_==undefined)?null:id_;
this.Size=(this.Size.substr(this.Size.length-2).toLowerCase()!="px")?this.Size+"px":this.Size;
this.Color=(color_==undefined)?"#000000":color_;
this.Line=document.createElement("DIV");
parent_.appendChild(this.Line);
this.Line.innerText="x";
this.Line.style.position="absolute";
this.Line.style.top=this.Top;
this.Line.style.left=this.Left;
this.Line.style.overflow="hidden";
if(this.Type==1){
this.Line.style.borderTopColor=this.Color;
this.Line.style.borderTopWidth=this.Size;
this.Line.style.borderTopStyle="solid";
this.Line.style.width=this.Long;
this.Line.style.height="0px";
}else{
this.Line.style.borderLeftColor=this.Color;
this.Line.style.borderLeftWidth=this.Size;
this.Line.style.borderLeftStyle="solid";
this.Line.style.height=this.Long;
this.Line.style.width="0px";
}
if(this.Id!=null)this.Line.id=this.Id;
}
}
function showChildNode(child){
var b=new OrgNode();
b.customParam.title = child.title;
if(child.children && child.children.length){
for(var i=0;i<child.children.length;i++){
b.Nodes.Add(showChildNode(child.children[i]));
}
}
return b;
}
function paintContactOrganization(dataArr, container){
var a=new OrgNode();
a.customParam.title = dataArr.title;
if(dataArr.children && dataArr.children.length){
for(var i=0;i<dataArr.children.length;i++){
a.Nodes.Add(showChildNode(dataArr.children[i]));
}
}
var OrgShows=new OrgShow(a);
OrgShows.parent = container||document.body; //设置父容器
OrgShows.Top=50; //设置顶距离
OrgShows.Left=50; //设置左距离
OrgShows.IntervalWidth=20; //设置节点间隔宽度
OrgShows.IntervalHeight=60; //设置节点间隔高度
OrgShows.ShowType=1; //设置节点展示方式 1横向 2竖向
OrgShows.BoxHeight=30; //设置节点默认高度
//OrgShows.BoxWidth=100; //设置节点默认宽度
var TempletStr="<div id=\"{Id}\" style=\"font-size:13px;padding:15px 15px 15px 15px;border:15px thin outset #7f8183;border-radius:10px;background-color:#bae0e3; clear:left;float:left;text-align:center;position:absolute;"
TempletStr+="\"><div style=\"line-height:20px;\">{title}</div></div>";
OrgShows.BoxTemplet = TempletStr;
OrgShows.Run();
}
</script>
<body>
<div id="tree" style="position: relative;width: 100%;margin: 0 auto;"></div>
<script language="javascript" type="text/javascript">
var arr = {
id:1,
title:"这是脑袋 ",
children:[
{
id:11,
title:"节点1.1",
children:[
{
id:111,
title:"子节点1.1_1",
children:[
{
id:1111,
title:"子节点1.1.1_1"
},
{
id:1112,
title:"子节点1.1.1_2"
}
]
},
{
id:112,
title:"子节点1.1_2",
children:[
{
id:1121,
title:"子节点1.1.2_1"
},
{
id:1122,
title:"子节点1.1.2_2"
}
]
}
]
},
{
id:12,
title:"节点1.2",
children:[
{
id:121,
title:"子节点1.2_1"
},
{
id:122,
title:"子节点1.2_2",
children:[
{
id:1221,
title:"子节点1.2.2_1"
},
{
id:1222,
title:"子节点1.2.2_2"
}
]
}
]
},
]
}
paintContactOrganization(arr, document.querySelector("#tree"));
</script>
</body>
</html>
一步一步缕清楚就好啦加油
