Heim >Backend-Entwicklung >PHP-Tutorial >So verwenden Sie Rekursion, um einen Binärbaum in PHP zu erstellen

So verwenden Sie Rekursion, um einen Binärbaum in PHP zu erstellen

不言
不言nach vorne
2018-09-30 14:24:422424Durchsuche

Der Inhalt dieses Artikels handelt davon, wie PHP Rekursion verwendet, um einen Binärbaum zu erstellen. Ich hoffe, dass er für Freunde hilfreich ist.

1. Verwenden Sie das Prinzip der Rekursion, mit der Ausnahme, dass dort, wo der Knoten ursprünglich gedruckt wurde, der Vorgang geändert wird, bei dem der Knoten generiert und dem Knoten ein Wert zugewiesen wird

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

2. Vorwort-Traversierung: Besuchen Sie zuerst den Wurzelknoten, durchqueren Sie den linken Teilbaum in Vorbestellung und durchqueren Sie den rechten Teilbaum in Vorbestellung.

3 Führen Sie den Nullzeiger jedes Knotens im Binärbaum zu einem virtuellen Knoten, dessen Wert Für einen bestimmten Wert # wird der Binärbaum als erweiterter Binärbaum des ursprünglichen Binärbaums verarbeitet. Der erweiterte Binärbaum erreicht eine Durchlaufsequenz, um einen Binärbaum zu bestimmen

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

Das obige ist der detaillierte Inhalt vonSo verwenden Sie Rekursion, um einen Binärbaum in PHP zu erstellen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Stellungnahme:
Dieser Artikel ist reproduziert unter:cnblogs.com. Bei Verstößen wenden Sie sich bitte an admin@php.cn löschen