关于增量树的设计

[Metaz]

树型结构在网页设计中常常会使用到，一般作为导航用。

增量树的概念：树型结构的每层节点是在父节点被第一次展开时从服务器下载；第一层上的节点在初始化树时下载。

网页中的树型结构完全是脚本驱动的，增量树要和服务器交互，如果页面重构，树也将被重构，展开每一级的时候，因此需要禁止页面重构，我们需要通过xmlhttp与服务器交互。树型结构有自己的事件，节点单击，双击，展开等。
一个完整的树型结构，包括 展开，收起图片
‘田’，‘曰’
，有节点图片，用以区分叶子和分支。还有线条，垂直线和水平线。树要能应用到实际开发中，每一个节点需要提供编号，标题属性，并通提供这些属性被外部访问的事件（如：单击，双击）。
xmlhttp的部分没有适用prototype.js
的ajax，本人借鉴了一下buffalo。

为便于大家参考学习之用，本人提供Metastree.js源码：

/*
Author :wzh
Description :Tree Navigator
Note :need prototype.js suported
*/
var Metastree = Class.create();
var MetasTreeNode = Class.create();
Metastree.version = '1.0.0.0';
Metastree.CLAZZ = 'METASTEE';
Metastree.getElementById = function(elementId){return $(elementId);}

Metastree.OpenImg = 'node_open.gif';
Metastree.CloseImg = 'node_close.gif';
Metastree.LeafImg = 'leaf.gif';
Metastree.FolderImg = 'folder.gif';
Metastree.ExpandImg = 'node_expand.gif';
Metastree.ExpandImg_ = 'node_expand_.gif';
Metastree.CollapseImg = 'node_collapse.gif';
Metastree.CollapseImg_ = 'node_collapse_.gif';
Metastree.WaitingImg = 'waiting.gif';

Metastree.line_L = 'L.gif'
Metastree.line_T = 'T.gif';
Metastree.line_I = 'I.gif';
Metastree.line__ = '__.gif';
Metastree.ROOT = 'METAS_TREE_V001';
function getXmlHttpPrefix() {
if (getXmlHttpPrefix.prefix)
return getXmlHttpPrefix.prefix;

var prefixes = ["MSXML2", "Microsoft", "MSXML", "MSXML3"];
var o;
for (var i = 0; i < prefixes.length; i++) {
try {
// try to create the objects
o = new ActiveXObject(prefixes[i] + ".XmlHttp");
return getXmlHttpPrefix.prefix = prefixes[i];
}
catch (ex) {};
}

throw new Error("Could not find an installed XMLHttp object");
}

function XmlHttp() {}

XmlHttp.create = function () {
try {
// NS & MOZ
if (window.XMLHttpRequest) {
var req = new XMLHttpRequest();
if (req.readyState == null) {
req.readyState = 1;
req.addEventListener("load", function () {
req.readyState = 4;
if (typeof req.onreadystatechange == "function")
req.onreadystatechange();
}, false);
}

return req;
}
// IE
if (window.ActiveXObject) {
return new ActiveXObject(getXmlHttpPrefix() + ".XmlHttp");
}
}
catch (ex) {}
// Fail
throw new Error("Your browser does not support XmlHttp objects");
};

function XmlDocument() {}
function getDomDocumentPrefix() {
if (getDomDocumentPrefix.prefix)
return getDomDocumentPrefix.prefix;
var prefixes = ["MSXML2", "Microsoft", "MSXML", "MSXML3"];
var o;
for (var i = 0; i < prefixes.length; i++) {
try {
o = new ActiveXObject(prefixes[i] + ".DomDocument");
return getDomDocumentPrefix.prefix = prefixes[i];
}
catch (ex) {};
}
throw new Error("Could not find an installed XML parser");
}
XmlDocument.create = function () {
try {
if (document.implementation &&
document.implementation.createDocument) {
var doc = document.implementation.createDocument("", "", null);
if (doc.readyState == null) {
doc.readyState = 1;
doc.addEventListener("load", function () {
doc.readyState = 4;
if (typeof doc.onreadystatechange == "function")
doc.onreadystatechange();
}, false);
}

return doc;
}
if (window.ActiveXObject)
return new ActiveXObject(getDomDocumentPrefix() + ".DomDocument");
}
catch (ex) {}
throw new Error("Your browser does not support XmlDocument objects");
};

