欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

[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
    }
  }
}