首页 > php教程 > 正文

「php」php如何实现根据前序和中序遍历结果重建二叉树(代码)

转载 2019-02-11 0 21

本篇文章给大家带来的内容是关于php如何实现根据前序和中序遍历结果重建二叉树(代码),有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。

「php」php如何实现根据前序和中序遍历结果重建二叉树(代码)

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

if in[p]==root break

for i=0;i

if i

//中序左子树数组

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」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

if($vin[$p]==$root){

break;

}

}

$preLeft=array();

$preRight=array();

$vinLeft=array();

$vinRight=array();

for($i=0;$i

if($i

$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

}

}

}

「php」php如何实现根据前序和中序遍历结果重建二叉树(代码)

以上就是php如何实现根据前序和中序遍历结果重建二叉树(代码)的详细内容

相关文章


  • php有两个经典类库可以让你事半功倍,php程序员你们知道?
  • 不懂PHP又找不到合适的PHP程序猿肿么办?看这里
  • 扣丁学堂PHP培训简述PHP语言的基础知识和特点有哪些
  • 跟着MISS学PHP版本升级:linux下把PHP当前版本升级到5.6
  • 「php」如何使用php中ftp的上传和下载功能的实现代码
  • 7月10日直播提醒!北邮在线PHP权威课程PHP:环境配置教程
  • JavaEE和PHP有什么区别 扣丁学堂JavaEE和PHP学哪个好
  • 青岛PHP培训机构哪个好 零基础看PHP视频教程能学会吗?