3v4l.org

run code in 300+ PHP versions simultaneously
<?php /* 构造如下一棵树: a / | \ b c d / \ | e f g | h 深度优先遍历(DFT): a b e f h c d g 广度优先遍历(BFT): a b c d e f g h */ $h = new TreeNode('h'); $g = new TreeNode('g'); $f = new TreeNode('f', [$h]); $e = new TreeNode('e'); $d = new TreeNode('d', [$g]); $c = new TreeNode('c'); $b = new TreeNode('b', [$e, $f]); $a = new TreeNode('a', [$b, $c, $d]); $tree = &$a; dft($tree); echo "\n----\n"; bft($tree); exit(); class TreeNode { public $data; public $children = []; public function __construct($data, $children = []) { $this->data = $data; $this->children = array_merge($this->children, $children); } } /** * depth first traversal * * 借助栈实现 */ function dft($tree) { $stack = array($tree, "\n"); while (!empty($stack)) { $node = array_pop($stack); if (is_string($node)) { echo $node; } else { echo $node->data; if ($node->children) { array_push($stack, "\n"); $children = array_reverse($node->children); foreach ($children as $c) { array_push($stack, "\t"); array_push($stack, $c); } array_push($stack, "\n"); } } } } /** * breadth first traversal * * 借助队列实现 */ function bft($tree) { $queue = array($tree, "\n"); while(!empty($queue)) { $node = array_shift($queue); if (is_string($node)) { echo $node; } else { echo $node->data; if ($node->children) { foreach ($node->children as $c) { array_push($queue, $c); array_push($queue, "\t"); } array_push($queue, "\n"); } } } }
Finding entry points
Branch analysis from position: 0
1 jumps found. (Code = 79) Position 1 = -2
filename:       /in/fg7g9
function name:  (null)
number of ops:  53
compiled vars:  !0 = $h, !1 = $g, !2 = $f, !3 = $e, !4 = $d, !5 = $c, !6 = $b, !7 = $a, !8 = $tree
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
   28     0  E >   NEW                                              $9      'TreeNode'
          1        SEND_VAL_EX                                              'h'
          2        DO_FCALL                                      0          
          3        ASSIGN                                                   !0, $9
   29     4        NEW                                              $12     'TreeNode'
          5        SEND_VAL_EX                                              'g'
          6        DO_FCALL                                      0          
          7        ASSIGN                                                   !1, $12
   30     8        NEW                                              $15     'TreeNode'
          9        SEND_VAL_EX                                              'f'
         10        INIT_ARRAY                                       ~16     !0
         11        SEND_VAL_EX                                              ~16
         12        DO_FCALL                                      0          
         13        ASSIGN                                                   !2, $15
   31    14        NEW                                              $19     'TreeNode'
         15        SEND_VAL_EX                                              'e'
         16        DO_FCALL                                      0          
         17        ASSIGN                                                   !3, $19
   32    18        NEW                                              $22     'TreeNode'
         19        SEND_VAL_EX                                              'd'
         20        INIT_ARRAY                                       ~23     !1
         21        SEND_VAL_EX                                              ~23
         22        DO_FCALL                                      0          
         23        ASSIGN                                                   !4, $22
   33    24        NEW                                              $26     'TreeNode'
         25        SEND_VAL_EX                                              'c'
         26        DO_FCALL                                      0          
         27        ASSIGN                                                   !5, $26
   34    28        NEW                                              $29     'TreeNode'
         29        SEND_VAL_EX                                              'b'
         30        INIT_ARRAY                                       ~30     !3
         31        ADD_ARRAY_ELEMENT                                ~30     !2
         32        SEND_VAL_EX                                              ~30
         33        DO_FCALL                                      0          
         34        ASSIGN                                                   !6, $29
   35    35        NEW                                              $33     'TreeNode'
         36        SEND_VAL_EX                                              'a'
         37        INIT_ARRAY                                       ~34     !6
         38        ADD_ARRAY_ELEMENT                                ~34     !5
         39        ADD_ARRAY_ELEMENT                                ~34     !4
         40        SEND_VAL_EX                                              ~34
         41        DO_FCALL                                      0          
         42        ASSIGN                                                   !7, $33
   36    43        ASSIGN_REF                                               !8, !7
   38    44        INIT_FCALL_BY_NAME                                       'dft'
         45        SEND_VAR_EX                                              !8
         46        DO_FCALL                                      0          
   39    47        ECHO                                                     '%0A----%0A'
   40    48        INIT_FCALL_BY_NAME                                       'bft'
         49        SEND_VAR_EX                                              !8
         50        DO_FCALL                                      0          
   42    51      > EXIT                                                     
  102    52*     > RETURN                                                   1

