PHP China | 中国开源之路 » PHP高级应用（应用讨论） » 树操作算法，非递归方法

sentrychen 发表于 2008-10-1 12:24

树操作算法，非递归方法

前些日子和一些朋友讨论关于无限分类的算法问题，其中提到了利用PHP数组进行操作的想法。其实无限分类算法就是树的算法。
利用数据库存储数据加递归搜索似乎是目前很流行的一种方法，但这种方法的效率低下，并增加了不少数据库的负担。
我这个算法采用文本方式存储数据，效率应该还可以。由于时间关系，算法是匆匆完成没有经过严格测试就放上来了，大家有兴趣的话就测试一下，找找其中的bug，或改善一下算法的性能。
提醒一点，如果你的PHP可利用的内存不到1G，请不要尝试去创建一个具有100万个节点的树。。。:lol:
树的操作算法是各种高级数据结构算法的基础，估计不少同学在大学的时候都学烂了，所以我就不必细讲了。现在要讨论的是如何在PHP这个编程环境里面如果实现该算法最大的性能。
好吧，我来抛砖引玉。
因时间关系没有写注释，看不懂的同学可以提问。
[php]
<?php
/**
* 树操作类
*
* 利用php数组对树进行构造，删除和遍历等操作，全部遍历采用非递归方法实现，并实现Iterator和Countable操作。
* 该算法可适用与无限分类等相关领域，对于同时操作百万级以上的数据可能需要512M以上的内存支持。
* 利用文本存储数据结构，如果需要数据库存储可继承本类并覆盖loadTree和saveTree方法。
*
* @copyrihgt [email=sentrychen@hotmail.com]sentrychen@hotmail.com[/email], 2008
* @author sentrychen [email=sentrychen@hotmail.com]sentrychen@hotmail.com[/email]>
* @version $Id: Tree.php, v 0.0.1 2008/10/01 11:51:25 uw Exp $
*/

class Itc_Tree implements Iterator,Countable
{
    const ID = 'i';
    const PID = 'p';
    const LEVEL ='l';
    const DATA = 'd';
    const CHILDREN = 'c';
    const DFS = 'DFS';
    const BFS = 'BFS';
    protected $_tree = array();
    protected $_filename = '';
    protected $_prefix = 'tree_';
    protected $_path = '';
    protected $_rootid = 0;
    protected $_lastid = 0;
    protected $_way = self::DFS;
    protected $_stack = array();
   
    public function __construct($name, $path = '')
    {
        $this->loadTree($name, $path);
    }
    public function loadTree ($name, $path = '')
    {
        if ($path != '') {
            if (is_dir($path)) {
                $this->_path = rtrim($path, '/\\') . DIRECTORY_SEPARATOR;
            } else {
                die('No such directory :' . $path);
            }
        }
        $name = md5($name);
        $this->_filename = $this->_path . $this->_prefix . $name ;
        if (is_file($this->_filename)) {
            $this->_tree = json_decode(file_get_contents($this->_filename),true);
            $this->_initTree();
            return true;
        }
        return false;
    }
    protected function _initTree ()
    {
        $ary = $this->listToTree($this->_tree);
        $this->_rootid = $ary['topid'];
        $this->_lastid = $ary['lastid'];
        $this->_tree[$this->_rootid][self::LEVEL] = 1;
        return $this;
    }
   
    public function listToTree(&$list){
        $return = array('topid'=>0,'lastid'=>0);
        foreach ($list as $id => &$node){
                if (isset($list[$node[self::PID]]))
                    $list[$node[self::PID]][self::CHILDREN][$id] = &$node;
                else
                    $return['topid'] = $id;
                if ($id > $return['lastid']) $return['lastid'] = $id;
            }
        return $return;
    }
   
    public function setTreeByList (array $list)
    {
        if (!$this->_checkList($list)){
            die('Incorrect data format');
        }
        $this->_tree = $list;
        $this->_initTree();
        return true;            
    }
   
    public function getTree($id = null)
    {
        if (null === $id) $id = $this->_rootid;
        if (isset($this->_tree[$id]))
            return $this->_tree[$id];
        else
            return null;

    }
   
