首页 > php教程 > 正文

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

转载 2019-02-11 0 2

本篇文章给大家带来的内容是关于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语言是世界上最好的语言
  • 「进阶篇」docker编排PHP开发坏境
  • 如何在 HTTP 头中隐藏 PHP 版本号
  • PHP作为服务器端语言,有哪些优点?
  • PHP学习jQuery笔记(4)——关于插件
  • 作者信息