<?php
/* 
用php寫(xiě)的無(wú)序樹(shù)
 */
 class unorderedTree{
 // 節(jié)點(diǎn)id計(jì)數(shù)器
 protected $nodeId=0;
 // 樹(shù)的深度
 protected $depth=0;
 // 樹(shù)的節(jié)點(diǎn)數(shù),
 protected $nodesCount=0;
 // 樹(shù)的度 @todo: 使其發(fā)揮作用
 public $degree=" to be implent";
 // 根節(jié)點(diǎn)id
 // 由于樹(shù)有多種從根節(jié)點(diǎn)開(kāi)始操作，不想每次遍歷樹(shù)到頂找root，用一個(gè)變量始終指向根節(jié)點(diǎn)
 protected $rootid=null;
 // 子節(jié)點(diǎn)集合, k-v 為 nodeid=>(stdclass)node
 // 一些樹(shù)的實(shí)現(xiàn)常常是采用節(jié)點(diǎn)和樹(shù)同一class，這里節(jié)點(diǎn)是使用 stdclass{ data, parent, id , childrenIds} ，因我認(rèn)為節(jié)點(diǎn)和樹(shù)應(yīng)為兩種對(duì)象，且stdclass要輕于樹(shù)的class
 // 節(jié)點(diǎn)格式說(shuō)明: $this->nodes[nodeId] = new stdclass{ id ,parentId, childrenIds, data }
 // id: 節(jié)點(diǎn)id
 // parentId: 節(jié)點(diǎn)父節(jié)點(diǎn)id
 // childrenIds: 子節(jié)點(diǎn)的id 不想每次遍歷樹(shù)確定層次關(guān)系 
 // 注意: 節(jié)點(diǎn)中, #只保存其自身數(shù)據(jù)和其子節(jié)點(diǎn)id的集合#, 子節(jié)點(diǎn)的數(shù)據(jù)通過(guò)從樹(shù) $tree->nodes[ $node->childrenIds[a_child_id] ] 訪(fǎng)問(wèn)
 // data: 節(jié)點(diǎn)中包含的數(shù)據(jù)，如節(jié)點(diǎn)名稱(chēng)等屬性數(shù)據(jù)
 protected $nodes=array();
 // 用戶(hù)自定義訪(fǎng)問(wèn)節(jié)點(diǎn)
 protected $userVisitFunction=null;
 /* 分組: 類(lèi)的基本函數(shù) */
 // @todo: 構(gòu)造樹(shù)
 public function __construct(){
 }
 // @todo: 銷(xiāo)毀樹(shù) 
 public function __destruct(){
  unset($this->nodes) ;
 }
  //------------ 獲取數(shù)據(jù)類(lèi)函數(shù)---------------
  // 獲取樹(shù)的深度,
  public function getTreeDepth(){
  return $this->depth;
  }
  // 獲取樹(shù)的節(jié)點(diǎn)數(shù)目 
  public function getCount(){
  return $this->NodesCount;
  }
  // 獲取樹(shù)的度 
  public function getDegree(){
  // @todo: 獲取樹(shù)的度（因?yàn)閷?duì)度暫時(shí)沒(méi)什么需要就不實(shí)現(xiàn)了 )
  return $this->degree;
  }
  //獲取指定節(jié)點(diǎn)
  public function getNode($nodeId){
  if(isset($this->Nodes[$nodeId])){
   return $this->Nodes[$nodeId];
  }
  else{
   return false;
  }
  }
  // 獲取最新id
  public function getId(){
  return $this->nodeId;
  }
  //獲取指定節(jié)點(diǎn)高度
  public function getNodeHeight($nodeId){
  if( array_key_exists($nodeId, $this->nodes) ){
   // 此節(jié)點(diǎn)已在樹(shù)里，高度至少為1，每找到一個(gè)父節(jié)點(diǎn)+1
   $height=1;
   // 記錄此樹(shù)中已經(jīng)訪(fǎng)問(wèn)過(guò)的節(jié)點(diǎn), 用于防止節(jié)點(diǎn)構(gòu)造時(shí)互相parent導(dǎo)致此函數(shù)死循環(huán)且及時(shí)結(jié)束查找
   $visitedNodesIds=array();
   // 記錄當(dāng)前操作節(jié)點(diǎn)的id
   $cid=$nodeId;
   // 當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)必須存在于此樹(shù)中
   // 不用遞歸
   while( isset($cid) ) {
    if( !in_array($cid,$visitedNodesIds ) ){
     if( $this->rootid===$cid){ //到頂,返回 
      return $height;
     }
     $visitedNodesIds[]=$cid;
     $cid= $this->nodes[ $cid ]->parentId;
     $height++; 
    }
    else{
     return false;
    }
   }
   return false;
  }
  else{
   return false;
  }
  }
  //獲取根節(jié)點(diǎn)
  public function getRoot(){
  return (!is_null($this->rootid) ) && $this->nodes[$this->rootid];
  }
  //獲取指定節(jié)點(diǎn)和其所有子節(jié)點(diǎn)構(gòu)成的數(shù)組 
  //這是用于獲取子樹(shù)的一個(gè)關(guān)鍵基礎(chǔ)操作
  public function getSubNodes($nodeId){
  if(isset($this->nodes[$nodeId])){
   $result=array();
   $toVisitNodeIds=array();
   $toVisitedNodeIds[]=$nodeId; 
   $result[]=$this->nodes[$nodeId]->id;
   array_shift($toVisitedNodeIds); 
   $toVisitedNodeIds=array_merge( $toVisitedNodeIds, $this->nodes[$nodeId]->childrenIds);
   while(!empty($toVisitedNodeIds)){
    $toVisitNodeId=array_shift($toVisitedNodeIds);
    $result[]=$this->nodes[$toVisitNodeId]->id;
    $toVisitedNodeIds=array_merge( $toVisitedNodeIds, $this->nodes[$toVisitNodeId]->childrenIds);
   }
   return $result ;
  }
  else{
   return false;
  }
  } 
  //@todo: 獲取由指定節(jié)點(diǎn)和其所有子節(jié)點(diǎn)構(gòu)建的子樹(shù)
  public function getSubTree($nodeid){
  }
  //---------------- 數(shù)據(jù)更新 -----------------
  public function setId($nodeId){
   $this->nodeId=$nodeId;
   return $this;
  }
  // 創(chuàng)建不重復(fù)的(樹(shù)中未被使用的) 新id
  public function seekId(){
  $this->nodeId++;
  return $this->nodeId;
  }
 public function setVisitFunction($userFunction){
  $this->userVisitFunction=$userFunction;
  }
  //插入子節(jié)點(diǎn)，默認(rèn)為插在根節(jié)點(diǎn)下
  public function insertNode($parent_id=null , $data=null){
  //注意node不是class tree
  $node = new stdclass; 
  $node->data = $data;
  //樹(shù)的節(jié)點(diǎn)數(shù)增加
  $this->nodeCount++;
  // 分配節(jié)點(diǎn)id
  $this->seekId();
  $node->id =$this->getId();
  //插入根節(jié)點(diǎn)
  if( (is_null($parent_id)) && is_null($this->rootid)){
   $node->parentId = null;
   $node->childrenIds = array();
   $this->depth=1; 
   $this->rootid=$node->id;
   $this->nodes [$node->id]=$node;
   return $this;
  } 
  elseif( isset($this->nodes[$parent_id]) || is_null($parent_id) ){
  // 插在此樹(shù)已有節(jié)點(diǎn)下
   if(is_null($parent_id)){
    $parent_id=$this->rootid;
   }
   $node->parentId = $parent_id;
   $node->childrenIds = array();
   //更新樹(shù)的最大深度
   $depth=$this->getNodeHeight($parent_id);
   $this->depth=max($depth+1, $this->depth);
   $this->nodes[$parent_id]->childrenIds []= $node->id;
   $this->nodes [$node->id]=$node;
   return $this;
  }
  else{
   return $this; 
  }
  } 
  //insert node 的別名
  public function append($parent_id=null , $data=null){
  return $this->insertNode($parent_id,$data);
  }
  // --------------- 數(shù)據(jù)訪(fǎng)問(wèn) -----
  //廣度優(yōu)先遍歷節(jié)點(diǎn)的別名, 全名太長(zhǎng)了
  public function b($nodeId=null){
  return $this->breadthTraversal($nodeId);
  }
  // 廣度優(yōu)先遍歷節(jié)點(diǎn)
  public function breadthTraversal($nodeId=null){
  if(is_null($this->rootid)){
   die("此樹(shù)為空樹(shù)，不可訪(fǎng)問(wèn)");
  }
  else{
   //全部遍歷
   if(is_null($nodeId) || ( $this->rootid===$nodeId) ){
    $nodeId=$this->rootid;
   }
   $toVisitNodeIds=array();
   $toVisitedNodeIds[]=$nodeId; 
   $this->visit( $this->nodes[$nodeId]);
   array_shift($toVisitedNodeIds); 
   $toVisitedNodeIds=array_merge( $toVisitedNodeIds, $this->nodes[$nodeId]->childrenIds);
   while(!empty($toVisitedNodeIds)){
    $toVisitNodeId=array_shift($toVisitedNodeIds);
    $this->visit( $this->nodes[$toVisitNodeId]);
    $toVisitedNodeIds=array_merge( $toVisitedNodeIds, $this->nodes[$toVisitNodeId]->childrenIds);
   }
  }
  return $this;
  }
  //深度優(yōu)先的別名
  public function d($nodeId=null){
  return $this->depthTraversall($nodeId);
  }
  // 深度優(yōu)先遍歷
  // 和廣度優(yōu)先的不同實(shí)現(xiàn)只在于array_merge的順序不同而已 ( php array 忒好用啊忒好用 )
  public function depthTraversall($nodeId=null){
  if(is_null($this->rootid)){
   die("此樹(shù)為空樹(shù)，不可訪(fǎng)問(wèn)");
  }
  else{
   //全部遍歷
   if(is_null($nodeId)){
    $nodeId=$this->rootid;
   }
   $toVisitNodeIds=array();
   $toVisitedNodeIds[]=$nodeId; 
   $this->visit( $this->nodes[$nodeId]);
   array_shift($toVisitedNodeIds); 
   $toVisitedNodeIds=array_merge( $this->nodes[$nodeId]->childrenIds, $toVisitedNodeIds );
   while(!empty($toVisitedNodeIds)){
    $toVisitNodeId=array_shift($toVisitedNodeIds);
    $this->visit( $this->nodes[$toVisitNodeId]);
    $toVisitedNodeIds=array_merge( $this->nodes[$toVisitNodeId]->childrenIds, $toVisitedNodeIds );
   }
  }
  return $this;
  }
  //訪(fǎng)問(wèn)單個(gè)節(jié)點(diǎn)
  public function visit($node){
  if(is_null($this->userVisitFunction )){
   return $node->id;
  }
  else{
   return call_user_func($this->userVisitFunction,$node,$this);
  }
  }
 }
?>