Function dft:
Finding entry points
Branch analysis from position: 0
1 jumps found. (Code = 42) Position 1 = 42
Branch analysis from position: 42
2 jumps found. (Code = 44) Position 1 = 45, Position 2 = 5
Branch analysis from position: 45
1 jumps found. (Code = 62) Position 1 = -2
Branch analysis from position: 5
2 jumps found. (Code = 43) Position 1 = 11, Position 2 = 13
Branch analysis from position: 11
1 jumps found. (Code = 42) Position 1 = 42
Branch analysis from position: 42
Branch analysis from position: 13
2 jumps found. (Code = 43) Position 1 = 17, Position 2 = 42
Branch analysis from position: 17
2 jumps found. (Code = 77) Position 1 = 27, Position 2 = 37
Branch analysis from position: 27
2 jumps found. (Code = 78) Position 1 = 28, Position 2 = 37
Branch analysis from position: 28
1 jumps found. (Code = 42) Position 1 = 27
Branch analysis from position: 27
Branch analysis from position: 37
2 jumps found. (Code = 44) Position 1 = 45, Position 2 = 5
Branch analysis from position: 45
Branch analysis from position: 5
Branch analysis from position: 37
Branch analysis from position: 42
filename:       /in/fg7g9
function name:  dft
number of ops:  46
compiled vars:  !0 = $tree, !1 = $stack, !2 = $node, !3 = $children, !4 = $c
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
   59     0  E >   RECV                                             !0      
   60     1        INIT_ARRAY                                       ~5      !0
          2        ADD_ARRAY_ELEMENT                                ~5      '%0A'
          3        ASSIGN                                                   !1, ~5
   61     4      > JMP                                                      ->42
   62     5    >   INIT_FCALL                                               'array_pop'
          6        SEND_REF                                                 !1
          7        DO_ICALL                                         $7      
          8        ASSIGN                                                   !2, $7
   63     9        TYPE_CHECK                                   64          !2
         10      > JMPZ                                                     ~9, ->13
   64    11    >   ECHO                                                     !2
   63    12      > JMP                                                      ->42
   66    13    >   FETCH_OBJ_R                                      ~10     !2, 'data'
         14        ECHO                                                     ~10
   67    15        FETCH_OBJ_R                                      ~11     !2, 'children'
         16      > JMPZ                                                     ~11, ->42
   68    17    >   INIT_FCALL                                               'array_push'
         18        SEND_REF                                                 !1
         19        SEND_VAL                                                 '%0A'
         20        DO_ICALL                                                 
   69    21        INIT_FCALL                                               'array_reverse'
         22        FETCH_OBJ_R                                      ~13     !2, 'children'
         23        SEND_VAL                                                 ~13
         24        DO_ICALL                                         $14     
         25        ASSIGN                                                   !3, $14
   70    26      > FE_RESET_R                                       $16     !3, ->37
         27    > > FE_FETCH_R                                               $16, !4, ->37
   71    28    >   INIT_FCALL                                               'array_push'
         29        SEND_REF                                                 !1
         30        SEND_VAL                                                 '%09'
         31        DO_ICALL                                                 
   72    32        INIT_FCALL                                               'array_push'
         33        SEND_REF                                                 !1
         34        SEND_VAR                                                 !4
         35        DO_ICALL                                                 
   70    36      > JMP                                                      ->27
         37    >   FE_FREE                                                  $16
   74    38        INIT_FCALL                                               'array_push'
         39        SEND_REF                                                 !1
         40        SEND_VAL                                                 '%0A'
         41        DO_ICALL                                                 
   61    42    >   ISSET_ISEMPTY_CV                                 ~20     !1
         43        BOOL_NOT                                         ~21     ~20
         44      > JMPNZ                                                    ~21, ->5
   78    45    > > RETURN                                                   null

End of function dft

