位编码算法的类
时间：2007-02-17 来源：PHP爱好者
按照前段时间说过的位编码算法实现了一个类（ http://www.chinaunix.net/forum/27/20031122/207556.html ），放出来大家看看，大家帮我改进。
[code:1:0011f57be3]
<?php
Class BinTree
{
//树结构
/*************************************
example:
$Structure = array(4,7,7,7,7);
树有4层，第一层4位编码，第二、第三、第四、第五层7位编码
************************************/
var $Structure;
/// 存储树的每层信息的数组
/*************************************
//特征码
//2^N-2^(N-(N1+N2+…+Ni))
example:
$Layer = array( 层的二进制编码长度 层的特征码 每一层每节点的公差
1 => array('len' => 4, 'mark' => 4026531840, 'tolerance' => 268435456),
2 => array('len' => 7, 'mark' => 4292870144, 'tolerance' => 2097152),
3 => array('len' => 7, 'mark' => 4294950912, 'tolerance' => 16384),
4 => array('len' => 7, 'mark' => 4294967168, 'tolerance' => 128),
5 => array('len' => 7, 'mark' => 4294967295, 'tolerance' => 1)
);
*************************************/
var $Layer;
//二进制编码总长度
var $binMarkLen;
//现在用来分析的目标节点，十进制
var $_decCurrentNode;
//现在用来分析的目标节点，二进制
var $_binCurrentNode;
//CurrentNodeID的所属的层
var $_CurrentLayer;
// 初始化树
function BinTree($Structure)
{
$this->binMarkLen = array_sum($Structure);
$tmpLen = 0;
foreach ( $Structure as $k => $v )
{
$this->Layer[$k+1]['len'] = $v;
$tmpLen += $v;
$this->Layer[$k+1]['mark'] = pow(2, $this->binMarkLen) - pow(2, $this->binMarkLen - $tmpLen);
$this->Layer[$k+1]['tolerance'] = pow(2, $this->binMarkLen - $tmpLen);
}
return true;
}
// 解析当前节点
function _parseNode($Node)
{
$this->_decCurrentNode = $Node;
//节点二进制编码
$this->_binCurrentNode = FillBit(base_convert($Node, 10, 2), $this->binMarkLen);
//节点处于树的第几层
$start = 0;
foreach ( $this->Layer as $k => $v )
{
$binMark = substr($this->_binCurrentNode, $start, $v['len']);
$testMark = str_repeat('0', $v['len']);
$start += $v['len'];
if ( $binMark == $testMark )
{
$this->_CurrentLayer = $k - 1;
break;
}
$this->_CurrentLayer = count($this->Layer);
}
}
// 清除上次解析的结果
function _unparseNode()
{
$this->_decCurrentNode = null;
$this->_binCurrentNode = null;
$this->_CurrentLayer = null;
}
// 获得父节点
// 如果$all不为空则以数组格式返回所有父节点，否则仅返回上一层节点
function getParent($Node, $all = '')
{
if ( $this->_decCurrentNode != $Node )
{
$this->_parseNode($Node);
}
if ( $this->_CurrentLayer == 1 )
{
$ParentNode = 0;
}
else
{
if ( $all )
{
for ( $i = 1; $i < $this->_CurrentLayer; $i++ )
{
$ParentNode[$i] = $Node & $this->Layer[$i]['mark'];
}
}
else
{
$ParentNode = $Node & $this->Layer[$this->_CurrentLayer - 1]['mark'];
}
}
return $ParentNode;
}
// 获得下级子节点值
// 如果$j没有赋值则返回所有的子节点
function getChild($Node, $j = '')
{
if ( $this->_decCurrentNode != $Node )
{
$this->_parseNode($Node);
}
if ( $this->_CurrentLayer == count($this->Layer) )
{
return false;
}
else
{
$ChildLayer = $this->_CurrentLayer + 1;
if ( $j > 0 )
{
if ( ($j > 0 ) and ($j < pow(2, $this->Layer[$ChildLayer]['len'])) )
{
$ChildNode = $this->Layer[$ChildLayer]['tolerance'] * $j + $Node;
}
else
{
return false;
}
}
else
{
for ( $i = 1; $i < pow(2, $this->Layer[$ChildLayer]['len']); $i++ )
{
$ChildNode[] = $this->Layer[$ChildLayer]['tolerance'] * $i + $Node;
}
}
}
return $ChildNode;
}
// 得到同一层的下一个节点
function getNextNode($Node)
{
if ( $this->_decCurrentNode != $Node )
{
$this->_parseNode($Node);
}
$thisLayer = $this->_CurrentLayer;
$ParentNode = $this->getParent($Node);
$this->_unparseNode();
$j = ($Node - $ParentNode)/$this->Layer[$thisLayer]['tolerance'];
if ( $j+1 < pow(2, $this->Layer[$thisLayer]['len']) )
{
return $this->Layer[$thisLayer]['tolerance'] + $Node;
}
else
{
return false;
}
}
}
Class DBBinTree extends BinTree
{
//树实例所在的表
var $Table;
//树实例所在的字段
var $Column;
// 初始化
function DBBinTree($Structure, $table, $column)
{
parent::BinTree($Structure);
$this->Table = $table;
$this->Column = $column;
return true;
}
// 获得父节点
// 如果$all不为空则以数组格式返回所有父节点，否则仅返回上一层节点
function SelectParent($Node, $all = '')
{
global $db;
$ParentNode = $this->getParent($Node, $all);
if ( is_array($ParentNode) )
{
$sql = "select * from ". $this->Table ." where ". $this->Column ." in (". implode(',', $ParentNode) .")";
}
else
{
$sql = "select * from ". $this->Table ." where ". $this->Column ." = ". $ParentNode;
}
$rowset = $db->getAll($sql);
if ( !$db->isError($rowset) )
{
return $rowset;
}
else
{
return false;
}
}
// 获得子节点
// 如果$all不为空则以数组格式返回所有子节点，否则仅返回下一层节点
function SelectChild($Node, $all = '')
{
global $db;
$this->_parseNode($Node);
$sql = "select * from ". $this->Table ." where ". $this->Column ." > ". $Node ." and ". $this->Column ." < ". $this->getNextNode($Node);
$res = $db->query($sql);
if ( !$db->isError($res) )
{
if ( $all )
{
while ( $row = $res->fetchRow() )
{
$rowset[] = $row;
}
}
else
{
$Child = $this->getChild($Node);
while ( $row = $res->fetchRow() )
{
if ( in_array($row[$this->Column], $Child) )
{
$rowset[] = $row;
}
}
}
return $rowset;
}
else
{
return false;
}
}
}
?>
[/code:1:0011f57be3]
夜猫子 回复于：2003-11-27 11:11:21 测试数据库：
INSERT INTO bintree (binMark,decMark) VALUES ('01000000000000000000000000000000',1073741824);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000000000000000000000',1092616192);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101000000000000000',1092780032);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001110000000000',1092787200);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001110000001000',1092787208);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101100000000000000',1092796416);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000110000000000000000',1092812800);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000110100000000000000',1092829184);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000111000000000000000',1092845568);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000111100000000000000',1092861952);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001110010000000',1092787328);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001110100000000',1092787456);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001110110000000',1092787584);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001111000000000',1092787712);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001111010000000',1092787840);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001111100000000',1092787968);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001111110000000',1092788096);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001110000001001',1092787209);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001110000001010',1092787210);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001110000001011',1092787211);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001110000001100',1092787212);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001110000001101',1092787213);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001110000001110',1092787214);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001110000001111',1092787215);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001110000010000',1092787216);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101000000010000000',1092780160);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101011111110000000',1092796288);
longnetpro 回复于：2003-11-27 18:59:18 好！但是如果层数很多那怎么办呢？或是某层超过最大值？
夜猫子 回复于：2003-11-27 19:01:36 这种算法就是建立在事先规划好树的容量的基础上，层数和每层的数量事先都要有数，所以不适合那种无限分层的树
这种树结构比较死一点，我另外想了一个灵活些的树结构，打算先在我的项目里用用，如果好的话，再推荐给大家
longnetpro 回复于：2003-11-27 21:13:38 能不能透露个大概的思路？一两句就行？我也觉得用路径方式虽然灵活，但某些方面也不太方便，而且开销也大。用整数好，但是容量有限，这个矛盾怎么解决？如果只是二者其一，还好办一点，主要是要同时兼顾查询和排序。不过有一点可以肯定，在数据库里用递归查询绝对是下下之策。
夜猫子 回复于：2003-11-27 21:45:56 其实也不是什么很新鲜的主意，就是普通的树加一个辅助字段而已，是在这个问题的讨论中吸收了别人的意见的结果。
node_id parent code
1 0 01
2 1 0102
3 2 010203
我分析了一下，如果层非常多的话，位编码的方式就不可行了，因为位是不定长的，只有普通的那种树结构能够轻松满足。但是普通的那种树最大的毛病就是基于递归的遍历，所以想到加一个辅助字段来解决这个递归的毛病。
code字段其实就是路径信息，但是采用36进制，以2位为一层的话，每层可以容纳(36^2)-1也就是1295个节点，假设code字段用varchar(255)的话，可以容纳127层36^(254)-1个节点，容量非常大了，当然很少会用到这么大的树，如果真要处理这么大的树，肯定需要更好的方法。
采用36进制以后，占用的存储空间相对小，编码比较短，在采用like查询子节点的时候效率会比用低进制编码存储的路径效率要高，而且我敢肯定，效率肯定是比递归高的。并且不是每次对树的查询都需要对这个字段查询，比如只是想查上一级节点，同一层节点，下一层节点就可以直接的利用原来的方法。
这种方式适用于不能确定长度的树，我觉得一般的情况来说，我不会碰到特别大的树，一般不会超过4到5层。根据不同的情况，这两种树结合着用就差不多了。
具体怎么样，我也不好说，所以打算先写出来自己用用才真正清楚效果，既然老兄你问到了，我就说说，请指正。
longnetpro 回复于：2003-11-27 22:16:38 太好了！基本和我原来的思路相同，不过我原来是没有这个Parent字段的，现在看来这个字段还是有必要的，可以提高查询效率，因为大多数情况下只会搜索树的一个分支，先限制一下比较好，而且Parent是整型的，索引中的B树查起来也快，然后再用CODE排序——不过好象又有点问题，Parent只可能是一个子节点的父节点ID，而如果该子节点还有子节点的话，那个孙子节点的Parent就是子节点ID，这样查询的时候会不会漏掉子节点以下（孙子节点那一层及以下层）的分支呢？不知道这段话夜猫看不看得明白？如果漏了的话，那这个Parent字段好象就没有意义了。
还有，我觉得36进制编码太少，我原来试过用96进制，几乎ASCII码中非敏感字符全用都用到了。因为CODE字段主要是在排序中才用到，所以编码复杂一点没关系，一般一些别的信息多数是另有字段存贮的，如果是二合一的话，那就只好用你前面的位编码了，在综合上是一个平衡。
还有一点就是，如果定为相同长度的字符串表示一层的话会有浪费（假如用四个字符或更多），我会考虑用一个字符表示长度，后面的表示ID，类似于PASCAL中string类型的存贮模式。
不过我原来都只实现过相同长度的字符串表示一层，而且用的是十进制，所以后来才想改进。
不知道有什么意见或建议？
如果愿意的话，请加本人MSN：[email protected]，可以继续讨论，谢谢。
夜猫子 回复于：2003-11-27 22:45:41 你的意见我想想，另外我有两点要说：
采用36进制是因为我用base_convert来换算进制，最高支持到36位，再高就不晓得怎么处理了，呵呵，longnetpro教我。
另外我发觉刚才在每层节点的容量上的记算是错误的，因为node_id是在数据库里用了auto_increment来实现的，因此，node_id是不可重复的，所以，编码里肯定不会出现0101或者0a0a这样的编码，这样实际上大大的降低了每层的容量，而且树越大，这个影响越明显，所以不能处理太大的树，不同的编码长度对应的上限之间的关系我还没有计算出来，估计应该是在可接受范围内的，太大的树现在不在考虑范围。
夜猫子 回复于：2003-11-27 22:50:00 呵呵，刚发完上一个帖子就想清楚上限了。
编码的进制是m
每层编码的长度是n
那么整个树的总节点容量上限是(m^n)-1，树的层数理论上限也是(m^n)-1，所以如果要采用这种方法的话，事先也要先计划好容量的。
mikespook 回复于：2003-11-27 23:14:59 恩~~~看看~~~
能不能改成16进制编码，这样编码比较短~~~
夜猫子 回复于：2003-11-27 23:21:21 之所以有容量的限制，主要是方便解析编码，所以每层的编码长度必须定长，如果在编码路径里用特殊字符来分隔的话，每层编码的长度就不必有硬性的限制，上限也就大大增加了，理论上上限就受到code字段的存储空间限制，实际上用于很大的树的处理绝不可取，不过对于小的树，效果不错。
其实在以前的讨论中，已经有人提出这种说法，只是当时没有向这个方向上去考虑，现在看了，那位朋友说得很有道理。
有兴趣可以看看：
http://be10.ods.org/avenger/bbs/index.php?act=ST&f=2&t=3073&s=
mikespook 回复于：2003-11-27 23:56:39 如果使用哈夫曼编码，不就可以不使用定长编码了么？
longnetpro 回复于：2003-11-28 08:50:55 [quote:9bdd2d3cb5="夜猫子"]之所以有容量的限制，主要是方便解析编码，所以每层的编码长度必须定长，如果在编码路径里用特殊字符来分隔的话，每层编码的长度就不必有硬性的限制，上限也就大大增加了，理论上上限就受到code字段的存储空间限制，..........
http://be10.ods.org/avenger/bbs/index.php?act=ST&f=2&t=3073&s=
[/quote:9bdd2d3cb5]
看了这篇文章，我发现那位static的想法根本不和我的想法同路。他所提出那一系列的问题以及回答，基本上是基于select *** from table where id IN()这一SQL的，因此无法精确高效地查询遍历子树，因为他的目的主要在于从下往上的查找，不在于从上往下的查找，而遍历却恰恰是从上往下的。他其实自己被蒙住了眼睛，看不清楚。他的方法仅只能适用于查找路径，却不能很好的排序——例如找到一到某一节点的所有的子树。他所说的btree不支持范围索引这句话本身就有问题。对整数来说，只要不必计算后再索引（我们的方法从来没有说在查询的时候先计算），btree都是可以索引的，因为btree理论最初就是针对整数进行索引，也是有范围的，懂btree查找原理的人自然明白是怎么回事，而且我们索引的也只有一个变量，根本不可能有btree不支持这种方式的索引这么一说。还有他的多个字段之说，就显得有点不太可取了，明显扩展和维护问题很大，因为改数据结构的影响比改字段值的影响要大得多。其实很简单的一点就是可能他根本还没有理解我们算法的意义和工作方式。我们的要求是得到某一节点详细完整的所有的子树，而他的算法只是得到某一节点的所有父节点，但却无任何顺序，实用价值明显较低，而且效率也不一定高得太多。因此他的方法是不足取的，我认为他的数据结构及数据库原理并非理解得十分透彻，而且有点陷入思维的牛角尖了。
我们还是继续讨论树遍历的问题吧。
这样假如该字段长度为240，每层长度为10，即最多可记录达到24层，而如果每层编码用90进制数，则总容量数（不是单层容量，因为ID多数为Auto的），理论上为90^10，即 34867844010000000000。也就是说，理论上，可以对有 34867844010000000000 条记录的表做最多24层的树型记录，好象从数目上应该是够了的，前提是所有ID号必须连续。当然，这个效率问题有待考证，不过一般来说，需要被查询的子树结构不应该太复杂（试想一般不可能要你在一个页面中显示从根开始下面所有的子节点的结构，而多数是本层的下一层的子节点）。再说了，如果因为此算法的原因将递归操作变成了简单排序，你还可以分页显示，取得一个效率和效果折中的结果。
不过，还是可以肯定，整数索引比字符串索引快，因此有了路径这一思想概念之后，想法改为两者结合可能会比较好，思路还在进一步酝酿之中，应该不会太难。要注意的是：做这个类的时候，最好别牵扯到数据库的操作，最好是纯算术运算及字符串操作，完了之后形成多个SQL的参数，然后再传给专有的数据库方面的操作类进行查询，以实现模块功能的最大化。
另：在 http://www.chinaunix.net/forum/27/20031122/207556.html 我所描述的方法已与夜猫子所说的方法类似了，不过还需要改进。
夜猫子 回复于：2003-11-28 09:15:19 你的意思，我大概明白了，抽时间写出来用用看
[quote:d748186cb4="longnetpro"]做这个类的时候，最好别牵扯到数据库的操作，最好是纯算术运算及字符串操作，完了之后形成多个SQL的参数，然后再传给专有的数据库方面的操作类进行查询，以实现模块功能的最大化[/quote:d748186cb4]
我的设计思想和你差不多，就是先写一个类，仅仅负责计算，然后再继承一个或者多个子类来负责和数据库打交道，处理各种情况，不过“完了之后形成多个SQL的参数，然后再传给专有的数据库方面的操作类进行查询”的方式的确要灵活得多
longnetpro 回复于：2003-11-28 10:02:17 现帖一个代码计算八十六进制数，编码从0x31到0x7E 共94个，除掉其中的SQL及PHP的敏感字符 " ' $ _ % [ ] 等 8 个字符，可用的共86个字符，即可实现八十六进制。
[code:1:5a5306eedb]
function getTreeBaseString($excluded = ''){
$bs = '';
for($i=0x21;$i<0x7F;$i++){
$c = chr($i);
$bs .= (strpos($excluded, $c) === false)? $c : '';
}
return $bs;
}
$bs = getTreeBaseString('"'$_%[]');
echo $bs."<br>n";
define(TREE_BASE_STRING, $bs);
define(TREE_BASE_LEN, strlen(TREE_BASE_STRING));
echo TREE_BASE_LEN."<br>n";
function dec2base($v_int){
if($v_int === 0) return substr(TREE_BASE_STRING, 0, 1);
$s = '';
do{
$r = $v_int % TREE_BASE_LEN;
$s = substr(TREE_BASE_STRING, $r, 1).$s;
$v_int = floor($v_int / TREE_BASE_LEN);
}while($v_int > 0);
return $s;
}
function base2dec($v_base){
$len = strlen($v_base);
$n = 0;
for($i = 0; $i < $len; $i ++){
$index = strpos(TREE_BASE_STRING, $v_base{$i});
if($index===false) return false;
$n = $n * TREE_BASE_LEN + $index;
}
return $n;
}
$i = 354389054;
$s = dec2base($i);
echo $s."<br>n";
echo base2dec($s)."<br>n";
echo $i;
[/code:1:5a5306eedb]
中间很多的 echo 的测试代码大家自行删除即可。
longnetpro 回复于：2003-11-28 10:31:37 以上两函数dec2base及base2dec不够精确，当数值过大时不准。现用bc函数解决精度问题。
[code:1:8db107959f]
function getTreeBaseString($excluded = ''){
$bs = '';
for($i=0x21;$i<0x7F;$i++){
$c = chr($i);
$bs .= (strpos($excluded, $c) === false)? $c : '';
}
return $bs;
}
$bs = getTreeBaseString('"'$_%[]');
echo $bs."<br>n";
define(TREE_BASE_STRING, $bs);
define(TREE_BASE_LEN, strlen(TREE_BASE_STRING));
echo TREE_BASE_LEN."<br>n";
function dec2base($v_int){
if($v_int === 0) return substr(TREE_BASE_STRING, 0, 1);
$s = '';
do{
$r = bcmod($v_int, TREE_BASE_LEN);
$s = substr(TREE_BASE_STRING, $r, 1).$s;
$v_int = bcdiv($v_int, TREE_BASE_LEN, 0);
}while($v_int > 0);
return $s;
}
function base2dec($v_base){
$len = strlen($v_base);
$n = 0;
for($i = 0; $i < $len; $i ++){
$index = strpos(TREE_BASE_STRING, $v_base{$i});
if($index===false) return false;
$n = bcadd(bcmul($n, TREE_BASE_LEN), $index);
}
return $n;
}
$i = '22130157888803070975';
$s = dec2base($i);
echo $s."<br>n";
$n = base2dec(str_repeat('~', 10));
echo $n."<br>n";
echo $i;
[/code:1:8db107959f]
但这时注意两函数参数要为字符串。
非常全面的一个php技术网站,php爱好者站 http://www.phpfans.net 有相当丰富的文章和源代码.
[code:1:0011f57be3]
<?php
Class BinTree
{
//树结构
/*************************************
example:
$Structure = array(4,7,7,7,7);
树有4层，第一层4位编码，第二、第三、第四、第五层7位编码
************************************/
var $Structure;
/// 存储树的每层信息的数组
/*************************************
//特征码
//2^N-2^(N-(N1+N2+…+Ni))
example:
$Layer = array( 层的二进制编码长度 层的特征码 每一层每节点的公差
1 => array('len' => 4, 'mark' => 4026531840, 'tolerance' => 268435456),
2 => array('len' => 7, 'mark' => 4292870144, 'tolerance' => 2097152),
3 => array('len' => 7, 'mark' => 4294950912, 'tolerance' => 16384),
4 => array('len' => 7, 'mark' => 4294967168, 'tolerance' => 128),
5 => array('len' => 7, 'mark' => 4294967295, 'tolerance' => 1)
);
*************************************/
var $Layer;
//二进制编码总长度
var $binMarkLen;
//现在用来分析的目标节点，十进制
var $_decCurrentNode;
//现在用来分析的目标节点，二进制
var $_binCurrentNode;
//CurrentNodeID的所属的层
var $_CurrentLayer;
// 初始化树
function BinTree($Structure)
{
$this->binMarkLen = array_sum($Structure);
$tmpLen = 0;
foreach ( $Structure as $k => $v )
{
$this->Layer[$k+1]['len'] = $v;
$tmpLen += $v;
$this->Layer[$k+1]['mark'] = pow(2, $this->binMarkLen) - pow(2, $this->binMarkLen - $tmpLen);
$this->Layer[$k+1]['tolerance'] = pow(2, $this->binMarkLen - $tmpLen);
}
return true;
}
// 解析当前节点
function _parseNode($Node)
{
$this->_decCurrentNode = $Node;
//节点二进制编码
$this->_binCurrentNode = FillBit(base_convert($Node, 10, 2), $this->binMarkLen);
//节点处于树的第几层
$start = 0;
foreach ( $this->Layer as $k => $v )
{
$binMark = substr($this->_binCurrentNode, $start, $v['len']);
$testMark = str_repeat('0', $v['len']);
$start += $v['len'];
if ( $binMark == $testMark )
{
$this->_CurrentLayer = $k - 1;
break;
}
$this->_CurrentLayer = count($this->Layer);
}
}
// 清除上次解析的结果
function _unparseNode()
{
$this->_decCurrentNode = null;
$this->_binCurrentNode = null;
$this->_CurrentLayer = null;
}
// 获得父节点
// 如果$all不为空则以数组格式返回所有父节点，否则仅返回上一层节点
function getParent($Node, $all = '')
{
if ( $this->_decCurrentNode != $Node )
{
$this->_parseNode($Node);
}
if ( $this->_CurrentLayer == 1 )
{
$ParentNode = 0;
}
else
{
if ( $all )
{
for ( $i = 1; $i < $this->_CurrentLayer; $i++ )
{
$ParentNode[$i] = $Node & $this->Layer[$i]['mark'];
}
}
else
{
$ParentNode = $Node & $this->Layer[$this->_CurrentLayer - 1]['mark'];
}
}
return $ParentNode;
}
// 获得下级子节点值
// 如果$j没有赋值则返回所有的子节点
function getChild($Node, $j = '')
{
if ( $this->_decCurrentNode != $Node )
{
$this->_parseNode($Node);
}
if ( $this->_CurrentLayer == count($this->Layer) )
{
return false;
}
else
{
$ChildLayer = $this->_CurrentLayer + 1;
if ( $j > 0 )
{
if ( ($j > 0 ) and ($j < pow(2, $this->Layer[$ChildLayer]['len'])) )
{
$ChildNode = $this->Layer[$ChildLayer]['tolerance'] * $j + $Node;
}
else
{
return false;
}
}
else
{
for ( $i = 1; $i < pow(2, $this->Layer[$ChildLayer]['len']); $i++ )
{
$ChildNode[] = $this->Layer[$ChildLayer]['tolerance'] * $i + $Node;
}
}
}
return $ChildNode;
}
// 得到同一层的下一个节点
function getNextNode($Node)
{
if ( $this->_decCurrentNode != $Node )
{
$this->_parseNode($Node);
}
$thisLayer = $this->_CurrentLayer;
$ParentNode = $this->getParent($Node);
$this->_unparseNode();
$j = ($Node - $ParentNode)/$this->Layer[$thisLayer]['tolerance'];
if ( $j+1 < pow(2, $this->Layer[$thisLayer]['len']) )
{
return $this->Layer[$thisLayer]['tolerance'] + $Node;
}
else
{
return false;
}
}
}
Class DBBinTree extends BinTree
{
//树实例所在的表
var $Table;
//树实例所在的字段
var $Column;
// 初始化
function DBBinTree($Structure, $table, $column)
{
parent::BinTree($Structure);
$this->Table = $table;
$this->Column = $column;
return true;
}
// 获得父节点
// 如果$all不为空则以数组格式返回所有父节点，否则仅返回上一层节点
function SelectParent($Node, $all = '')
{
global $db;
$ParentNode = $this->getParent($Node, $all);
if ( is_array($ParentNode) )
{
$sql = "select * from ". $this->Table ." where ". $this->Column ." in (". implode(',', $ParentNode) .")";
}
else
{
$sql = "select * from ". $this->Table ." where ". $this->Column ." = ". $ParentNode;
}
$rowset = $db->getAll($sql);
if ( !$db->isError($rowset) )
{
return $rowset;
}
else
{
return false;
}
}
// 获得子节点
// 如果$all不为空则以数组格式返回所有子节点，否则仅返回下一层节点
function SelectChild($Node, $all = '')
{
global $db;
$this->_parseNode($Node);
$sql = "select * from ". $this->Table ." where ". $this->Column ." > ". $Node ." and ". $this->Column ." < ". $this->getNextNode($Node);
$res = $db->query($sql);
if ( !$db->isError($res) )
{
if ( $all )
{
while ( $row = $res->fetchRow() )
{
$rowset[] = $row;
}
}
else
{
$Child = $this->getChild($Node);
while ( $row = $res->fetchRow() )
{
if ( in_array($row[$this->Column], $Child) )
{
$rowset[] = $row;
}
}
}
return $rowset;
}
else
{
return false;
}
}
}
?>
[/code:1:0011f57be3]
夜猫子 回复于：2003-11-27 11:11:21 测试数据库：
INSERT INTO bintree (binMark,decMark) VALUES ('01000000000000000000000000000000',1073741824);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000000000000000000000',1092616192);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101000000000000000',1092780032);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001110000000000',1092787200);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001110000001000',1092787208);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101100000000000000',1092796416);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000110000000000000000',1092812800);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000110100000000000000',1092829184);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000111000000000000000',1092845568);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000111100000000000000',1092861952);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001110010000000',1092787328);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001110100000000',1092787456);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001110110000000',1092787584);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001111000000000',1092787712);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001111010000000',1092787840);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001111100000000',1092787968);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001111110000000',1092788096);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001110000001001',1092787209);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001110000001010',1092787210);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001110000001011',1092787211);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001110000001100',1092787212);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001110000001101',1092787213);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001110000001110',1092787214);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001110000001111',1092787215);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101001110000010000',1092787216);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101000000010000000',1092780160);
INSERT INTO bintree (binMark,decMark) VALUES ('01000001001000101011111110000000',1092796288);
longnetpro 回复于：2003-11-27 18:59:18 好！但是如果层数很多那怎么办呢？或是某层超过最大值？
夜猫子 回复于：2003-11-27 19:01:36 这种算法就是建立在事先规划好树的容量的基础上，层数和每层的数量事先都要有数，所以不适合那种无限分层的树
这种树结构比较死一点，我另外想了一个灵活些的树结构，打算先在我的项目里用用，如果好的话，再推荐给大家
longnetpro 回复于：2003-11-27 21:13:38 能不能透露个大概的思路？一两句就行？我也觉得用路径方式虽然灵活，但某些方面也不太方便，而且开销也大。用整数好，但是容量有限，这个矛盾怎么解决？如果只是二者其一，还好办一点，主要是要同时兼顾查询和排序。不过有一点可以肯定，在数据库里用递归查询绝对是下下之策。
夜猫子 回复于：2003-11-27 21:45:56 其实也不是什么很新鲜的主意，就是普通的树加一个辅助字段而已，是在这个问题的讨论中吸收了别人的意见的结果。
node_id parent code
1 0 01
2 1 0102
3 2 010203
我分析了一下，如果层非常多的话，位编码的方式就不可行了，因为位是不定长的，只有普通的那种树结构能够轻松满足。但是普通的那种树最大的毛病就是基于递归的遍历，所以想到加一个辅助字段来解决这个递归的毛病。
code字段其实就是路径信息，但是采用36进制，以2位为一层的话，每层可以容纳(36^2)-1也就是1295个节点，假设code字段用varchar(255)的话，可以容纳127层36^(254)-1个节点，容量非常大了，当然很少会用到这么大的树，如果真要处理这么大的树，肯定需要更好的方法。
采用36进制以后，占用的存储空间相对小，编码比较短，在采用like查询子节点的时候效率会比用低进制编码存储的路径效率要高，而且我敢肯定，效率肯定是比递归高的。并且不是每次对树的查询都需要对这个字段查询，比如只是想查上一级节点，同一层节点，下一层节点就可以直接的利用原来的方法。
这种方式适用于不能确定长度的树，我觉得一般的情况来说，我不会碰到特别大的树，一般不会超过4到5层。根据不同的情况，这两种树结合着用就差不多了。
具体怎么样，我也不好说，所以打算先写出来自己用用才真正清楚效果，既然老兄你问到了，我就说说，请指正。
longnetpro 回复于：2003-11-27 22:16:38 太好了！基本和我原来的思路相同，不过我原来是没有这个Parent字段的，现在看来这个字段还是有必要的，可以提高查询效率，因为大多数情况下只会搜索树的一个分支，先限制一下比较好，而且Parent是整型的，索引中的B树查起来也快，然后再用CODE排序——不过好象又有点问题，Parent只可能是一个子节点的父节点ID，而如果该子节点还有子节点的话，那个孙子节点的Parent就是子节点ID，这样查询的时候会不会漏掉子节点以下（孙子节点那一层及以下层）的分支呢？不知道这段话夜猫看不看得明白？如果漏了的话，那这个Parent字段好象就没有意义了。
还有，我觉得36进制编码太少，我原来试过用96进制，几乎ASCII码中非敏感字符全用都用到了。因为CODE字段主要是在排序中才用到，所以编码复杂一点没关系，一般一些别的信息多数是另有字段存贮的，如果是二合一的话，那就只好用你前面的位编码了，在综合上是一个平衡。
还有一点就是，如果定为相同长度的字符串表示一层的话会有浪费（假如用四个字符或更多），我会考虑用一个字符表示长度，后面的表示ID，类似于PASCAL中string类型的存贮模式。
不过我原来都只实现过相同长度的字符串表示一层，而且用的是十进制，所以后来才想改进。
不知道有什么意见或建议？
如果愿意的话，请加本人MSN：[email protected]，可以继续讨论，谢谢。
夜猫子 回复于：2003-11-27 22:45:41 你的意见我想想，另外我有两点要说：
采用36进制是因为我用base_convert来换算进制，最高支持到36位，再高就不晓得怎么处理了，呵呵，longnetpro教我。
另外我发觉刚才在每层节点的容量上的记算是错误的，因为node_id是在数据库里用了auto_increment来实现的，因此，node_id是不可重复的，所以，编码里肯定不会出现0101或者0a0a这样的编码，这样实际上大大的降低了每层的容量，而且树越大，这个影响越明显，所以不能处理太大的树，不同的编码长度对应的上限之间的关系我还没有计算出来，估计应该是在可接受范围内的，太大的树现在不在考虑范围。
夜猫子 回复于：2003-11-27 22:50:00 呵呵，刚发完上一个帖子就想清楚上限了。
编码的进制是m
每层编码的长度是n
那么整个树的总节点容量上限是(m^n)-1，树的层数理论上限也是(m^n)-1，所以如果要采用这种方法的话，事先也要先计划好容量的。
mikespook 回复于：2003-11-27 23:14:59 恩~~~看看~~~
能不能改成16进制编码，这样编码比较短~~~
夜猫子 回复于：2003-11-27 23:21:21 之所以有容量的限制，主要是方便解析编码，所以每层的编码长度必须定长，如果在编码路径里用特殊字符来分隔的话，每层编码的长度就不必有硬性的限制，上限也就大大增加了，理论上上限就受到code字段的存储空间限制，实际上用于很大的树的处理绝不可取，不过对于小的树，效果不错。
其实在以前的讨论中，已经有人提出这种说法，只是当时没有向这个方向上去考虑，现在看了，那位朋友说得很有道理。
有兴趣可以看看：
http://be10.ods.org/avenger/bbs/index.php?act=ST&f=2&t=3073&s=
mikespook 回复于：2003-11-27 23:56:39 如果使用哈夫曼编码，不就可以不使用定长编码了么？
longnetpro 回复于：2003-11-28 08:50:55 [quote:9bdd2d3cb5="夜猫子"]之所以有容量的限制，主要是方便解析编码，所以每层的编码长度必须定长，如果在编码路径里用特殊字符来分隔的话，每层编码的长度就不必有硬性的限制，上限也就大大增加了，理论上上限就受到code字段的存储空间限制，..........
http://be10.ods.org/avenger/bbs/index.php?act=ST&f=2&t=3073&s=
[/quote:9bdd2d3cb5]
看了这篇文章，我发现那位static的想法根本不和我的想法同路。他所提出那一系列的问题以及回答，基本上是基于select *** from table where id IN()这一SQL的，因此无法精确高效地查询遍历子树，因为他的目的主要在于从下往上的查找，不在于从上往下的查找，而遍历却恰恰是从上往下的。他其实自己被蒙住了眼睛，看不清楚。他的方法仅只能适用于查找路径，却不能很好的排序——例如找到一到某一节点的所有的子树。他所说的btree不支持范围索引这句话本身就有问题。对整数来说，只要不必计算后再索引（我们的方法从来没有说在查询的时候先计算），btree都是可以索引的，因为btree理论最初就是针对整数进行索引，也是有范围的，懂btree查找原理的人自然明白是怎么回事，而且我们索引的也只有一个变量，根本不可能有btree不支持这种方式的索引这么一说。还有他的多个字段之说，就显得有点不太可取了，明显扩展和维护问题很大，因为改数据结构的影响比改字段值的影响要大得多。其实很简单的一点就是可能他根本还没有理解我们算法的意义和工作方式。我们的要求是得到某一节点详细完整的所有的子树，而他的算法只是得到某一节点的所有父节点，但却无任何顺序，实用价值明显较低，而且效率也不一定高得太多。因此他的方法是不足取的，我认为他的数据结构及数据库原理并非理解得十分透彻，而且有点陷入思维的牛角尖了。
我们还是继续讨论树遍历的问题吧。
这样假如该字段长度为240，每层长度为10，即最多可记录达到24层，而如果每层编码用90进制数，则总容量数（不是单层容量，因为ID多数为Auto的），理论上为90^10，即 34867844010000000000。也就是说，理论上，可以对有 34867844010000000000 条记录的表做最多24层的树型记录，好象从数目上应该是够了的，前提是所有ID号必须连续。当然，这个效率问题有待考证，不过一般来说，需要被查询的子树结构不应该太复杂（试想一般不可能要你在一个页面中显示从根开始下面所有的子节点的结构，而多数是本层的下一层的子节点）。再说了，如果因为此算法的原因将递归操作变成了简单排序，你还可以分页显示，取得一个效率和效果折中的结果。
不过，还是可以肯定，整数索引比字符串索引快，因此有了路径这一思想概念之后，想法改为两者结合可能会比较好，思路还在进一步酝酿之中，应该不会太难。要注意的是：做这个类的时候，最好别牵扯到数据库的操作，最好是纯算术运算及字符串操作，完了之后形成多个SQL的参数，然后再传给专有的数据库方面的操作类进行查询，以实现模块功能的最大化。
另：在 http://www.chinaunix.net/forum/27/20031122/207556.html 我所描述的方法已与夜猫子所说的方法类似了，不过还需要改进。
夜猫子 回复于：2003-11-28 09:15:19 你的意思，我大概明白了，抽时间写出来用用看
[quote:d748186cb4="longnetpro"]做这个类的时候，最好别牵扯到数据库的操作，最好是纯算术运算及字符串操作，完了之后形成多个SQL的参数，然后再传给专有的数据库方面的操作类进行查询，以实现模块功能的最大化[/quote:d748186cb4]
我的设计思想和你差不多，就是先写一个类，仅仅负责计算，然后再继承一个或者多个子类来负责和数据库打交道，处理各种情况，不过“完了之后形成多个SQL的参数，然后再传给专有的数据库方面的操作类进行查询”的方式的确要灵活得多
longnetpro 回复于：2003-11-28 10:02:17 现帖一个代码计算八十六进制数，编码从0x31到0x7E 共94个，除掉其中的SQL及PHP的敏感字符 " ' $ _ % [ ] 等 8 个字符，可用的共86个字符，即可实现八十六进制。
[code:1:5a5306eedb]
function getTreeBaseString($excluded = ''){
$bs = '';
for($i=0x21;$i<0x7F;$i++){
$c = chr($i);
$bs .= (strpos($excluded, $c) === false)? $c : '';
}
return $bs;
}
$bs = getTreeBaseString('"'$_%[]');
echo $bs."<br>n";
define(TREE_BASE_STRING, $bs);
define(TREE_BASE_LEN, strlen(TREE_BASE_STRING));
echo TREE_BASE_LEN."<br>n";
function dec2base($v_int){
if($v_int === 0) return substr(TREE_BASE_STRING, 0, 1);
$s = '';
do{
$r = $v_int % TREE_BASE_LEN;
$s = substr(TREE_BASE_STRING, $r, 1).$s;
$v_int = floor($v_int / TREE_BASE_LEN);
}while($v_int > 0);
return $s;
}
function base2dec($v_base){
$len = strlen($v_base);
$n = 0;
for($i = 0; $i < $len; $i ++){
$index = strpos(TREE_BASE_STRING, $v_base{$i});
if($index===false) return false;
$n = $n * TREE_BASE_LEN + $index;
}
return $n;
}
$i = 354389054;
$s = dec2base($i);
echo $s."<br>n";
echo base2dec($s)."<br>n";
echo $i;
[/code:1:5a5306eedb]
中间很多的 echo 的测试代码大家自行删除即可。
longnetpro 回复于：2003-11-28 10:31:37 以上两函数dec2base及base2dec不够精确，当数值过大时不准。现用bc函数解决精度问题。
[code:1:8db107959f]
function getTreeBaseString($excluded = ''){
$bs = '';
for($i=0x21;$i<0x7F;$i++){
$c = chr($i);
$bs .= (strpos($excluded, $c) === false)? $c : '';
}
return $bs;
}
$bs = getTreeBaseString('"'$_%[]');
echo $bs."<br>n";
define(TREE_BASE_STRING, $bs);
define(TREE_BASE_LEN, strlen(TREE_BASE_STRING));
echo TREE_BASE_LEN."<br>n";
function dec2base($v_int){
if($v_int === 0) return substr(TREE_BASE_STRING, 0, 1);
$s = '';
do{
$r = bcmod($v_int, TREE_BASE_LEN);
$s = substr(TREE_BASE_STRING, $r, 1).$s;
$v_int = bcdiv($v_int, TREE_BASE_LEN, 0);
}while($v_int > 0);
return $s;
}
function base2dec($v_base){
$len = strlen($v_base);
$n = 0;
for($i = 0; $i < $len; $i ++){
$index = strpos(TREE_BASE_STRING, $v_base{$i});
if($index===false) return false;
$n = bcadd(bcmul($n, TREE_BASE_LEN), $index);
}
return $n;
}
$i = '22130157888803070975';
$s = dec2base($i);
echo $s."<br>n";
$n = base2dec(str_repeat('~', 10));
echo $n."<br>n";
echo $i;
[/code:1:8db107959f]
但这时注意两函数参数要为字符串。
非常全面的一个php技术网站,php爱好者站 http://www.phpfans.net 有相当丰富的文章和源代码.
相关阅读 更多 +
