선주문 및 순차 순회 결과를 기반으로 PHP에서 이진 트리를 재구성하는 방법(코드)

이 문서의 내용은 선주문 및 순차 순회 결과를 기반으로 PHP가 이진 트리(코드)를 재구성하는 방법에 대한 것입니다. 필요한 친구가 참고할 수 있기를 바랍니다. 당신에게 도움이 되십시오.

이진 트리의 선순 순회 및 순차 순회 결과를 입력하고 이진 트리를 재구성하세요. 입력된 선순순회와 순순순회 결과에 반복되는 숫자가 포함되지 않는다고 가정한다. 예를 들어 선순 순회 시퀀스 {1,2,4,7,3,5,6,8}과 순차 순회 시퀀스 {4,7,2,1,5,3,8을 입력하면 ,6}, 이진 트리를 재구성하고 반환합니다. ... 왼쪽 하위 트리입니다. 루트 노드 오른쪽에 있는 오른쪽 하위 트리가 오른쪽 하위 트리입니다.
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 중국어 웹사이트의 기타 관련 기사를 참조하세요!