So rekonstruieren Sie einen Binärbaum in PHP basierend auf den Ergebnissen der Vorbestellungs- und In-Order-Traversierung (Code)

Der Inhalt dieses Artikels handelt davon, wie PHP einen Binärbaum (Code) basierend auf den Ergebnissen der Vorbestellung und der Durchquerung in der Reihenfolge rekonstruieren kann. Ich hoffe, dass er einen gewissen Referenzwert hat Es wird Ihnen hilfreich sein.

Geben Sie die Ergebnisse der Durchquerung vor der Bestellung und der Durchquerung in der Reihenfolge eines Binärbaums ein. Bitte rekonstruieren Sie den Binärbaum. Gehen Sie davon aus, dass die Ergebnisse der eingegebenen Durchquerung vor der Bestellung und der Durchquerung in der Reihenfolge keine wiederholten Zahlen enthalten. Wenn Sie beispielsweise die Durchlaufsequenz vor der Reihenfolge {1,2,4,7,3,5,6,8} und die Durchlaufsequenz in der Reihenfolge {4,7,2,1,5,3,8} eingeben ,6}, rekonstruieren Sie dann den Binärbaum und kehren Sie zurück.
1. Die Durchquerung vor der Bestellung erfolgt in der Mitte, links und rechts. Die Durchquerung in der Mitte erfolgt nach links, in der Mitte und nach rechts Alle Knoten des Arrays sind linke Teilbäume. Der rechte Teilbaum rechts vom Wurzelknoten ist der rechte Teilbaum 0-Position, von 1 bis 1 ist die Anzahl der linken Teilbäume Der linke Teilbaum, die anderen sind der rechte Teilbaum
4. Bestimmen Sie vier Arrays, das Vorbestellungs-Array des linken Teilbaums, das Vorbestellungs-Array des rechten Teilbaums, das Inorder-Array des linken Teilbaums inorder rechter Teilbaum-Array;

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

Das obige ist der detaillierte Inhalt vonSo rekonstruieren Sie einen Binärbaum in PHP basierend auf den Ergebnissen der Vorbestellungs- und In-Order-Traversierung (Code). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!