    public function getParent($id){
        if (isset($this->_tree[$id]) && isset($this->_tree[$this->_tree[$id][self::PARENT]])){
            return $this->_tree[$this->_tree[$id][self::PARENT]];
        }
        return null;
    }
      
    public function getParentsId($start,$level = null)
    {   
        
        $parent = array();
        $id = $start;
        do{
            if (!isset($this->_tree[$id])) break;
            $pid = $this->_tree[$id][self::PID];
            if (null !== $level && !$level--) break;
            if (!isset($this->_tree[$pid])) break;
        }
        while(true);
        return $parent;
    }
   
    public function getChildren($id){
        if (isset($this->_tree[$id])){
            return $this->_tree[$id][self::CHILDREN];
        }
        return null;
    }
   
    public function getTreeAll()
    {
        return $this->_tree;
    }
   
    public function getTreeList()
    {
        if (isset($this->_tree)) {
            return $this->toList($this->_tree);
        }
        return null;
    }
   
    public function toList($tree){
        $ary = array();
        foreach ($tree as $id => $node){
            unset($node[self::CHILDREN]);
            $ary[$id] = $node;
        }
        return $ary;
    }
   
    public function getDepth(){
        $depth = 1;
        $id = $this->_rootid;
        $stack = array($id);
        $i = 0;
        if (!isset($this->_tree[$id][self::LEVEL]))
            $this->_tree[$id][self::LEVEL] = 1;
        do{
            $id = $stack[$i++];
           $pid = $this->_tree[$id][self::PID];
           if (isset($this->_tree[$id][self::CHILDREN])){
               $stack = array_merge($stack,array_keys($this->_tree[$id][self::CHILDREN]));   
           }
           if (isset($this->_tree[$id][self::LEVEL])){
                   $level = $this->_tree[$id][self::LEVEL];
           }
           else {
                   $level = $this->_tree[$pid][self::LEVEL] + 1;
                   $this->_tree[$id][self::LEVEL] = $level;
           }
           if ($depth < $level) $depth = $level;
        }while(isset($stack[$i]));
        return $depth;
    }
   
    public function getLastId(){
        return $this->_lastid;
    }
   
    public function getRootId(){
        return $this->_rootid;
    }
   
    public function getRoot(){
        return $this->_tree[$this->_rootid];
    }
            
    public function getData($id){
        if (isset($this->_tree[$id])){
            return $this->_tree[$id][self::DATA];
        }
        return null;
    }
   
    public function setData($id,$data){
        if (isset($this->_tree[$id])){
            $this->_tree[$id][self::DATA] = $data;
            return true;
        }
        return false;
    }
        
    public function addRoot($data = null)
    {
        $root = array(
            self::ID => $this->_rootid,
            self::PID => $this->_rootid - 1,
            self::LEVEL => 1,
            self::DATA => $data
        );  
        $this->_tree[$this->_rootid] = &$root;
        $this->_lastid = $this->_rootid;
        return $this->_rootid;
    }
      
    public function addLeaf($pid,$data = null)
    {
        if (!isset($this->_tree[$pid])){
            if (isset($this->_tree[$this->_rootid]))
                $pid = $this->_rootid;
            else {
                $this->_lastid = $this->addRoot($data);
                return $this->_lastid;
            }
        }
        $id = ++$this->_lastid;
        $level = isset($this->_tree[$pid][self::LEVEL])? $this->_tree[$pid][self::LEVEL] + 1 : null;
        $this->_tree[$id] = array(
            self::ID => $id,
            self::PID => $pid,
            self::LEVEL => $level,
            self::DATA => $data
        );
        $this->_tree[$pid][self::CHILDREN][$id] = &$this->_tree[$id];
        return $id;
    }
    public function insertChild($pid, $children)
    {
        if (!isset($this->_tree[$pid])){
            return false;
        }
        if ($children instanceof self){
            $children = $children->getTree();
        }
        
        if (is_array($children)){
             $children = $this->toList($children);
            $lastid = $this->_lastid + 1;
            $list = array();
            foreach ($children as $id => $node){
                $node[self::ID] +=$lastid;
                $node[self::PID] +=$lastid;
                $list[$id + $lastid] = $node;
            }
            $ary = $this->listToTree($list);
            $this->_lastid = $ary['lastid'];
            $list[$ary['topid']][self::PID] = $pid;
            $this->_tree += $list;
            $this->_tree[$pid][self::CHILDREN][$ary['topid']] = &$this->_tree[$ary['topid']];
            return $this->_lastid;
        }
        return $this->addLeaf($pid,$children);
    }
   
