树形结构数据排序算法.docx

需求是把数组按照树形结构排列，假设数据是在数据库中的。最简单的思路或者说常规的思路就是递归算法了。递归算法是比较快的和准确的，但是有一个问题就是会比较浪费不必要的资源，递归算法执行的过程中会开 启N个 函数入口，也就是函数需要一直保存状态等待起递归的运算结果。例如这个树形有 5层*60行，则在递归算法中浪费的运算至少60次，并且保持5个函数一直是运算中状态，不合理的是同样要做60+次的数据库查询，因为不管其有没有子 类，算法执行过程中都需要去重复执行递归运算，事实上实际执行过程中不止这个数。可以写个简单的例子来测试递归算法调用函数的次数。/* 先假设我的数据是这样子的array( array(id=1,pid=0), array(id=2,pid=0), array(id=3,pid=2), array(id=4,pid=0), array(id=5,pid=3), array(id=6,pid=1), array(id=7,pid=1), array(id=8,pid=6), array(id=9,pid=7), array(id=10,pid=9); */$db = new MysqlDb();$num = 0;function treeArray($pid) global $db, $num; $num+; $data = $db - getAll(SELECT * FROM test_a WHERE pid = .$pid); /返回一个二维数组 $result = array(); foreach($data as $val) $valchild = treeArray($valid); $result = $val; return $result;print_r(treeArray(0); /树形的结果var_dump($num); /11然后我们系统越作越大了，数据库资源紧张了，我们要求在不改变数据库结构的同时尽可能的减少数据库的操作。那么这样做就需要我们有一算法来给你的数据排序了。$num = 0;function treeArray() global $num, $db; /操作数，数字 $data = $db - getALl(SELECT * FROM test_a WHERE 1); /获取所有数据 $result = array(); /新的数组来接受拍序好的二维数组 foreach($data as $val) /循环数组 $num+; /记录操作数 if($valpid = 0) /父节点是0 $valchild = getChild($valid, $data); /获取子节点 $result = $val; /添加到新数组中 return $result; /返回数组/*参数 父id ,二维数组*/function getChild($pid, $data) global $num; /记录数 $result = array(); /新的数组 foreach($data as $val) /遍历数组 $num+; /操作加一 if($valpid = $pid) /数组的父节点相等 $valchild = getChild($valid, $data); /获取子节点 $result = $val; /添加到新的数组 return $result; /返回结果 print_r(treeArray();var_dump($num); /110好了，我们最起码实现了不用多次请求数据库了，不过在作数组遍历的时候我们做了很多次运算然后我们的系统功能模块越来越多，其中树形结构数据这一块的调 用也特别多，程序执行速度越来越不进人意了。我们则需要设计一个速度更快，消耗资源更少的算法。这里我用了php里的变量引用，其它语言里肯定也有这种引 用方式，有些类似于C语言的指针。function treeArray() global $db; $data = $db - getAll(SELECT * FROM test_a WHERE 1); $result = array(); /定义索引数组，用于记录节点在目标数组的位置 $I = array(); foreach($data as $val) /遍历数组 if($valpid = 0) /父类为0 $i = count($result); /计算索引 $result$i = $val; /添加数组到新数组 $I$valid = & $result$i; else $i = count($I$valpidchild); $I$valpidchild$i = $val; $I$valid = & $I$valpidchild$i; return $result;申明：算法不是我原创的，