Home >Backend Development >PHP Tutorial >How to use recursion to create a binary tree in PHP

How to use recursion to create a binary tree in PHP

不言
不言forward
2018-09-30 14:24:422422browse

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=='#'){*T=NULL;}else{malloc();(*T)->data=ch;createFunc((*T)->lchild);createFunc((*T)->rchild);}

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

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!

Statement:
This article is reproduced at:cnblogs.com. If there is any infringement, please contact admin@php.cn delete