位编码算法的类（分类算法）

<?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;
}
}
}
?>;