if (window.DOMParser &&
window.XMLSerializer &&
window.Node && Node.prototype && Node.prototype.__defineGetter__) {

Document.prototype.loadXML = function (s) {

var doc2 = (new DOMParser()).parseFromString(s, "text/xml");

while (this.hasChildNodes())
this.removeChild(this.lastChild);
for (var i = 0; i < doc2.childNodes.length; i++) {
this.appendChild(this.importNode(doc2.childNodes[i], true));
}
};

Document.prototype.__defineGetter__("xml", function () {
return (new XMLSerializer()).serializeToString(this);
});
};

Metastree.prototype = {
initialize:
function(containerId,marginLeft,marginTop,imgPath,hasCheckBox,serverName,events){
this.container = Metastree.getElementById(containerId);
this.marginLeft = parseInt(marginLeft);
this.marginTop = parseInt(marginTop);
this.imgPath = imgPath;
this.serverName = serverName;
this.currentNode = null;
this.setTreeEvents(events);
this.initTree();
this.nodes = new Array();
this.downloadChildren();
this.root = new
MetasTreeNode(this,Metastree.ROOT,Metastree.ROOT,'',-1,0,events,false);
},
onWaiting: function(tree,state){
var msgPanel = $('WaitingPanel');
if(!msgPanel){
msgPanel = document.createElement('DIV');
msgPanel.setAttribute('id','WaitingPanel');
var pos = getPosition(tree.container);
pos[0]+=parseInt(tree.container.offsetHeight/2);
pos[1]+=parseInt(tree.container.offsetWidth/2);
msgPanel.style.cssText =
'background-color:transparent;position:absolute;z-index:1000;left:' +
pos[1] + 'px;top:'
+ pos[0] +'px;';
msgPanel.innerHTML = "<img border=0 style='display:" +
state?"":"none" + " src='"+tree.imgPath+"/"+ Metastree.WaitingImg +"'>"
;
tree.msgPanel = msgPanel;
}else{
if(tree.msgPanel.childNodes[0]){
tree.msgPanel.childNodes[0].style.display = state?'':'none';
}
}
},
response : function() {
if(this.transport.status == '200') {
var data = this.transport.responseText;
var xmlDoc = XmlDocument.create();
xmlDoc.async=false;
this.events["onWaiting"](this,false);
xmlDoc.loadXML(data);
var root = xmlDoc.documentElement;
var nodeList = root.getElementsByTagName("node");
var node;
var myTree = this;
var inlineIndex =
myTree.currentNode?myTree.getInlineIndex(myTree.currentNode.nodeId) :
-1;
var size = nodeList.length;
for(var i = 0; i < size; i++) {
node = nodeList[i];
var treeNode =
new MetasTreeNode(myTree,
myTree.currentNode,
node.getAttribute("nodeId"),
node.getAttribute("nodeTitle"),
++inlineIndex,
parseInt(node.getAttribute("childrenCnt")),
myTree.events,
(i != size-1),
node.getAttribute("nodeImg") || null);
myTree.nodes[treeNode.nodeId] = treeNode;
myTree.appendNode(treeNode);
}
} else {
this.events["onException"](this.transport.responseText);
}
},
getContainerId : function(){
return this.container.id;
},
initTree: function(){
if(!this.mainPanel){
var panel = document.createElement('DIV');
this.container.appendChild(panel);
panel.style.cssText =
'z-index:80;width:100%;height:100%;margin-left: '+this.marginLeft+'px;'
+ 'margin-top: ' + this.marginTop + 'px';
this.mainPanel = document.createElement('TABLE');
panel.appendChild(this.mainPanel);
this.mainPanel.style.cssText =
'width:100%;z-index:90;table-layout:fixed';
this.mainPanel.border=0;
this.mainPanel.cellPadding = 0;
this.mainPanel.cellSpacing = 0;
}
},
setTreeEvents: function(events) {
this.events = {
onWaiting: this.onWaiting,
onFinish: new Function(),
onException: new Function(),
onError: new Function()
};
Object.extend(this.events, events || {});
},
clearAll : function(){
var size = this.mainPanel.rows.length;
for(var e = size -1 ; e>=0; e-- ){
this.mainPanel.deleteRow(e);
}
for(e in this.nodes){
this.nodes[e] = null;
}
},
updateNode: function(nodeId){
},
getNodeById: function(nodeId){
return this.nodes[nodeId];
},
getInlineIndex: function(nodeId){
for(var e = this.mainPanel.rows.length-1;e>=0;e--){
if(nodeId == this.mainPanel.rows[e].getAttribute('nodeId')){
return e;
}
}
return -1;
},
collapseChildren: function(nodeId,flag){
var idx = -1;
for(var e = 0;e<this.mainPanel.rows.length;e++){
if(nodeId == this.mainPanel.rows[e].getAttribute("nodeId")){
idx = e;
break;
}
}
if(-1 != idx){
var node = this.nodes[nodeId];
var e= idx + 1;
var cnt = idx + node.childrenCnt;
while(e <= cnt){
if(e>=this.mainPanel.rows.length)
break;
this.mainPanel.rows[e].style.display = (flag?'none':'');
node =
this.nodes[this.mainPanel.rows[e].getAttribute('nodeId')];
if(node && node.childrenCnt > 0 && node.expanded &&
node.downloaded){
cnt += node.childrenCnt;
}
e++;
}
}
},
downloadChildren:function(nodeId){
this.transport = XmlHttp.create();
this.transport.open("GET", this.serverName + '?parent=' +
(nodeId?nodeId:''), true);
this.transport.send('');
this.transport.onreadystatechange = this.onStateChange.bind(this);
},
onStateChange: function(){
if (this.transport.readyState == 4) {
this.response();
}
},
appendNode: function(node){
var r = this.mainPanel.insertRow(node.inlineIdx);
r.valign = 'center';
r.height = '20px';
r.setAttribute('nodeId',node.nodeId);
var c = r.insertCell(-1);
var l = node.layerLevel;
var nodeHeader = '';
var p = node;
while(l>0){
p = p.parentNode;
if(!p)break;
if(p.hasNextSibling){
nodeHeader = '<img border=0 src="'+this.imgPath
+'/'+Metastree.line_I+'"
style="margin-top:0px;margin-bottom:-3px;background-color:transparent">'
+ nodeHeader;
}else{
nodeHeader = '<span style="width:21px;"><img src="" border=0
style="height:1px;width:21px;"></span>' + nodeHeader;
}
l--;
}
c.innerHTML = nodeHeader + c.innerHTML;
c.appendChild(node.nodeExpandImg);
c.appendChild(node.titleContent);
},
appendChild : function(parentId,newId,newTitle,childrenCnt){
var parent = this.getNodeById(parentId);
var inlineIndex = parent?this.getInlineIndex(parentId):0;
if(!parent)
parent = this.root;
var myLastChild = parent.lastChild();
if(myLastChild)myLastChild.hasNextSibling = true;
var node =
new MetasTreeNode(this,
parent,
newId,
newTitle,
childrenCnt+inlineIndex,
childrenCnt,
false,
this.events);
this.nodes[newId] = node;
var r =
this.mainPanel.insertRow(parent.getChildrenCnt()+inlineIndex);
r.valign = 'center';
r.height = '20px';
r.setAttribute('nodeId',newId);
var c = r.insertCell(-1);
var l = node.layerLevel;
var nodeHeader = '';
var p = node;
while(l>0){
p = p.parentNode;
if(!p)break;
if(p.hasNextSibling){
nodeHeader = '<img border=0 src="'+this.imgPath
+'/'+Metastree.line_I+'"
style="margin-top:0px;margin-bottom:-3px;background-color:transparent">'
+ nodeHeader;
}else{
nodeHeader = '<span style="width:21px;"><img src="" border=0
style="height:1px;width:21px;"></span>' + nodeHeader;
}
l--;
}
c.innerHTML = nodeHeader + c.innerHTML;
c.appendChild(node.nodeExpandImg);
c.appendChild(node.titleContent);
parent.childrenCnt ++;
parent.expanded = true;
parent.downloaded = true;
},
getChildren: function(nodeId){
var ret = [];
for(var e in ret){
var temp = this.nodes[e];
if(temp.parentNode && nodeId == temp.parentNode.nodeId )
ret.push(temp);
}
return ret.sort(this.sortNode);
},
exchangePosition:function(nodeId1,nodeId2){
var idx1 = nodeId1.inlineIdx;
nodeId1.inlineIdx = nodeId2.inlineIdx;
nodeId2.inlineIdx = idx1;
},
sortNode: function(o1,o2){
return o1.inlineIdx - o2.inlineIdx;
},
expandNodeEvent : function(nodeId){
alert(nodeId);
}
};