    public function deleteChild($id){
        if (!isset($this->_tree[$id])){
            return null;
        }
        $pid = $this->_tree[$id][self::PID];
        $delTree = array();
        if (isset($this->_tree[$pid])){
            unset($this->_tree[$pid][self::CHILDREN][$id]);
        }
        $stack = array($id);
        do{
            $id = array_pop($stack);
            if (isset($this->_tree[$id][self::CHILDREN]))
                $stack =array_merge($stack, array_keys($this->_tree[$id][self::CHILDREN]));
            $delTree[$id] = $this->_tree[$id];
            unset($this->_tree[$id]);
        }while(!empty($stack));
        return $delTree;
    }
   
    public function emptyTree(){
        $this->_tree = array();
        $this->_rootid = 0;
        $this->_lastid = 0;
        return true;
    }
   
    public function destroyTree(){
        $this->emptyTree();
        if (is_file($this->_filename))
            unlink($this->_filename);
        return true;            
    }
   
    protected function _checkList (array $list)
    {
        $isChecked = true;
        $topNum = 0;
        foreach ($list as $id => $node) {
            if (! isset($node[self::ID]) || ! isset($node[self::PID]) || $node[self::ID] != $id) {
                $isChecked = false;
                break;
            }else{
                if (!isset($list[$node[self::PID]])) $topNum++;
                if ($topNum > 1){
                    $isChecked = false;
                    break;
                }
            }
        }
        return $isChecked;
    }
   
    public function getLevel($id){
        if (isset($this->_tree[$id]) && isset($this->_tree[$id][self::LEVEL]) )
            return $this->_tree[$id][self::LEVEL];
        $level = 0;
        $id2 = $id;
        while(isset($this->_tree[$id2])){
            if (isset($this->_tree[$id2][self::LEVEL])){
                $level += $this->_tree[$id2][self::LEVEL];
                break;
            }
            $level++;
            $id2 = $this->_tree[$id2][self::PID];
        }
        if (isset($this->_tree[$id]))
            $this->_tree[$id][self::LEVEL] = $level;
        return $level;
    }
      
    public function DFS($callback = null,$id = null){
        if (null === $id) $id = $this->_rootid;
        if (!isset($this->_tree[$id])){
            return null;
        }
        if (null == $callback || !function_exists($callback)){
            return null;
        }
        $stack = array($id);
        $return = null;
        do{
           $id = array_shift($stack);
           $children = null;
           if (isset($this->_tree[$id][self::CHILDREN])){
               $children = array_keys($this->_tree[$id][self::CHILDREN]);
               $stack = array_merge($children,$stack);
           }
           $args = array(
                   self::ID => $id,
                self::PID => $this->_tree[$id][self::PID],
                self::DATA => &$this->_tree[$id][self::DATA],
                self::LEVEL => $this->getLevel($id),
                self::CHILDREN => $children
           );
           $back = call_user_func($callback,$args);
           if (isset($back)){
               if (is_string($back)) $return .= $back;
               else if (is_array($back)) $return[] = $back;
               else if (is_int($back)) $return += $back;
               else if (is_bool($back) && $back) $return = $this->_tree[$id];
           }
        }while(!empty($stack));
        return $return;
        
    }
   
