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

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

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

 

一： 思想

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

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

 

二：场景

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

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

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

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

 

三：举例

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

 来说吧，首先上图：

 

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

 

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

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

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

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

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

    

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

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

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

 

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

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

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

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

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

 head 

 title /title 

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

 script type="text/javascript" 

 $(document).ready(function () {

 var zNodes = [

 { id: 1, pId: 0, name: ".Net技术" },

 { id: 2, pId: 0, name: "编程语言" },

 { id: 3, pId: 0, name: "软件设计" },

 { id: 4, pId: 1, name: ".Net新手区" },

 { id: 5, pId: 1, name: "Asp.Net" },

 { id: 6, pId: 1, name: "C#" },

 { id: 7, pId: 1, name: "WinForm" },

 { id: 8, pId: 4, name: ".Net码畜区" },

 { id: 9, pId: 2, name: "Java" },

 var setting = ["id", "pId"];

 //第一步： 转化数据结构模型

 var result = ToForest(zNodes, setting);

 var mynode = " ul " + GetNodes(result) + " /ul 

 $("body").append(mynode);

 var html = "";

 //第二步:深度优先(这里面的html格式可以自己更改)

 function GetNodes(result) {

 for (var i = 0; i result.length; i++) {

 html += " li " + result[i].name;

 if (result[i].childs != undefined) {

 html += " ul 

 GetNodes(result[i].childs);

 html += " /ul 

 html += " /li 

 return html;

 //setting的格式:[ID，Name，PID]

 function ToForest(sNodes, setting) {

 var i, l,

 //主键ID

 key = setting[0];

 //parentID

 parentKey = setting[1];

 //childs

 childsKey = "childs";

 //参数检查

 if (!key || key == "" || !sNodes)

 return [];

 if ($.isArray(sNodes)) {

 //存放森树形式的数据模型

 var r = [];

 //存放以ID为key，ID对应的实体为value

 var tmpMap = [];

 //赋值操作

 for (i = 0; i sNodes.length; i++) {

 //获取当前的id

 var id = sNodes[i][key];

 tmpMap[id] = sNodes[i];

 //对json逐层遍历确定层级关系

 for (i = 0; i sNodes.length; i++) {

 //获取当前的pid

 var pid = sNodes[i][parentKey];

 //判断是否是顶级节点

 if (tmpMap[pid]) {

 //判断该节点是否有孩子节点

 if (!tmpMap[pid][childsKey])

 tmpMap[pid][childsKey] = [];

 //将此节点放在该节点的孩子中

 tmpMap[pid][childsKey].push(sNodes[i]);

 } else {

 //如果是顶级节点直接存放

 r.push(sNodes[i]);

 return r;

 } else {

 return [sNodes];

 /script 

 /head 

 body 

 /body 

 /html 

 

算法刷题第十天：递归 / 回溯--1 时间复杂度：O(n+m)，其中 n 和 m 分别为两个链表的长度。因为每次循环迭代中，l1 和 l2 只有一个元素会被放进合并链表中， 因此 while 循环的次数不会超过两个链表的长度之和。所有其他操作的时间复杂度都是常数级别的，因此总的时间复杂度为 O(n+m)。
【算法题解】 Day30 搜索与回溯 今天的算法是 「搜索与回溯」 相关，“算法题解系列文章旨在精选重点与易错的算法题，总结常见的算法思路与可能出现的错误，以实战习题的形式理解算法，使用算法。”
【算法题解】 Day29 搜索与回溯 今天的算法是 「搜索与回溯」 相关，“算法题解系列文章旨在精选重点与易错的算法题，总结常见的算法思路与可能出现的错误，以实战习题的形式理解算法，使用算法。”
【算法题解】 Day23 搜索与回溯 今天的算法是 「搜索与回溯」 相关，“算法题解系列文章旨在精选重点与易错的算法题，总结常见的算法思路与可能出现的错误，以实战习题的形式理解算法，使用算法。”
【算法题解】 Day22 搜索与回溯 今天的算法是 「搜索与回溯」 相关，“算法题解系列文章旨在精选重点与易错的算法题，总结常见的算法思路与可能出现的错误，以实战习题的形式理解算法，使用算法。”