PHP 비순차 트리 구현 기술

이 글은 주로 PHP unordered tree의 구현 기술을 소개합니다. 관심 있는 친구들이 참고하면 좋겠습니다.

이 기사의 예는 PHP 비순차 트리의 구현 방법을 설명하며 세부 사항은 다음과 같습니다.

실행 효과는 아래 그림과 같습니다.

php 코드는 다음과 같습니다.

<?php
/* 
用php写的无序树
 */
 class unorderedTree{
 // 节点id计数器
 protected $nodeId=0;
 // 树的深度
 protected $depth=0;
 // 树的节点数,
 protected $nodesCount=0;
 // 树的度 @todo: 使其发挥作用
 public $degree=" to be implent";
 // 根节点id
 // 由于树有多种从根节点开始操作，不想每次遍历树到顶找root，用一个变量始终指向根节点
 protected $rootid=null;
 // 子节点集合, k-v 为 nodeid=>(stdclass)node
 // 一些树的实现常常是采用节点和树同一class，这里节点是使用 stdclass{ data, parent, id , childrenIds} ，因我认为节点和树应为两种对象，且stdclass要轻于树的class
 // 节点格式说明: $this->nodes[nodeId] = new stdclass{ id ,parentId, childrenIds, data }
 // id: 节点id
 // parentId: 节点父节点id
 // childrenIds: 子节点的id 不想每次遍历树确定层次关系 
 // 注意: 节点中, #只保存其自身数据和其子节点id的集合#, 子节点的数据通过从树 $tree->nodes[ $node->childrenIds[a_child_id] ] 访问
 // data: 节点中包含的数据，如节点名称等属性数据
 protected $nodes=array();
 // 用户自定义访问节点
 protected $userVisitFunction=null;
 /* 分组: 类的基本函数 */
 // @todo: 构造树
 public function __construct(){
 }
 // @todo: 销毁树 
 public function __destruct(){
  unset($this->nodes) ;
 }
  //------------ 获取数据类函数---------------
  // 获取树的深度,
  public function getTreeDepth(){
  return $this->depth;
  }
  // 获取树的节点数目 
  public function getCount(){
  return $this->NodesCount;
  }
  // 获取树的度 
  public function getDegree(){
  // @todo: 获取树的度（因为对度暂时没什么需要就不实现了 )
  return $this->degree;
  }
  //获取指定节点
  public function getNode($nodeId){
  if(isset($this->Nodes[$nodeId])){
   return $this->Nodes[$nodeId];
  }
  else{
   return false;
  }
  }
  // 获取最新id
  public function getId(){
  return $this->nodeId;
  }
  //获取指定节点高度
  public function getNodeHeight($nodeId){
  if( array_key_exists($nodeId, $this->nodes) ){
   // 此节点已在树里，高度至少为1，每找到一个父节点+1
   $height=1;
   // 记录此树中已经访问过的节点, 用于防止节点构造时互相parent导致此函数死循环且及时结束查找
   $visitedNodesIds=array();
   // 记录当前操作节点的id
   $cid=$nodeId;
   // 当前节点的父节点必须存在于此树中
   // 不用递归
   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;
  }
  }
  //获取根节点
  public function getRoot(){
  return (!is_null($this->rootid) ) && $this->nodes[$this->rootid];
  }
  //获取指定节点和其所有子节点构成的数组 
  //这是用于获取子树的一个关键基础操作
  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: 获取由指定节点和其所有子节点构建的子树
  public function getSubTree($nodeid){
  }
  //---------------- 数据更新 -----------------
  public function setId($nodeId){
   $this->nodeId=$nodeId;
   return $this;
  }
  // 创建不重复的(树中未被使用的) 新id
  public function seekId(){
  $this->nodeId++;
  return $this->nodeId;
  }
 public function setVisitFunction($userFunction){
  $this->userVisitFunction=$userFunction;
  }
  //插入子节点，默认为插在根节点下
  public function insertNode($parent_id=null , $data=null){
  //注意node不是class tree
  $node = new stdclass; 
  $node->data = $data;
  //树的节点数增加
  $this->nodeCount++;
  // 分配节点id
  $this->seekId();
  $node->id =$this->getId();
  //插入根节点
  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) ){
  // 插在此树已有节点下
   if(is_null($parent_id)){
    $parent_id=$this->rootid;
   }
   $node->parentId = $parent_id;
   $node->childrenIds = array();
   //更新树的最大深度
   $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);
  }
  // --------------- 数据访问 -----
  //广度优先遍历节点的别名, 全名太长了
  public function b($nodeId=null){
  return $this->breadthTraversal($nodeId);
  }
  // 广度优先遍历节点
  public function breadthTraversal($nodeId=null){
  if(is_null($this->rootid)){
   die("此树为空树，不可访问");
  }
  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;
  }
  //深度优先的别名
  public function d($nodeId=null){
  return $this->depthTraversall($nodeId);
  }
  // 深度优先遍历
  // 和广度优先的不同实现只在于array_merge的顺序不同而已 ( php array 忒好用啊忒好用 )
  public function depthTraversall($nodeId=null){
  if(is_null($this->rootid)){
   die("此树为空树，不可访问");
  }
  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;
  }
  //访问单个节点
  public function visit($node){
  if(is_null($this->userVisitFunction )){
   return $node->id;
  }
  else{
   return call_user_func($this->userVisitFunction,$node,$this);
  }
  }
 }
?>

요약: 위 내용은 이 글의 전체 내용입니다. 모든 분들의 공부에 도움이 되었으면 좋겠습니다.

관련 권장 사항:

PHP 디자인 패턴의 기본 지식 및 적용

PHP 바코드의 정의 및 생성 방법

PHP가 파일 확장자를 결정하고 얻는 여러 가지 방법

위 내용은 PHP 비순차 트리 구현 기술의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!