算法洗脑系列（8篇）——第六篇回溯思想

83 阅读 0 评论 55 点赞

我是靠谱客的博主花痴航空，最近开发中收集的这篇文章主要介绍算法洗脑系列（8篇）——第六篇回溯思想，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

记得广告中经常听到过，抱着试试看的态度买了3个疗程，效果不错........ 也经常听人说过什么车到山前必有路，船到桥头自然直。

哈哈，这种思想就是回溯思想，也可称为试探思想。

一：思想

有时我们要得到问题的解，先从其中某一种情况进行试探，在试探过程中，一旦发现原来的选择是错误的，那么就退回一步重新选择，

然后继续向前试探，反复这样的过程直到求出问题的解。

二：场景

回溯思想是一个非常重要的思想，应用场景也是非常广泛。

① “下棋”：每一次走棋的位置都要考虑到是否是损人利己，如果是害人害己的走法就要回撤，找下一步损人利己的走法。

② “迷宫”：这种问题用试探法来解决相信我也不用向大家介绍了，其实迷宫问题抽象起来就是“对图的遍历问题“，当然对

图的遍历我先前的文章是有的，有兴趣的可以自己看一看。

三：举例

记得我写第一篇文章的时候有园友希望我能找些实际的项目案例，这不，今天就给大家带来了，首先就拿博客园的“网站分类”层级菜单

来说吧，首先上图：

针对这样的层级结构我们设计数据表一般都会设计成无限极分类，如下图：

那么问题来了，针对这样的数据，我们该如何在页面上呈现呢？

码农的做法就是点击一个父节点然后异步去数据库读取子节点，好一点的做法就会有人把数据放在xml里面，但是都逃避不了多次与

服务器进行交互，带来比较大的性能问题。

我们这里要讲的当然是减轻服务器的压力，页面呈现的时候直接Load出所有数据，然后序列化为Json，就如上面的图中一样，我们用

算法来解剖上面的json数据。

首先上面的json数据是由多个多叉树组成的森林，画图如下：

那么接下来如何遍历这个森林，数据结构中，森林是可以转化为二叉树的，然后采用”先序，中序或者后序”，当然对森林遍历也可以

采用“深度优先，广度优先”。

好了，分析了这么多，其实也就是二步走：

第一：将Json数据变成森林的数据结构模型。

第二：对森林进行遍历，这里就采用深度优先。


1 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

2 <html xmlns="http://www.w3.org/1999/xhtml">

3 <head>

4
<title></title>

5
<script src="Scripts/jquery-1.4.1.js" type="text/javascript"></script>

6
<script type="text/javascript">

7
$(document).ready(function () {

8 

9
var zNodes = [
 10
{ id: 1, pId: 0, name: ".Net技术" },
 11
{ id: 2, pId: 0, name: "编程语言" },
 12
{ id: 3, pId: 0, name: "软件设计" },
 13
{ id: 4, pId: 1, name: ".Net新手区" },
 14
{ id: 5, pId: 1, name: "Asp.Net" },
 15
{ id: 6, pId: 1, name: "C#" },
 16
{ id: 7, pId: 1, name: "WinForm" },
 17
{ id: 8, pId: 4, name: ".Net码畜区" },
 18
{ id: 9, pId: 2, name: "Java" },
 19
];
 20 
 21
var setting = ["id", "pId"];
 22 
 23
//第一步： 转化数据结构模型
 24
var result = ToForest(zNodes, setting);
 25 
 26
var mynode = "<ul>" + GetNodes(result) + "</ul>";
 27 
 28
$("body").append(mynode);
 29 
 30
});
 31 
 32
var html = "";
 33 
 34
//第二步:深度优先(这里面的html格式可以自己更改)
 35
function GetNodes(result) {
 36
for (var i = 0; i < result.length; i++) {
 37 
 38
html += "<li>" + result[i].name;
 39 
 40
if (result[i].childs != undefined) {
 41
html += "<ul>";
 42
GetNodes(result[i].childs);
 43
html += "</ul>";
 44
}
 45 
 46
html += "</li>";
 47
}
 48 
 49
return html;
 50
}
 51 
 52
//setting的格式:[ID，Name，PID]
 53
function ToForest(sNodes, setting) {
 54
var i, l,
 55 
 56
//主键ID
 57
key = setting[0];
 58 
 59
//parentID
 60
parentKey = setting[1];
 61 
 62
//childs
 63
childsKey = "childs";
 64 
 65
//参数检查
 66
if (!key || key == "" || !sNodes)
 67
return [];
 68 
 69
if ($.isArray(sNodes)) {
 70 
 71
//存放森树形式的数据模型
 72
var r = [];
 73 
 74
//存放以ID为key，ID对应的实体为value
 75
var tmpMap = [];
 76 
 77
//赋值操作
 78
for (i = 0; i < sNodes.length; i++) {
 79
//获取当前的id
 80
var id = sNodes[i][key];
 81 
 82
tmpMap[id] = sNodes[i];
 83
}
 84 
 85
//对json逐层遍历确定层级关系
 86
for (i = 0; i < sNodes.length; i++) {
 87 
 88
//获取当前的pid
 89
var pid = sNodes[i][parentKey];
 90 
 91
//判断是否是顶级节点
 92
if (tmpMap[pid]) {
 93
//判断该节点是否有孩子节点
 94
if (!tmpMap[pid][childsKey])
 95
tmpMap[pid][childsKey] = [];
 96
//将此节点放在该节点的孩子中
 97
tmpMap[pid][childsKey].push(sNodes[i]);
 98
} else {
 99
//如果是顶级节点直接存放
100
r.push(sNodes[i]);
101
}
102
}
103
return r;
104
} else {
105
return [sNodes];
106
}
107
}
108
</script>
109 </head>
110 <body>
111 </body>
112 </html>