Maison >développement back-end >tutoriel php >Comment utiliser la récursivité pour créer un arbre binaire en PHP

Comment utiliser la récursivité pour créer un arbre binaire en PHP

不言
不言avant
2018-09-30 14:24:422424parcourir

Le contenu de cet article explique comment PHP utilise la récursion pour créer un arbre binaire. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.

1. Utilisez le principe de récursion, sauf que l'impression originale des nœuds est modifiée en l'opération de génération de nœuds et d'attribution de valeurs aux nœuds

if(ch=='#'){*T=NULL;}else{malloc();(*T)->data=ch;createFunc((*T)->lchild);createFunc((*T)->rchild);}

2. Traversée de pré-ordre : visitez d'abord le nœud racine, parcourez le sous-arbre de gauche en pré-ordre et parcourez le sous-arbre de droite en pré-ordre

3. , Sa valeur est une valeur spécifique #, et l'arbre binaire traité est un arbre binaire étendu de l'arbre binaire d'origine. L'arbre binaire étendu réalise une séquence de parcours pour déterminer un arbre binaire

.
<?php
class BinTree{
        public $data;
        public $left;
        public $right;
}
//前序遍历生成二叉树
function createBinTree(){
        $handle=fopen("php://stdin","r");
        $e=trim(fgets($handle));
        if($e=="#"){
                $binTree=null;
        }else{
                $binTree=new BinTree();
                $binTree->data=$e;
                $binTree->left=createBinTree();
                $binTree->right=createBinTree();
        }  
        return $binTree;
}   
$tree=createBinTree();
var_dump($tree);
A
B
#
D
#
#
C
#
#
object(BinTree)#1 (3) {
  ["data"]=>
  string(1) "A"
  ["left"]=>
  object(BinTree)#2 (3) {
    ["data"]=>
    string(1) "B"
    ["left"]=>
    NULL
    ["right"]=>
    object(BinTree)#3 (3) {
      ["data"]=>
      string(1) "D"
      ["left"]=>
      NULL
      ["right"]=>
      NULL
    }
  }
  ["right"]=>
  object(BinTree)#4 (3) {
    ["data"]=>
    string(1) "C"
    ["left"]=>
    NULL
    ["right"]=>
    NULL
  }
}

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

Déclaration:
Cet article est reproduit dans:. en cas de violation, veuillez contacter admin@php.cn Supprimer