PHP树实现：访问父节点

Question

我有一个用PHP实现的自己的Tree对象。假设我们有一棵树，如：

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

我可以访问Subfolder 1这样的：

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

而且$sf1将举行Subfolder 1节点。我想实现一个GetParentNode()方法，使

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

这是树的定义：

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

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

它的工作原理通过嵌套树对象，因此，子文件夹1还可以访问，如：

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

这将是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; 
} 

如何在这里实现父节点访问？

解决

解决方案是增加包含到父节点的参考的父属性。 谢谢！

Answer 1

您必须将父对象的引用传递给节点。

Answer 2

您需要存储每个节点的父节点（除没有父节点的根节点外）。

所以只需要加一个父属性您JaxpTreeNode持有父节点或空如果它的根节点。

Answer 3

这是完整的代码我用来建立一个二叉树数据结构及其相应的操作：

<?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 
?>