    public function BFS($callback = null,$id = null){
        if (null === $id) $id = $this->_rootid;
        if (!isset($this->_tree[$id])){
            return array();
        }
        if (null == $callback || !function_exists($callback)){
            $callback = null;
        }
        $stack = array($id);
        $return = null;
        do{
            $id = array_shift($stack);
            $children = null;
            if (isset($this->_tree[$id][self::CHILDREN])){
                $children = array_keys($this->_tree[$id][self::CHILDREN]);
                $stack = array_merge($stack,$children);   
            }   
            $args = array(
                   self::ID => $id,
                self::PID => $this->_tree[$id][self::PID],
                self::DATA => &$this->_tree[$id][self::DATA],
                self::LEVEL => $this->getLevel($id),
                self::CHILDREN => $children
           );

            $return = call_user_func($callback,$args);
            if (isset($back)){
               if (is_string($back)) $return .= $back;
               else if (is_array($back)) $return[] = $back;
               else if (is_int($back)) $return += $back;
               else if (is_bool($back) && $back) $return = $this->_tree[$id];
           }

        }while(!empty($stack));
        return $return;
    }
   
    public function saveTree(){
        file_put_contents($this->_filename, json_encode($this->toList($this->_tree)));
        return true;
    }   
    public function setWay($way = self::DFS){
        if (in_array($way,array(self::DFS,self::BFS))){
            $this->_way = $way;
            $this->rewind();
        }
        return $this;
    }
   
    public function rewind()
    {
        if (isset($this->_tree[$this->_rootid]))
        {
            $this->_stack = array($this->_rootid);
        }
        else{
            $this->_stack = array();
            
        }
        return $this;
    }
   
    public function next()
    {
        $id = array_shift($this->_stack);
        if (isset($this->_tree[$id][self::CHILDREN])){
           $children = array_keys($this->_tree[$id][self::CHILDREN]);
           if ($this->_way == self::BFS)
               $this->_stack = array_merge($this->_stack,$children);
           else
               $this->_stack = array_merge($children,$this->_stack);
        }
    }
   
    public function count()
    {
        return count($this->_tree);
    }
   
    public function key()
    {
        return current($this->_stack);
    }
   
    public function current()
    {
        $id = current($this->_stack);
        if (isset($this->_tree[$id])){
            return $this->_tree[$id];
        }
        else
            return null;
    }
   
    public function valid()
    {
        return !empty($this->_stack);
    }
}



[/php]

[[i] 本帖最后由 sentrychen 于 2008-10-3 11:08 编辑 [/i]]

sentrychen 发表于 2008-10-1 14:43

功能测试
[php]
<?php
include '../lib/Itc/Tree.php';
$loop = 10;
$tree = new Itc_Tree('t10');
//获得最后一个ID
$id = $tree->getLastId();
$i=0;
//构造一棵10个结点的随机树
while($loop--){
        $pid = rand(0,$id);
        $id = $tree->addLeaf($pid,'data' . $i++);
}
//定义一个遍历访问函数
function visit($node){
        printf("%'-" . $node[Itc_Tree::LEVEL] . "s%s[%d]\n",'',$node[Itc_Tree::DATA],$node[Itc_Tree::ID]);
}
//打印树结构
//print_r($tree->getTreeList());

echo "<pre>";
//广度优先遍历树1
echo "广度优先1：\n";
$tree->BFS('visit');
//广度优先遍历树2
echo "广度优先2：\n";
$tree->setWay(Itc_Tree::BFS);
foreach($tree as $id => $node){
        echo $id,',';
}
echo "\n";
//深度优先遍历树1
echo "深度优先1：\n";
$tree->DFS('visit');
//深度优先遍历树
echo "深度优先2：\n";
$tree->setWay(Itc_Tree::DFS);
foreach($tree as $id => $node){
        echo $id,',';
}
echo "\n";
echo "树的深度：";
echo $tree->getDepth() ,"\n";
echo "树的结构：";
print_r($tree->getTree());
echo "</pre>";
//保存树
$tree->saveTree();

