[PHP] 算法-根据前序和中序遍历结果重建二叉树的PHP实现
程序员文章站
2022-05-30 09:28:59
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。 1.前序遍历是中,左,右;中序遍历是左,中,右 2.前序遍历的... ......
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。 1.前序遍历是中,左,右;中序遍历是左,中,右 2.前序遍历的第一个是根结点,中序遍历数组中从开始到根结点的所有是左子树,可以知道左子树的个数,根结点右边的是右子树 3.前序遍历除去0位置的,从1到左子树个数位置是左子树,其他的是右子树 4.确定四个数组,前序左子树数组,前序右子树数组,中序左子树数组,中序右子树数组;递归调用 reconstructbinarytree(pre,in) if(pre.length) return null//递归终止条件 root=pre[0] node=new node(root) //在中序中找根结点的位置 p=0 for p;p<pre.length;p++ if in[p]==root break for i=0;i<pre.length;i++ if i<p //中序左子树数组 inleft[]=in[i] //前序左子树数组 preleft[]=pre[i+1] else if i>p //中序的右子树 inright[]=in[i] //前序的右子树 preright[]=pre[i] node->left=reconstructbinarytree(preleft,inleft) node->right=reconstructbinarytree(preright,inright) return node
<?php class treenode{ var $val; var $left = null; var $right = null; function __construct($val){ $this->val = $val; } }; function reconstructbinarytree($pre, $vin){ $len=count($pre); if($len==0){ return null; } $root=$pre[0]; $node=new treenode($root); for($p=0;$p<$len;$p++){ if($vin[$p]==$root){ break; } } $preleft=array(); $preright=array(); $vinleft=array(); $vinright=array(); for($i=0;$i<$len;$i++){ if($i<$p){ $preleft[]=$pre[$i+1]; $vinleft[]=$vin[$i]; }else if($i>$p){ $preright[]=$pre[$i]; $vinright[]=$vin[$i]; } } $node->left=reconstructbinarytree($preleft,$vinleft); $node->right=reconstructbinarytree($preright,$vinright); return $node; } $pre=array(1,2,4,7,3,5,6,8); $vin=array(4,7,2,1,5,3,8,6); $node=reconstructbinarytree($pre,$vin);; var_dump($node);
object(treenode)#1 (3) { ["val"]=> int(1) ["left"]=> object(treenode)#2 (3) { ["val"]=> int(2) ["left"]=> object(treenode)#3 (3) { ["val"]=> int(4) ["left"]=> null ["right"]=> object(treenode)#4 (3) { ["val"]=> int(7) ["left"]=> null ["right"]=> null } } ["right"]=> null } ["right"]=> object(treenode)#5 (3) { ["val"]=> int(3) ["left"]=> object(treenode)#6 (3) { ["val"]=> int(5) ["left"]=> null ["right"]=> null } ["right"]=> object(treenode)#7 (3) { ["val"]=> int(6) ["left"]=> object(treenode)#8 (3) { ["val"]=> int(8) ["left"]=> null ["right"]=> null } ["right"]=> null } } }
上一篇: 最小化安装的centos7.5上编译安装git2.19
下一篇: linux子系统折腾记 (二)
推荐阅读
-
Python利用前序和中序遍历结果重建二叉树的方法
-
PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解
-
[PHP] 算法-根据前序和中序遍历结果重建二叉树的PHP实现
-
PHP根据树的前序遍历和中序遍历构造树并输出后序遍历的方法
-
Python利用前序和中序遍历结果重建二叉树的方法
-
PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解
-
[PHP] 算法-根据前序和中序遍历结果重建二叉树的PHP实现
-
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树
-
根据前序序列和中序序列,重建一颗树(PHP递归实现)
-
根据前序序列和中序序列,重建一颗树(PHP递归实现)