归约树

 

目的：归约操作

规则：将要操作的内容分为多级，上级节点可覆盖下级节点，因此仅保留上级节点，所有子节点都被剔除

输入：根/父节点   要加入的节点

输出：归约-缩减后的树/子树

如：

$tree = array();

 

输入
$node1 = array(0=>"10");
$node2 = array(0=>"20");
$node3 = array(0=>"40");
$node11 = array(0=>"10",1=>"13");
$node12 = array(0=>"10",1=>"32");
$node21 = array(0=>"20",1=>"132");
$node311 = array(0=>"40",1=>"13",2=>"47");
$node112 = array(0=>"10",1=>"13",2=>"67");

 

add($tree,$node112);         

 

生成树

{"10":{"value":"10","Lv":0,"tag":0,"13":{"value":"13","Lv":1,"tag":0,"67":{"value":"67","Lv":2,"tag":1}}}}

 
add($tree,$node11);     

剔除子节点  2=>"67"

生成树

{"10":{"value":"10","Lv":0,"tag":0,"13":{"value":"13","Lv":1,"tag":1}}}

add($tree,$node12);
add($tree,$node3);
add($tree,$node311);
add($tree,$node12);
add($tree,$node21);
add($tree,$node1);
add($tree,$node2);

最后生成树为

{"10":{"value":"10","Lv":0,"tag":1},"40":{"value":"40","Lv":0,"tag":1},"20":{"value":"20","Lv":0,"tag":1}}

 

/**
 * 递归--缩减树
 * @param unknown_type $root
 * @param unknown_type $new
 */
function add(&$root,&$new) {
    if( !isset($new) ) return;
    $baseArr = array("value"=>"value","Lv"=>"Lv","tag"=>"tag");

    foreach( $new as $key=>$value) {//key:0~N-1 级别:key+1
        if( !isset($value) ) break;//该级别及以下为空
        
        $Lv = $key + 1;
        if( isset($root[$value]) ) {//原已有相同节点
            if( $root[$value]['tag'] == 1 ) {//是叶子节点
                break;
            } else {//不是叶子,进入下一级处理
                if(1 == count($new)){
                    $toDumpArr = array_diff_key($root[$value],$baseArr);    
                 foreach($toDumpArr as $dKey => $dValue) {
                     unset($root[$value][$dKey]);
                 }    
                 unset($new[$key]);
                 $root[$value]['tag'] = 1;
                 break;
                }
                
                unset($new[$key]);
                add($root[$value],$new);
            }
        } else {//原未有相同节点，加入
            $root[$value]['value'] = $value;
            $root[$value]['Lv'] = $key;
            if(1 == count($new)) {//是叶子节点
                $root[$value]['tag'] = 1;
                unset($new[$key]);                
             break;
            } else {//不是叶子,进入下一级处理
             $root[$value]['tag'] = 0;
             unset($new[$key]);
                add($root[$value],$new);
            }
        }
    }
}