构造树是数据结构中的重要问题之一。给定一棵二叉树的前序遍历和中序遍历,如何构造这颗二叉树的正确结构呢?本文将详细讲解PHP根据树的前序遍历和中序遍历构造树并输出后序遍历的方法。
给定一个二叉树的前序遍历和中序遍历,我们可以通过前序遍历确定树的根节点,再通过中序遍历确定左右子树的节点,从而得到树的结构。具体流程如下:
以下是PHP中实现从前序遍历和中序遍历恢复二叉树的函数:
/**
* 通过前序遍历和中序遍历构造二叉树
*
* @param array $preorder 前序遍历数组
* @param array $inorder 中序遍历数组
* @return TreeNode|null 返回根节点
*/
function buildTree($preorder, $inorder) {
if (!$preorder || !$inorder) {
return null;
}
// 根节点
$rootVal = $preorder[0];
$rootIndex = array_search($rootVal, $inorder);
$rootNode = new TreeNode($rootVal);
// 构造左子树
$leftInorder = array_slice($inorder, 0, $rootIndex);
$leftPreorder = array_slice($preorder, 1, $rootIndex);
$rootNode->left = buildTree($leftPreorder, $leftInorder);
// 构造右子树
$rightInorder = array_slice($inorder, $rootIndex + 1);
$rightPreorder = array_slice($preorder, $rootIndex + 1);
$rootNode->right = buildTree($rightPreorder, $rightInorder);
echo $rootNode->val . " "; // 输出后序遍历
return $rootNode;
}
由于构造的过程以后序遍历的方式记录树结构,故在上述代码中输出了树的后序遍历结果,用于验证构造是否正确。
下面通过两个示例说明函数的使用方法。
已知二叉树的前序遍历是[3,9,20,15,7],中序遍历是[9,3,15,20,7],构造出对应的二叉树并输出后序遍历结果。
class TreeNode {
public $val = null;
public $left = null;
public $right = null;
function __construct($value) { $this->val = $value; }
}
$preorder = [3, 9, 20, 15, 7];
$inorder = [9, 3, 15, 20, 7];
buildTree($preorder, $inorder); // 输出结果:9 15 7 20 3
输出的结果为9 15 7 20 3
,与实际后序遍历结果一致,说明构造成功。
已知二叉树的前序遍历是[1, 2, 4, 5, 7, 8, 3, 6],中序遍历是[4, 2, 7, 5, 8, 1, 3, 6],构造出对应的二叉树并输出后序遍历结果。
$preorder = [1, 2, 4, 5, 7, 8, 3, 6];
$inorder = [4, 2, 7, 5, 8, 1, 3, 6];
buildTree($preorder, $inorder); // 输出结果:4 7 8 5 2 6 3 1
输出的结果为4 7 8 5 2 6 3 1
,与实际后序遍历结果一致,说明构造成功。
本文详细讲解了PHP根据树的前序遍历和中序遍历构造树并输出后序遍历的方法。该方法对于二叉树的构造和遍历有着重要的作用,在实际应用中也有广泛的应用。
本文链接:http://task.lmcjl.com/news/7803.html