///－－－－－－－－输出结果-------------------------
广度优先1：
-data0[0]
--data1[1]
--data3[3]
--data4[4]
--data6[6]
---data2[2]
---data7[7]
---data5[5]
---data8[8]
----data9[9]
广度优先2：
0,1,3,4,6,2,7,5,8,9,
深度优先1：
-data0[0]
--data1[1]
---data2[2]
----data9[9]
---data7[7]
--data3[3]
---data5[5]
---data8[8]
--data4[4]
--data6[6]
深度优先2：
0,1,2,9,7,3,5,8,4,6,
树的深度：4
树的结构：Array
(
    [i] => 0
    [p] => -1
    [l] => 1
    [d] => data0
    [c] => Array
        (
            [1] => Array
                (
                    [i] => 1
                    [p] => 0
                    [l] => 2
                    [d] => data1
                    [c] => Array
                        (
                            [2] => Array
                                (
                                    [i] => 2
                                    [p] => 1
                                    [l] => 3
                                    [d] => data2
                                    [c] => Array
                                        (
                                            [9] => Array
                                                (
                                                    [i] => 9
                                                    [p] => 2
                                                    [l] => 4
                                                    [d] => data9
                                                )

                                        )

                                )

                            [7] => Array
                                (
                                    [i] => 7
                                    [p] => 1
                                    [l] => 3
                                    [d] => data7
                                )

                        )

                )

            [3] => Array
                (
                    [i] => 3
                    [p] => 0
                    [l] => 2
                    [d] => data3
                    [c] => Array
                        (
                            [5] => Array
                                (
                                    [i] => 5
                                    [p] => 3
                                    [l] => 3
                                    [d] => data5
                                )

                            [8] => Array
                                (
                                    [i] => 8
                                    [p] => 3
                                    [l] => 3
                                    [d] => data8
                                )

                        )

                )

            [4] => Array
                (
                    [i] => 4
                    [p] => 0
                    [l] => 2
                    [d] => data4
                )

            [6] => Array
                (
                    [i] => 6
                    [p] => 0
                    [l] => 2
                    [d] => data6
                )

        )

)
[/php]

sentrychen 发表于 2008-10-1 17:45

删除子数和插入子树操作。
[php]
//利用原来保存的数据进行操作
include '../lib/Itc/Tree.php';
$tree = new Itc_Tree('t10');
echo "<pre>";
//删除结点为2的子树，返回被删除的子树
$delTree = $tree->deleteChild(2);
//在结点3插入刚刚被删除的子树
$tree->insertChild(3,$delTree);
print_r($tree->getTree());
echo "</pre>";
//输出结果
Array
(
    [i] => 0
    [p] => -1
    [l] => 1
    [d] => data0
    [c] => Array
        (
            [1] => Array
                (
                    [i] => 1
                    [p] => 0
                    [l] => 2
                    [d] => data1
                    [c] => Array
                        (
                            [7] => Array
                                (
                                    [i] => 7
                                    [p] => 1
                                    [l] => 3
                                    [d] => data7
                                )

                        )

                )

            [3] => Array
                (
                    [i] => 3
                    [p] => 0
                    [l] => 2
                    [d] => data3
                    [c] => Array
                        (
                            [5] => Array
                                (
                                    [i] => 5
                                    [p] => 3
                                    [l] => 3
                                    [d] => data5
                                )

                            [8] => Array
                                (
                                    [i] => 8
                                    [p] => 3
                                    [l] => 3
                                    [d] => data8
                                )

                            [12] => Array
                                (
                                    [i] => 12
                                    [p] => 3
                                    [l] => 3
                                    [d] => data2
                                    [c] => Array
                                        (
[i]                                            [19] => Array
                                                (
                                                    [i] => 19
                                                    [p] => 12
                                                    [l] => 4
                                                    [d] => data9
                                                )

                                        )

                                )

                        )

                )

            [4] => Array
                (
                    [i] => 4
                    [p] => 0
                    [l] => 2
                    [d] => data4
                )

            [6] => Array
                (
                    [i] => 6
                    [p] => 0
                    [l] => 2
                    [d] => data6
                )

        )

)
[/php][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]

[[i] 本帖最后由 sentrychen 于 2008-10-1 17:47 编辑 [/i]]

sentrychen 发表于 2008-10-1 18:14

//性能测试，感觉还不是很满意。构造一棵10万个结点的树，然后遍历，保存
[php]
include '../lib/Itc/Tree.php';
$loop = 100000;
test('');
$tree = new Itc_Tree('t100000');
//获得最后一个ID
$id = $tree->getLastId();
$i=0;
//构造一棵10万个结点的随机树

while($loop--){
        $pid = rand(0,$id);
        $id = $tree->addLeaf($pid,'data' . $i++);
}
test('创建时间');

