简单的树结构，可以插入，删除，检测某节点是否存在

tree.php

<?php

/**
* 简单的树结构，可以插入，删除，检测某节点是否存在
*/
class XcTree
{
    // tree structure
    // $tree = array(
    //     array(
    //         'id' => 'xx',
    //         'children' => $tree;
    //     ),
    //     ...
    // );
    private $tree = array();

    /**
     * 创建一个空树
     */
    public static function create()
    {
        return new self();
    }

    /**
     * 从指定数据创建树
     * 如果是序列化的，将自动反序列化
     */
    public static function from_data($data)
    {
        $t = new self();
        if (is_string($data)) {
            $data = unserialize($data);
        }
        assert(is_array($data));
        $t->tree = $data;
        return $t;
    }

    /**
     * 添加一个id的节点，在$parent_id下添加。
     * 支持添加树
     */
    public function add($id, $parent_id = null, $index = -1)
    {
        if ($parent_id) {
            self::_search_add($this->tree, $id, $parent_id, $index);
        } else {
            self::_add($this->tree, $id, $index);
        }
    }

    private static function _add(&$tree, $id, $index)
    {
        $node = array('id' => $id, 'children' => array());
        if ($index == -1) {
            $tree[] = $node;
        } else {
            array_splice($tree, $index, 0, array($node));
        }
    }
    private static function _search_add(&$tree, $id, $parent_id, $index)
    {
        if (empty($tree)) {
            return false;
        }
        foreach ($tree as $k => &$v) {
            if ($parent_id == $v['id']) {
                self::_add($v['children'], $id, $index);
                return true;
            }
            if (($v['children'])) {
                return self::_search_add($v['children'], $id, $parent_id, $index);
            }
        }
        return false;
    }

    /**
     * 删除指定id的node
     * @return bool 成功失败
     */
    public function delete($id)
    {
        return self::_delete($this->tree, $id);
    }
    private static function _delete(&$tree, $id)
    {
        if (empty($tree)) {
            return false;
        }
        reset($tree);
        while (list($k, $v) = each($tree)) {
            if ($id == $v['id']) {
                unset($tree[$k]);
                return true;
            }
            if (($v['children'])) {
                $rs = self::_delete($tree[$k]['children'], $id);
                if ($rs) {
                    return $rs;
                }
            }
        }
        return false;
    }

    public function move($id, $parent_id, $index)
    {
        $rs = $this->delete($id);
        if (!$rs) {
            return false;
        }
        $this->add($id, $parent_id, $index);
        return true;
    }

    /**
     * 查看指定的id是否存在
     * @return bool 成功失败
     */
    public function exists($id)
    {
        $this->_result = false;
        $this->walk(function ($_id, $children, &$result) use($id) {
            if ($id == $_id) {
                $result = true;
                return false;
            }
            return true;
        });
        return $this->_result;
    }

    /**
     * 遍历整棵树
     */
    public function walk($callback)
    {
        $this->_go = true;
        $this->_walk($this->tree, $callback, $this->_result);
        return $this->_result;
    }

    private function _walk(&$tree, $callback, &$reduce)
    {
        if (empty($tree)) {
            return array();
        }
        if (!$this->_go || !is_array($tree) || !is_numeric(key($tree))) {
            return $tree;
        }
        reset($tree);
        while (list($k, $v) = each($tree)) {
            $id = $v['id'];
            $children = isset($v['children']) ? $v['children'] : array();
            $this->_go = $callback($id, $children, $reduce);
            if ($this->_go) {
                if ($children) {
                    $children = $this->_walk($children, $callback, $reduce);
                }
            }
            $tree[$k] = compact('id', 'children');
            if (!$this->_go) {
                break;
            }
        }
        return $tree;
    }

    /**
     * 将树转化为数组，指定id时获取其子节点
     */
    public function to_array($id = null)
    {
        if ($id) {
            $this->_result = array();
            $this->walk(function ($_id, $children, &$result) use($id) {
                if ($id == $_id) {
                    $result = $children;
                    return false;
                }
                return true;
            });
            return $this->_result;
        } else {
            return $this->tree;
        }
    }
}

ini_set('display_errors', 1);
error_reporting(E_ALL);

$t = XcTree::create();

$t->add('n1');
$t->add('n2');

$t->add('n3', 'n1');
$t->add('n4', 'n1');
$t->add('n5', 'n1', 0);

$t->delete('n4');

echo "<pre>";
print_r($t->to_array('n1'));