Function bft:
Finding entry points
Branch analysis from position: 0
1 jumps found. (Code = 42) Position 1 = 34
Branch analysis from position: 34
2 jumps found. (Code = 44) Position 1 = 37, Position 2 = 5
Branch analysis from position: 37
1 jumps found. (Code = 62) Position 1 = -2
Branch analysis from position: 5
2 jumps found. (Code = 43) Position 1 = 11, Position 2 = 13
Branch analysis from position: 11
1 jumps found. (Code = 42) Position 1 = 34
Branch analysis from position: 34
Branch analysis from position: 13
2 jumps found. (Code = 43) Position 1 = 17, Position 2 = 34
Branch analysis from position: 17
2 jumps found. (Code = 77) Position 1 = 19, Position 2 = 29
Branch analysis from position: 19
2 jumps found. (Code = 78) Position 1 = 20, Position 2 = 29
Branch analysis from position: 20
1 jumps found. (Code = 42) Position 1 = 19
Branch analysis from position: 19
Branch analysis from position: 29
2 jumps found. (Code = 44) Position 1 = 37, Position 2 = 5
Branch analysis from position: 37
Branch analysis from position: 5
Branch analysis from position: 29
Branch analysis from position: 34
filename:       /in/fg7g9
function name:  bft
number of ops:  38
compiled vars:  !0 = $tree, !1 = $queue, !2 = $node, !3 = $c
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
   85     0  E >   RECV                                             !0      
   86     1        INIT_ARRAY                                       ~4      !0
          2        ADD_ARRAY_ELEMENT                                ~4      '%0A'
          3        ASSIGN                                                   !1, ~4
   87     4      > JMP                                                      ->34
   88     5    >   INIT_FCALL                                               'array_shift'
          6        SEND_REF                                                 !1
          7        DO_ICALL                                         $6      
          8        ASSIGN                                                   !2, $6
   89     9        TYPE_CHECK                                   64          !2
         10      > JMPZ                                                     ~8, ->13
   90    11    >   ECHO                                                     !2
   89    12      > JMP                                                      ->34
   92    13    >   FETCH_OBJ_R                                      ~9      !2, 'data'
         14        ECHO                                                     ~9
   93    15        FETCH_OBJ_R                                      ~10     !2, 'children'
         16      > JMPZ                                                     ~10, ->34
   94    17    >   FETCH_OBJ_R                                      ~11     !2, 'children'
         18      > FE_RESET_R                                       $12     ~11, ->29
         19    > > FE_FETCH_R                                               $12, !3, ->29
   95    20    >   INIT_FCALL                                               'array_push'
         21        SEND_REF                                                 !1
         22        SEND_VAR                                                 !3
         23        DO_ICALL                                                 
   96    24        INIT_FCALL                                               'array_push'
         25        SEND_REF                                                 !1
         26        SEND_VAL                                                 '%09'
         27        DO_ICALL                                                 
   94    28      > JMP                                                      ->19
         29    >   FE_FREE                                                  $12
   98    30        INIT_FCALL                                               'array_push'
         31        SEND_REF                                                 !1
         32        SEND_VAL                                                 '%0A'
         33        DO_ICALL                                                 
   87    34    >   ISSET_ISEMPTY_CV                                 ~16     !1
         35        BOOL_NOT                                         ~17     ~16
         36      > JMPNZ                                                    ~17, ->5
  102    37    > > RETURN                                                   null

End of function bft

Class TreeNode:
Function __construct:
Finding entry points
Branch analysis from position: 0
1 jumps found. (Code = 62) Position 1 = -2
filename:       /in/fg7g9
function name:  __construct
number of ops:  12
compiled vars:  !0 = $data, !1 = $children
line      #* E I O op                           fetch          ext  return  operands
-------------------------------------------------------------------------------------
   48     0  E >   RECV                                             !0      
          1        RECV_INIT                                        !1      <array>
   49     2        ASSIGN_OBJ                                               'data'
          3        OP_DATA                                                  !0
   50     4        INIT_FCALL                                               'array_merge'
          5        FETCH_OBJ_R                                      ~4      'children'
          6        SEND_VAL                                                 ~4
          7        SEND_VAR                                                 !1
          8        DO_ICALL                                         $5      
          9        ASSIGN_OBJ                                               'children'
         10        OP_DATA                                                  $5
   51    11      > RETURN                                                   null

End of function __construct

End of class TreeNode.

Generated using Vulcan Logic Dumper, using php 8.0.0


preferences:
162.79 ms | 1443 KiB | 18 Q