How to use recursion to create a binary tree in PHP-PHP Tutorial-php.cn

How to use recursion to create a binary tree in PHP

不言

Release： 2023-04-04 08:40:01

forward

2413 people have browsed it

The content of this article is about how PHP uses recursion to create a binary tree. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

1. Use the principle of recursion, except that the original printing of nodes is changed to the operation of generating nodes and assigning values to nodes

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

Copy after login

2. Preface Traversal: First visit the root node, traverse the left subtree in preorder, and traverse the right subtree in preorder; middle and left

3. Lead the null pointer of each node in the binary tree to a virtual node whose value For a specific value #, the binary tree is processed as an extended binary tree of the original binary tree, and the extended binary tree is used to determine a binary tree through a traversal sequence

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

Copy after login

The above is the detailed content of How to use recursion to create a binary tree in PHP. For more information, please follow other related articles on the PHP Chinese website!