Ousland
侠客
侠客
  • UID67
  • 粉丝10
  • 关注0
  • 发帖数38
  • 社区居民
  • 阅读:2370
  • 回复:1

第六周作业 2014-8-23 崔景宇

楼主#
更多 发布于:2014-08-23 00:18
二叉树
编辑节点的自平衡还在看资料.
<?php
 
# 为了更好的理解,我将节点存在文件里.
# 文件存储节点;
class node
{
    private $dir = './cache';
     
    public function __construct($dir = '')
    {
        $dir       = $dir ?: $this->dir;
        $this->dir = $dir;
        if (!is_dir($dir)) {
            mkdir($dir);
        }
         
    }
     
    # 存;
    public function _set($name, $value)
    {
        $data     = serialize($value);
        $filename = $this->dir . '/' . $name;
        file_put_contents($filename, $data);
    }
     
    # 取;
    public function _get($name = '')
    {
        $filename = $this->dir . '/' . $name;
        if (!file_exists($filename) || !is_file($filename)) {
            return null;
        }
        $value = file_get_contents($filename);
        return unserialize($value);
    }
     
    # 删;
    public function _unset($name)
    {
        $filename = $this->dir . '/' . $name;
        @unlink($filename);
    }
     
    public function __destruct()
    {
        @rmdir($this->dir);
    }
     
}
 
 
/**
 * 简单的二叉树 CURD操作;
 * Author@Cui;
 */
class Xtree
{
     
    private $node;
     
    private $root;
     
    private $size;
     
    public function __construct()
    {
        $this->node = new node();
    }
     
    # 增加节点;
    public function addNode($val)
    {
         
        $path = uniqid(rand(1, 99)) . rand(1, 9999999);
         
        if (!$this->root) {
            $this->root    = 'root.' . $path;
            $data          = array();
            $data['val']   = $val;
            $data['left']  = '';
            $data['right'] = '';
            $data['layer'] = '1';
            $data['path']  = $this->root;
            $this->node->_set($this->root, $data);
            return true;
        }
         
        return $this->each($val, function($node, $parent, $forwad, $layer) use ($val, $path)
        {
            if ($node['val'] != $val) {
                $data          = array();
                $data['val']   = $val;
                $data['path']  = $path;
                $data['layer'] = $layer;
                $data['left']  = '';
                $data['right'] = '';
                 
                $parent[$forwad] = $path;
                 
                $this->size++;
                $this->node->_set($parent['path'], $parent);
                $this->node->_set($path, $data);
                return true;
            }
            return false;
        });
         
    }
     
    #修改节点 如何自平衡,还在看资料;
    public function editNode($val, $toVal)
    {
        $this->each($val, function($node) use ($val, $toVal)
        {
             
        });
    }
     
    #删除节点;
    public function delNode($val)
    {
         
        return $this->each($val, function($node, $parent, $forwad) use ($val)
        {
            if ($val == $node['val']) {
                 
                if ($forwad == 'root') {
                    $paths = $this->order();
                    foreach ($paths as $value) {
                        $this->node->_unset($value['path']);
                    }
                    $this->root = null;
                    $this->size = 0;
                    return true;
                }
                 
                $left  = $node['left'];
                $right = $node['right'];
                 
                if (!$left && !$right) {
                    $parent[$forwad] = '';
                    $this->node->_set($parent['path'], $parent);
                    $this->node->_unset($node['path']);
                    return true;
                }
                 
                if (($left && !$right) || (!$left && $right)) {
                    $parent[$forwad] = $node[$forwad];
                    $this->node->_set($parent['path'], $parent);
                    $this->node->_unset($node['path']);
                    return true;
                }
                 
                #中序排序,找到相邻的比他大的那个交换左右节点????
                $paths = $this->order($node['path']);
                 
                while ($path = array_shift($paths)) {
                    if ($path['val'] == $val) {
                        break;
                    }
                }
                 
                $curr            = $path;
                $next            = array_shift($paths);
                $next[$forwad]   = $curr[$forwad];
                $parent[$forwad] = $next['path'];
                $this->node->_set($parent['path'], $parent);
                $this->node->_set($next['path'], $next);
                $this->node->_unset($curr['path']);
                return true;
            }
             
            return false;
             
        });
         
    }
     
    # 根据值遍历;
    public function each($val, $callBack)
    {
         
        $node   = $this->node->_get($this->root);
        $layer  = 1;
        $forwad = 'root';
        $parent = $node;
        while ($node) {
             
            $parent = $node['val'] != $val ? $node : $parent;
            $layer++;
             
            if ($node['val'] > $val) {
                $forwad = 'left';
                $node   = $this->node->_get($node['left']);
                continue;
            }
             
            if ($node['val'] < $val) {
                $forwad = 'right';
                $node   = $this->node->_get($node['right']);
                continue;
            }
             
            break;
             
        }
         
        return $callBack($node, $parent, $forwad, $layer);
         
    }
     
    #中序遍历;
    public function order($node = '')
    {
         
        $root = $node ?: $this->root;
        $tree = $this->node->_get($root);
         
        $left  = array();
        $right = array();
         
        $leftTree = $this->node->_get($tree['left']);
        $righTree = $this->node->_get($tree['right']);
         
        if ($leftTree) {
            $left = $this->order($tree['left']);
             
        }
         
        if ($righTree) {
            $right = $this->order($tree['right']);
             
        }
         
        $root = array(
            'V' . $tree['val'] => $tree
        );
         
        return array_merge($left, $root, $right);
         
    }
     
}
 
$Xtree = new Xtree();
$Xtree->addNode(10);
$Xtree->addNode(11);
$Xtree->addNode(12);
$Xtree->addNode(9);
$Xtree->addNode(9.5);
$Xtree->addNode(9.8);
$Xtree->addNode(8);
$Xtree->addNode(7);
$Xtree->addNode(6);
 
$Xtree->delNode(9);
$Xtree->delNode(11);
 
print_r($Xtree->order());
 
 
?>
[Ousland于2014-08-23 09:15编辑了帖子]
喜欢0
BlackTree
管理员
管理员
  • UID1
  • 粉丝116
  • 关注6
  • 发帖数715
  • 社区居民
  • 最爱沙发
  • 喜欢达人
  • 原创写手
沙发#
发布于:2014-08-27 16:31
景宇 数据结构这个作业完成的不错!

返回顶部