11.3 树的遍历：LDR，LRD，VLR 相关代码
- VLR：前序遍历
- LDR：中序遍历
- LRD：后序遍历
<?phpclassLeaf{public$leftLeaf;public$rightLeaf;public$label;publicfunction__construct($label){$this->label=$label;}}/**
* 前序遍历
* @param $leaf Leaf
* @param string $result
* @return bool
*/functionVLR($leaf,&$result){if(!$leaf){returnfalse;}$result.=$leaf->label;VLR($leaf->leftLeaf,$result);VLR($leaf->rightLeaf,$result);}/**
* 中序遍历
* @param $leaf Leaf
* @param $result string
* @return bool
*/functionLDR($leaf,&$result){if(!$leaf){returnfalse;}if($leaf->leftLeaf){LDR($leaf->leftLeaf,$result);}$result.=$leaf->label;LDR($leaf->rightLeaf,$result);}/**
* 后续遍历
* @param $leaf Leaf
* @param $result string
* @return bool
*/functionLRD($leaf,&$result){if(!$leaf){returnfalse;}LRD($leaf->leftLeaf,$result);LRD($leaf->rightLeaf,$result);$result.=$leaf->label;returnfalse;}// 相关记法部分/**
* 解析前缀记法
* @param $string
* @return mixed
*/functionParseStringVLR($string){global$supportOperation;$stringIndex=strlen($string);$string=str_split($string);while($stringIndex>0){$stringIndex--;if(in_array($string[$stringIndex],$supportOperation)){$string[$stringIndex]=calculate($string[$stringIndex],$string[$stringIndex+1],$string[$stringIndex+2]);unset($string[$stringIndex+1]);unset($string[$stringIndex+2]);$string=array_values($string);$stringIndex=count($string);}}return$string[0];}/**
* 解析后缀记法
* @param $string
* @return mixed
*/functionParseStringLRD($string){global$supportOperation;$length=strlen($string)-1;$string=str_split($string);$stringIndex=-1;while($stringIndex<$length){$stringIndex++;if(in_array($string[$stringIndex],$supportOperation)){$string[$stringIndex]=calculate($string[$stringIndex],$string[$stringIndex-2],$string[$stringIndex-1]);unset($string[$stringIndex-1]);unset($string[$stringIndex-2]);$string=array_values($string);$length=count($string)-1;$stringIndex=0;}}return$string[0];}/**
* 解析中缀记法
* @param $string
* @return mixed
*/functionParseStringLDR($string){global$supportOperation;$length=strlen($string)-1;$string=str_split($string);$stringIndex=-1;while($stringIndex<$length){$stringIndex++;if(in_array($string[$stringIndex],$supportOperation)){$string[$stringIndex]=calculate($string[$stringIndex],$string[$stringIndex-1],$string[$stringIndex+1]);unset($string[$stringIndex-1]);unset($string[$stringIndex+1]);$string=array_values($string);$length=count($string)-1;$stringIndex=0;}}return$string[0];}$supportOperation=['+','-','*','/'];functioncalculate($operation,$data1,$data2){$result=0;switch($operation){case"+":$result=$data1+$data2;break;case"-":$result=$data1-$data2;break;case"*":$result=$data1*$data2;break;case"/":if($data2!=0){$result=round($data1/$data2,2);}break;default:$result=0;}return$result;}然后这里是对应的调用代码：
<?phprequire_once__DIR__.DIRECTORY_SEPARATOR."树的遍历.php";functioncreateLeaf($x,$y){$indexLeaf=newLeaf('+');$indexLeaf->leftLeaf=newLeaf('*');$indexLeaf->rightLeaf=newLeaf('+');$indexLeaf->leftLeaf->leftLeaf=newLeaf('+');$indexLeaf->leftLeaf->leftLeaf->leftLeaf=newLeaf($x);$indexLeaf->leftLeaf->leftLeaf->rightLeaf=newLeaf($y);$indexLeaf->leftLeaf->rightLeaf=newLeaf(2);$indexLeaf->rightLeaf->leftLeaf=newLeaf('-');$indexLeaf->rightLeaf->rightLeaf=newLeaf(3);$indexLeaf->rightLeaf->leftLeaf->leftLeaf=newLeaf($x);$indexLeaf->rightLeaf->leftLeaf->rightLeaf=newLeaf(4);return$indexLeaf;}$x=2;$y=4;$result=13;$indexLeaf=createLeaf($x,$y);$string='';VLR($indexLeaf,$string);print$string.PHP_EOL;printParseStringVLR($string).PHP_EOL;$string='';LRD($indexLeaf,$string);print$string.PHP_EOL;printParseStringLRD($string).PHP_EOL;$string='';LDR($indexLeaf,$string);print$string.PHP_EOL;printParseStringLDR($string);对应的树图如下所示：
其中x=2，y=4。