php如何完成根据前序与中序遍历结果重建二叉树（代码）

[摘要]本篇文章给大家带来的内容是关于php如何实现根据前序和中序遍历结果重建二叉树（代码），有一定的参考价值，有需要的朋友可以参考一下，希望对你有所帮助。输入某二叉树的前序遍历和中序遍历的结果，请重建出该...

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

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{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
    }
  }
}以上就是php如何实现根据前序和中序遍历结果重建二叉树（代码）的详细内容，更多请关注php中文网其它相关文章！				
				
					微信
					分享
				

网站建设是一个广义的术语，涵盖了许多不同的技能和学科中所使用的生产和维护的网站。



  关键词：php如何完成根据前序与中序遍历结果重建二叉树（代码）