PHP根据树的前序遍历和中序遍历构造树并输出后序遍历的方法

本文实例讲述了PHP根据树的前序遍历中序遍历构造树并输出后序遍历的方法。分享给大家供大家参考,具体如下:

先来看看前序遍历、中序遍历与后序遍历原理图:

根据树的前序遍历和中序遍历构造树并输出后序遍历代码如下:

<?php

class BinaryTreeNode{

public $m_value;

public $m_left;

public $m_right;

}

function ConstructCore($preorder,$inorder){

if(count($preorder)!=count($inorder) || count($preorder)==0 || count($inorder)==0)

return null;

$headNode=new BinaryTreeNode;

$headNode->m_value=$preorder[0];

if(count($preorder)==1){

$headNode->m_left=null;

$headNode->m_right=null;

return $headNode;

}

array_shift($preorder);

$pos=array_search($headNode->m_value,$inorder);

$leftin=array_slice($inorder,0,$pos);

$rightin=array_slice($inorder,$pos+1);

$leftpre=array_slice($preorder,0,$pos);

$rightpre=array_slice($preorder,$pos);

$headNode->m_left=ConstructCore($leftpre,$leftin);

$headNode->m_right=ConstructCore($rightpre,$rightin);

return $headNode;

}

$pre=array(1,2,4,7,3,5,6,8);

$in=array(4,7,2,1,5,3,8,6);

$tree=ConstructCore($pre,$in);

function tail($tree){

if($tree->m_right!=null)

echo tail($tree->m_right);

if($tree->m_left!=null)

echo tail($tree->m_left);

echo $tree->m_value;

}

tail($tree);

?>

运行结果:

86537421

更多关于PHP相关内容感兴趣的读者可查看本站专题:《PHP数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)操作技巧大全》、《PHP常用遍历算法与技巧总结》及《PHP数学运算技巧总结》

希望本文所述对大家PHP程序设计有所帮助。

以上是 PHP根据树的前序遍历和中序遍历构造树并输出后序遍历的方法 的全部内容, 来源链接: utcz.com/p/221326.html

回到顶部