MetasTreeNode.prototype = {
initialize:
function(tree,parent,nodeId,nodeTitle,inlineIdx,childrenCnt,events,hasNextSibling,nodeImg){
if(!parent){
parent = tree.root;
}
if(Metastree.ROOT != parent){
this.setParent(parent);
}
this.tree = tree;
this.children=[];
this.childPosition = [];
this.nodeId=nodeId;
this.nodeTitle = nodeTitle;
this.childrenCnt = childrenCnt;
this.checked = false;
this.downloaded = false;
this.layerLevel = parent && typeof(parent)!= 'string'
?(parent.layerLevel + 1 ): 0;
this.inlineIdx = inlineIdx;
this.setNodeEvents(events);
this.hasNextSibling = hasNextSibling;
this.nodeImg = nodeImg;
this.expanded = false;
this.downloaded = false;
this.titleContent = document.createElement('SPAN');//node text
DIV
this.nodeExpandImg = document.createElement('SPAN');
this.nodeExpandImg.style.verticalAlign = 'middle';
this.titleContent.style.verticalAlign = 'top';
var img = document.createElement('IMG');
img.border=0;
img.style.cssText =
'z-index:100;background-color:transparent;margin-top:0px;margin-bottom:-2px;';
img.src =
this.tree.imgPath+'/'
+ (this.nodeImg || (this.hasChildren()?
(this.hasNextSibling?Metastree.CollapseImg :
Metastree.CollapseImg_ )
:( this.hasNextSibling?Metastree.line_T:Metastree.line_L)));
this.nodeExpandImg.appendChild(img);
this.nodeExpandImg.appendChild(img);
img = document.createElement('IMG');
img.style.cssText =
'background-color:transparent;margin-top:0px;margin-bottom:-2px;';
img.src = this.tree.imgPath + '/' +
(this.hasChildren()?Metastree.FolderImg : Metastree.LeafImg);
img.border = 0;
this.nodeExpandImg.appendChild(img);
this.titleContent.innerHTML = '<span with=10></span><span
style="vertical-align:middle"><a href=#>'+ this.nodeTitle
+'</a></span>';
this.setTitleContent(this.titleContent,this.nodeExpandImg);
},
setParent : function(parent){
if(!parent.children[this.nodeId]){//排在最后
parent.childPosition[this.nodeId] = parent.getChildrenCnt();
}
parent.children[this.nodeId] = this;
this.parentNode = parent;
},
nextSibling : function(forward){
if(this.parentNode){
for(var e in this.parentNode.childPosition){
if(e == this.nodeId){
var pos = parseInt(this.parentNode.childPosition[e]) ;
if(forward)pos++;
else pos--;
for( var ee in this.parentNode.childPosition){
if(this.parentNode.childPosition[ee] == pos){
return this.parentNode.children[ee];
}
}
}
}
}
return null;
},
getChildrenCnt : function(){
var ret = 0;
for(var e in this.children){
if(typeof(e) == 'string')ret++;
}
return ret;
},
lastChild : function(){
if(this.parentNode){
var pos = this.getChildrenCnt()-1;
for( var ee in this.parentNode.childPosition){
if(this.parentNode.childPosition[ee] == pos){
return this.parentNode.children[ee];
}
}
}
return null;
},
hasChildren : function(){
return this.childrenCnt > 0;
},
setTitleContent: function(contentObj,imgObj,expandFlag){
this.titleContent = contentObj;
this.nodeExpandImg = imgObj;
var node_ = this;
this.titleContent.onclick = function(){
if(node_.tree.currentNode)

node_.tree.currentNode.titleContent.childNodes[1].className='';
node_.titleContent.childNodes[1].className='currentNode';
node_.tree.currentNode = node_;
node_.events['onNodeTextClick'](node_);
}
this.titleContent.ondbclick = function(){
if(node_.tree.currentNode)

node_.tree.currentNode.titleContent.childNodes[1].className='';
node_.titleContent.childNodes[1].className='currentNode';
node_.tree.currentNode = node_;
node_.events['onNodeTextDBClick'](node_);
}
if(this.hasChildren()){
this.nodeExpandImg.onclick= function(){
node_.tree.currentNode = node_;
node_.events['onNodeImgClick'](node_);
if(!node_.expanded){
if(!node_.downloaded){
node_.tree.downloadChildren(node_.nodeId);
node_.downloaded = true;
}else{
node_.tree.collapseChildren(node_.nodeId,false);
}
node_.nodeExpandImg.firstChild.src =
node_.tree.imgPath+'/'
+ (node_.nodeImg ||
(node_.hasChildren()?
(node_.hasNextSibling?Metastree.ExpandImg :
Metastree.ExpandImg_)
:(
node_.hasNextSibling?Metastree.line_T:Metastree.line_L)));
}else{
node_.tree.collapseChildren(node_.nodeId,true);
node_.nodeExpandImg.firstChild.src =
node_.tree.imgPath+'/'
+ (node_.nodeImg ||
(node_.hasChildren()?
( node_.hasNextSibling?Metastree.CollapseImg
:Metastree.CollapseImg_):(
node_.hasNextSibling?Metastree.line_T:Metastree.line_L)));
}
node_.expanded = !node_.expanded;
}
this.nodeExpandImg.ondbclick = function(){
node_.events['onNodeImgDBClick'](node_);
}
}
if(expandFlag && !this.expanded)
expandThis();
},
expandSelf: function(){
if(typeof this.nodeExpandImg.onclick == 'function')
this.nodeExpandImg.onclick();
},
setNodeEvents: function(events){
this.events = {
onNodeTextClick : MetastreeNodeDefault.onNodeTextClick,
onNodeExpandClick : MetastreeNodeDefault.onNodeExpandClick,
onNodeTextDBClick : MetastreeNodeDefault.onNodeTextDBClick,
onNodeCollapseClick : MetastreeNodeDefault.onNodeCollapseClick,
onNodeImgClick : MetastreeNodeDefault.onNodeImgClick,
onNodeImgDBClick : MetastreeNodeDefault.onNodeImgDBClick
};
Object.extend(this.events,events ||{});
}

}
MetastreeNodeDefault = {
onNodeTextClick : function(nodeId){
},
onNodeExpandClick : function(nodeId){
alert('onNodeExpandClick');
},
onNodeCollapseClick : function(nodeId){
alert('onNodeCollapseClick');
},
onNodeTextDBClick : function(nodeId){
alert('onNodeTextDBClick');
},
onNodeImgClick: function(nodeId){
alert('onNodeImgClick');
},
onNodeImgDBClick: function(nodeId){
alert('onNodeImgDBClick');
}
}

function getPosition(obj) {
var t = parseInt(obj.offsetTop)+parseInt(obj.offsetHeight);
var l = obj.offsetLeft;
while(obj = obj.offsetParent) {
t += obj.offsetTop;
l += obj.offsetLeft;
}
var pos = new Array();
pos[0] = t;
pos[1] = l;
return pos;
}