foreach($tree as $id => $node){
        $a = $node[Itc_Tree::PID];
}
test('遍历时间');
$tree->saveTree();
test('保存时间');
function test($tag){
                static $pTime = 0;
                static $pMemory = 0;
                $nowTime = microtime(TRUE);
                $nowMem = memory_get_usage();
                if ($pTime){
                        echo $tag , " | "  , number_format(($nowTime - $pTime),6)
                                ,"  秒|  " , number_format($nowMem - $pMemory) , "字节<br>\n";
                }
                $pTime = $nowTime;
                $pMemory = $nowMem;
}
//输出结果

创建时间 | 1.320593 秒| 60,750,304字节
遍历时间 | 2.449615 秒| 24,736字节
保存时间 | 0.704968 秒| 39,240字节
[/php]

sentrychen 发表于 2008-10-3 10:25

呵呵，没人感兴趣，也许是太基础了或者我写得太烂

把牛人问倒 发表于 2008-10-3 10:28

LZ高手  能打包成附件下载吗

naodai 发表于 2008-10-5 00:52

先站位,慢慢研究!!

lxylxy888666 发表于 2008-10-5 01:26

值得好好看看，
但实际运用，
犹豫了，
怕怕tukiz13

sentrychen 发表于 2008-10-5 08:45

[quote]原帖由 [i]lxylxy888666[/i] 于 2008-10-5 01:26 发表 [url=http://bbs.phpchina.com/redirect.php?goto=findpost&pid=629756&ptid=81976][img]http://bbs.phpchina.com/images/common/back.gif[/img][/url]
值得好好看看，
但实际运用，
犹豫了，
怕怕tukiz13 [/quote]
呵呵，怕啥呢?

lxylxy888666 发表于 2008-10-5 10:07

不知道你花了多少时间，，，
如果用数据库，我只要一两个小时，
而这样写。我一两天就写不出来。。
tukiz14

sentrychen 发表于 2008-10-5 10:20

[quote]原帖由 [i]lxylxy888666[/i] 于 2008-10-5 10:07 发表 [url=http://bbs.phpchina.com/redirect.php?goto=findpost&pid=629851&ptid=81976][img]http://bbs.phpchina.com/images/common/back.gif[/img][/url]
不知道你花了多少时间，，，
如果用数据库，我只要一两个小时，
而这样写。我一两天就写不出来。。
tukiz14 [/quote]
花了一个上午的时间写，再花一个下午的时间调试。

lxylxy888666 发表于 2008-10-5 10:40

我的哥啊，强啊

七月十五 发表于 2008-10-5 15:28

算法精妙，可以应用在很多实际场合，受益良多。
非常感谢楼主分享。
建议加精，以资鼓励。

shanji 发表于 2008-10-5 15:38

五五说好，就是好！

sentrychen 发表于 2008-10-5 17:51

[quote]原帖由 [i]七月十五[/i] 于 2008-10-5 15:28 发表 [url=http://bbs.phpchina.com/redirect.php?goto=findpost&pid=630105&ptid=81976][img]http://bbs.phpchina.com/images/common/back.gif[/img][/url]
算法精妙，可以应用在很多实际场合，受益良多。
非常感谢楼主分享。
建议加精，以资鼓励。 [/quote]
呵呵，谢谢加精，这个算法我也没有在实际场合应用过，可能还有很多地方会有bug。
有空我再写一个二叉树的算法，二叉树有4种遍历方式，估计也有很多地方需要用到的。

lsnow 发表于 2008-10-6 15:16

这么长，哪看得懂啊。

把你的思路写出来就可以了。

ajaxer 发表于 2008-10-6 16:09

学习,mark

liyong98847 发表于 2008-10-15 12:15

我狂顶！！！！！
tukiz19

ws00377531 发表于 2008-10-22 09:19

老话题 到底是把逻辑操作交给数据库 还是交给自己的代码！

pylong 发表于 2008-10-22 10:02

回复 19# ws00377531 的帖子

具体问题具体分析
如果是数据库负荷大的系统，尽量减轻数据库负担，减少数据库中的运算

查看完整版本: 树操作算法，非递归方法