[php]
<?php
#树节点
class Node {
public $data = null;
public $parent = null;
public $left = null;
public $right = null;
}
#根据先序和中序遍历数组建立二叉树，注意是二叉树，不是二叉排序树,而且条件是树没有相同的值
#思想是使用先序数组确定根节点，然后通过中序数组找到根节点的左右子树节点
#@param pre 前序遍历数组
#@param in 中序遍历数组
#@param pre_s 对于前序数组的构建树开始坐标
#@param pre_e 对于前序数组的构建树结束坐标
#@param in_s 对于中序数组的构建树起始坐标
#@param p 构建树的根节点的父节点
function build_bt_prein($pre, $in, $pre_s, $pre_e, $in_s, $p) {
$root = new Node();
$root->parent = $p;
$root->data = $pre[$pre_s]; #根节点数据在pre数组的第一位
$root_inx = array_search($root->data, $in); #根节点在in数组中的坐标
#我把左右子树的pre数组，in数组的开始结束坐标写出来，便于理解
$pre_l_s = $pre_s + 1; #左子树在pre数组的开始坐标
$pre_l_e = $pre_s + ($root_inx – $in_s); #左子树在pre数组的结束坐标，其中root_inx-in_s为左子树长度
$pre_r_s = $pre_l_e + 1; #右子树开始坐标
$pre_r_e = $pre_e; #右子树结束坐标
$in_l_s = $in_s; #左子树在in数组开始坐标
$in_r_s = $root_inx + 1; #右子树在in数组开始坐标
#注意此处
if ($pre_l_s <= $pre_l_e) $root->left = build_bt_prein($pre, $in, $pre_l_s, $pre_l_e, $in_l_s, $root);
if ($pre_r_s <= $pre_r_e) $root->right = build_bt_prein($pre, $in, $pre_r_s, $pre_r_e, $in_r_s, $root);
return $root;
}
#中序遍历
function inorder_traverse($root) {
if ($root->left != null) inorder_traverse($root->left);
echo $root->data . " ";
if ($root->right != null) inorder_traverse($root->right);
}
$pre = array(7, 10, 4, 3, 1, 2, 8, 11);
$in = array(4, 10, 3, 1, 7, 11, 8, 2);
// $pre = array(2, 7);
// $in = array(7, 2);
$root = build_bt_prein($pre, $in, 0, count($pre) – 1, 0, null);
inorder_traverse($root);
?>
[/php]
