任务目的
- 熟练JavaScript
- 学习树这种数据结构的基本知识
任务描述
- 基于上个任务，将二叉树变成了多叉树，并且每一个节点中带有内容
- 提供一个按钮，显示开始遍历，点击后，以动画的形式呈现遍历的过程
- 当前被遍历到的节点做一个特殊显示（比如不同的颜色）
- 每隔一段时间（500ms，1s等时间自定）再遍历下一个节点
- 增加一个输入框及一个“查询”按钮，点击按钮时，开始在树中以动画形式查找节点内容和输入框中内容一致的节点，找到后以特殊样式显示该节点，找不到的话给出找不到的提示。查询过程中的展示过程和遍历过程保持一致
整体思路
这里首先也采用面向过程的思路，实现对多叉树的遍历，这里利用深度优先模拟了前中后序遍历，同时也实现了广度优先遍历，也可以利用这四种方式进行查询。
首先是利用div模拟多叉树，同时添加四个按钮和一个文本框用来进行不同的遍历和查询。
<div id="tree_wrap">
Super
<div>
Cat
<div>
Apple
<div>Pear</div>
<div>Pig</div>
<div>Cola</div>
<div>Soccer</div>
</div>
<div>
Phone
</div>
<div>
<div>Book</div>
<div>School</div>
</div>
</div>
<div>
Note
<div>
Human
<div>Code</div>
<div>Operate</div>
<div>Man</div>
</div>
<div>
Program
<div>
Bement
<div>Cat</div>
</div>
<div>Glass</div>
</div>
</div>
<div>
Fish
</div>
</div>
<input type="text" id="searchValue">
<button id="dlr">深度优先模拟前序遍历</button>
<button id="ldr">深度优先模拟中序遍历</button>
<button id="lrd">深度优先模拟后序遍历</button>
<button id="bfs">广度优先遍历</button>
<span>文本框为空时只进行遍历。如果需要搜索，请在文本框中输入要查询的内容</span>
把上面提到的四种遍历算法写出来，在进行广度遍历时，添加一个临时数组，模拟队列进行广度遍历。
//深度优先模拟前序
function dlr(node){
// console.log(node.children[0]);
if(node){
nodeArray.push(node);
if(node.children){
for(var i=0;i<node.children.length;i++){
dlr(node.children[i]);
}
}
}
}
//深度优先模拟中序
function ldr(node){
if(node){
ldr(node.firstElementChild);
nodeArray.push(node);
for(var i=1;i<node.children.length;i++){
ldr(node.children[i]);
}
}
}
//深度优先模拟后序
function lrd(node){
if(node.children){
for(var i=0;i<node.children.length;i++){
lrd(node.children[i]);
}
}
nodeArray.push(node);
}
//广度优先
function bfs(node){
var temp = [];
if(node){
temp.push(node);
}
while(temp.length){
node = temp.shift();
nodeArray.push(node);
if(node.children){
for(var i=0;i<node.children.length;i++){
temp.push(node.children[i]);
}
}
}
}
然后把按钮与不同的算法相关联
//按钮handler
function btnHandler(){
if(isRun){
alert("等会儿");
}else{
var tree = $("#tree_wrap");
var id = event.target.id;
switch(id){
case 'dlr':
dlr(tree);
break;
case 'ldr':
ldr(tree);
break;
case 'lrd':
lrd(tree);
break;
case 'bfs':
bfs(tree);
break;
}
renderData();
}
}
//初始化函数
function init(){
var btns = document.getElementsByTagName("button");
for(var i=0;i<btns.length;i++){
addHandler(btns[i],"click",btnHandler);
}
var searchInput = $("#searchValue");
searchInput.addEventListener("focus",function(e){
e.target.value = "";
});
}
在最后的渲染函数中，在原来的基础上，根据input中是否为空来判断是否需要查询。
var isRun = false;
//渲染数据
function renderData(){
var value = $("#searchValue").value.trim();
//清除查询标记的颜色
for(var i=0;i<nodeArray.length;i++){
// nodeArray[i].style.color = "#000";
nodeArray[i].classList.remove("searched");
}
var timer = null,i=0,isSeached = false;
timer = setInterval(run,500);
function run(){
isRun = true;
if(i<nodeArray.length){
if(i-1 > -1){
//清除上一个节点的背景色
// nodeArray[i-1].className = "";
nodeArray[i-1].classList.remove("selected");
}
// nodeArray[i].className = "selected";
nodeArray[i].classList.add("selected");
//判断是否在进行查询
if(value){
var nodeValue = nodeArray[i].firstChild.nodeValue.trim();
if(value == nodeValue){
// nodeArray[i].style.color = "red";
nodeArray[i].classList.add("searched");
isSeached = true;
}
}
i++;
}else{
//清除最一个节点的背景色
// nodeArray[i-1].className = "";
nodeArray[i-1].classList.remove("selected");
//判断是否被找到
if(value && !isSeached){
alert("没有找到");
}
nodeArray = [];
isRun = false;
clearInterval(timer);
return;
}
}
}