JS 遍历树
程序员文章站
2022-06-16 12:14:16
...
这几天一直在研究js,今天写一个关于js遍历树的JS程序:
- 关于树形结构的介绍:
一般的树形结构如下,存在着父子,兄弟关系,其实这也是一种数学模型;常见的树有:二叉树【图1】、多
叉树【图2】;
图1 | 图2 |
=====二叉树是多叉树的特例;
2. 结合上图二叉树有三种遍历方式:
前序:GDBEACF;
中序:ABDGECF;
后续:GDEBFCA;
=====在此多叉树没有左右子树之分,也就没有严格意义上的三种遍历方式,但还可以有其中前序,后续遍历;
3. 多叉树遍历的JS实现如下:
在此将上述多叉树的数据存储为JSON如下:
/**数据格式决定算法设计:*/
/**前序遍历
*/
var scanStr="";
function scan1(root){
var text = root.text;
var children = root.children;
scanStr+=text;
if(children != null)
{
for(var i in children)
scan1(children[i]);
}
}
/**后序遍历
*/
function scan2(root){
var children = root.children;
if(children != null){
for(var i in children)//扫描孩子节点
scan2(children[i]);
// scanStr+=root.text;
//}else{//是叶子节点了
// scanStr+=root.text;
}
scanStr+=root.text;
}
引申》》》》》》》》》》 树的生成方式《《《《《《《《《《《
递归的方式查询数据生成树;
以层次的方式生成树;
【生成方式也不例外,要根据给出的原数据的格式来决定采用何种方式来生成树】
引申》》》》》》》》》》树的节点移动《《《《《《《《《《《
function moveNode(root){
var children = root.children;
var attr = root.attr;
if(children != null){
for(var i in children)//扫描孩子节点
moveNode(children[i]);
if(attr == 0){
var parent = root.p;
parentRemoveNode(parent,root);//父节点先移除
var c = root.children;
if(c!=null)
parentAppendNode(parent,c);
}
}else{
if(attr == 0){
var parent = root.p;
parentRemoveNode(parent,root);//父节点先移除
var c = root.children;
if(c!=null)
parentAppendNode(parent,c);
}
}
}
//设置parentNode ;root 的parent 为Null
function setParentNode(root){
var children = root.children;
if(children != null)
{
for(var i in children){
var c = children[i];
c.p = root;
setParentNode(c);
}
}
}
/**父节点数组中删除一个节点
*/
function parentRemoveNode(parent,node){
var c = parent.children;
if(c == null)
return ;
var nodeId = node.id;
for(var i=0;i<c.length;i++){
var id = c[i].id;
if(nodeId == id){//找到了
c.splice(i,1);
// alert("移除:"+node.text+" "+node.id+" "+parent.length);
break ;//删除完毕,打断
}
}
//alert(JSON.stringify(parent));
}
/**将多个节点放到父节点下
*/
function parentAppendNode(parent,children)
{
for(var i=0;i<children.length;i++)
children[i].p = parent;//重新设置父节点
parent.children = parent.children.concat(children);//两个数组合并 //合并后重新赋值
}
关于上述代码的实例: