Implémentation de l'arborescence PHP: accès au nœud parent

Question

J'ai un objet Tree implémenté en PHP. Disons que nous avons un arbre comme:

 
Root 
|_ Folder 1 
|_ Folder 2 
    |_ Subfolder 1 

Je peux accéder à Subfolder 1 comme ceci:

$sf1 = $Tree->NavigateTo("Folder 2/Subfolder 1")

Et $sf1 tiendra le nœud Subfolder 1. Je veux mettre en œuvre une méthode GetParentNode(), de sorte que

$parent = $sf1->GetParentNode() // Equivalent to Folder 2

Telle est la définition de l'arbre:

class JaxpTree 
{ 
    /** 
    * @var  JaxpTree|JaxpTreeNode Array of Tree nodes. 
    * @access public 
    */ 
    public $Nodes; 

    /** 
    * @var  JaxpList Array of Tree items. 
    * @access public 
    */ 
    public $ItemList; 
} 

Il fonctionne par l'imbrication des objets d'arbres, si Subfolder 1 est accessible aiment aussi:

$Tree->Nodes["Folder 2"]->Nodes["Subfolder 1"]

qui sera un objet TreeNode:

/** 
* Represents a Tree node. 
* 
* @package  Jaxp.Trees 
* @subpackage TreeNode 
* @since  1.0 
*/ 

class JaxpTreeNode 
{ 
    /** 
    * @var  int Node id. 
    * @access public 
    */ 
    public $Id; 

    /** 
    * @var  JaxpTreeNodeAttributes Contains the node's attributes. 
    * @access public 
    */ 
    public $Attributes; 
} 

Comment puis-je implémenter l'accès au nœud parent ici?

Résolu

La solution est d'ajouter une propriété parent qui contient une référence au nœud parent. Merci!

Answer 1

Vous devez transmettre une référence du parent au noeud.

Answer 2

Vous devez stocker le nœud parent pour chaque nœud (à l'exception du nœud racine qui n'a pas de nœud parent).

Il suffit donc ajouter un parent attribut à votre JaxpTreeNode qui détient le nœud parent ou null si c'est le nœud racine.

Answer 3

Ceci est le code complet je l'ai utilisé pour construire une structure de données d'arbre binaire et ses opérations correspondantes:

<?php 
class Node 
{ 
public $data; 
public $leftChild; 
public $rightChild; 

public function __construct($data) 
    { 
    $this->data=$data; 
    $this->leftChild=null; 
    $this->rightChild=null; 
    } 
public function disp_data() 
    { 
    echo $this->data; 
    } 


}//end class Node 
class BinaryTree 
{ 
public $root; 
//public $s; 
public function __construct() 
    { 
    $this->root=null; 
    //$this->s=file_get_contents('store'); 

    } 
//function to display the tree 
    public function display() 
    { 
    $this->display_tree($this->root); 

    } 
    public function display_tree($local_root) 
    { 

    if($local_root==null) 
    return; 
    $this->display_tree($local_root->leftChild); 
    echo $local_root->data."<br/>"; 
    $this->display_tree($local_root->rightChild); 

    } 
// function to insert a new node 
    public function insert($key) 
    { 
    $newnode=new Node($key); 
     if($this->root==null) 
     { 
     $this->root=$newnode; 
     return; 
     } 
     else 
     { 
     $parent=$this->root; 
     $current=$this->root; 
      while(true) 
      { 
       $parent=$current; 
       //$this->find_order($key,$current->data); 
       if($key==($this->find_order($key,$current->data))) 
        { 
         $current=$current->leftChild; 
         if($current==null) 
         { 
          $parent->leftChild=$newnode; 
          return; 
         }//end if2 
        }//end if1 
       else 
        { 
         $current=$current->rightChild; 
         if($current==null) 
         { 
          $parent->rightChild=$newnode; 
          return; 
         } //end if1      
        } //end else 
      }//end while loop 
     }//end else 

    } //end insert function 

//function to search a particular Node 
public function find($key) 
    { 
    $current=$this->root; 
    while($current->data!=$key) 
      { 
      if($key==$this->find_order($key,$current->data)) 
       { 
       $current=$current->leftChild; 
       } 
      else 
       { 
       $current=$current->rightChild; 
       } 
      if($current==null) 
       return(null); 

      } 
     return($current->data); 
    }// end the function to search 
public function delete1($key) 
    { 
    $current=$this->root; 
    $parent=$this->root; 

    $isLeftChild=true; 
    while($current->data!=$key) 
      { 
      $parent=$current; 
      if($key==($this->find_order($key,$current->data))) 
      { 
       $current=$current->leftChild; 
       $isLeftChild=true; 
      } 
      else 
      { 
       $current=$current->rightChild; 
       $isLeftChild=false; 
      } 
      if($current==null) 
       return(null); 
      }//end while loop 

     echo "<br/><br/>Node to delete:".$current->data; 
    //to delete a leaf node 
    if($current->leftChild==null&&$current->rightChild==null) 
     { 
      if($current==$this->root) 
       $this->root=null; 
      else if($isLeftChild==true) 
      { 
      $parent->leftChild=null; 
      } 
     else 
      { 
      $parent->rightChild=null; 
      } 
     return($current);  
     }//end if1 
    //to delete a node having a leftChild 
    else if($current->rightChild==null) 
     { 
      if($current==$this->root) 
      $this->root=$current->leftChild; 
      else if($isLeftChild==true) 
      { 
      $parent->leftChild=$current->leftChild; 
      } 
      else 
      { 
      $parent->rightChild=$current->leftChild; 
      } 
      return($current); 
     }//end else if1 
    //to delete a node having a rightChild 
    else if($current->leftChild==null) 
     { 
     if($current==$this->root) 
      $this->root=$current->rightChild; 
     else if($isLeftChild==true) 
      { 
      $parent->leftChild=$current->rightChild; 
      } 
     else 
      { 
      $parent->rightChild=$current->rightChild; 
      } 
      return($current); 
     } 
    //to delete a node having both childs 
    else 
     { 
     $successor=$this->get_successor($current); 
     if($current==$this->root) 
      { 
      $this->root=$successor; 

      } 
     else if($isLeftChild==true) 
      { 
      $parent->leftChild=$successor; 
      } 
     else 
      { 
      $parent->rightChild=$successor; 
      }  
     $successor->leftChild=$current->leftChild; 
     return($current); 
     } 


    }//end the function to delete a node 
//Function to find the successor node 
public function get_successor($delNode) 
    { 
    $succParent=$delNode; 
    $successor=$delNode; 
    $temp=$delNode->rightChild; 
    while($temp!=null) 
     { 
      $succParent=$successor; 
      $successor=$temp; 
      $temp=$temp->leftChild; 
     } 
    if($successor!=$delNode->rightChild) 
    { 
     $succParent->leftChild=$successor->rightChild; 
     $successor->rightChild=$delNode->rightChild; 
    } 
    return($successor); 
    } 
//function to find the order of two strings 
public function find_order($str1,$str2) 
    { 
    $str1=strtolower($str1); 
    $str2=strtolower($str2); 
    $i=0; 
    $j=0; 

    $p1=$str1[i]; 
    $p2=$str2[j]; 
    while(true) 
    { 
     if(ord($p1)<ord($p2)||($p1==''&&$p2=='')) 
     { 

      return($str1); 
     } 
     else 
     { 
      if(ord($p1)==ord($p2)) 
      { 
       $p1=$str1[++$i]; 
       $p2=$str2[++$j]; 
       continue; 
      } 
      return($str2); 
     } 
    }//end while 

    } //end function find string order 

public function is_empty() 
    { 
    if($this->root==null) 
     return(true); 
    else 
     return(false); 
    } 
}//end class BinaryTree 
?>