/** * PHP Binary Tree Algorithms * Created on 2017-5-6 * Author entner * Email 1185087164@qq.com */
Introduction
Binary tree is strictly defined. It has a good demonstration function for data storage and calculation.
Many people say that the binary tree is useless for eggs. I think it is his salary and company that make him cross the barrier. Many people also learn some knowledge about trees and find it useless. What I want to say is that reading a book does not reflect the value of this book, and it takes several more books to distinguish you from others. Come out.
In addition, some common scenes of trees are cited to justify what I have said.
Compiler expression processing
Fast Search and Sort
File Compression
File System Management
Game Scene Division, Monitoring and Rendering
I admit that you don't have direct contact with many of these things, but the key is to learn a kind of thinking and design.
Ten thousand steps back can also add a little insight:
I. Binary tree abstract data type operation entries
There are too many operations on books. I just list some common ones, interesting beliefs and skills to find good ones. - InitTree Constructs Empty Trees - Value returns the value of a node in the tree - Assign assigns value to a node in the tree - Parent returns the parent of a non-root node, otherwise it returns empty - LeftChild returns to the leftmost child of a non-leaf node, otherwise returns to null
2. Common Data Structures of Steganographic Binary Trees
Steganography will make you remember more deeply, but also exercise abstract logical thinking. If you can't understand it, you can read it several times and check the relevant information again. It shouldn't be a big problem. You can even find a piece of paper to write it by heart.
/**
* InitTree Initialization Tree
*
*
Typedef int TElementType // Construct a data type
Typedef Struct Tree {// Construct Binary Tree Abstract Data Types
TElementType data; // Declare an array, first build a tree
Struct Tree *leftChild; // Left Child Node
Struct Tree *rightChild; // Right Child Node
}Tree;
*／
/**
* Value gets the node of the tree (preface traversal)
* Return returns the acquired node value
Status Value(Tree *T，int e){
if(T == null){
return error;
}
e = T->Value(T->leftChild);
e = T->Value(T->rightChild);
return e;
}
*/
/**
* Assign assigns a node in the tree a value of V (preface traversal)
* Return returns the assigned node value
Status Assign(Tree *T，int e, TElementType v){
if(T == null){
return error;
}
e = T->Assign(T->leftChild);
e = T->Assign(T->rightChilg);
e = v;
return e;
}
*/
3. Basic Realization of Binary Tree Structure
/** * Basic Structure Realization * Declare a class, construct default array, array length, left and right child pointer, node value four attributes */ Class Tree { protected $tree; //Array structure protected $MaxSize; protected $leftChild; protected $rightChild; protected $temp; //Assignment Temporary Variable Container public function __construct($size){ $this->InitTree($size); } /** * TODO: Initialization Binary Tree * @param int $maxsize Array Max value */ public function InitTree($maxsize){ $this->MaxSize = $maxsize; $this->leftChild = 0; $this->rightChild = 0; $this->tree = ['A','B','#','D','#','#','C','#','#']; //Construct a binary tree, # stands for null values } /** * TODO: Query * @param int $node The ordinal number of a node in a tree * @param return $value Returns the value of a node in the tree */ public function Value($node){ if($this->tree == null || $this->tree[0] == '#'){ exit(); } // $i = 0; // $i++; // if($this->tree[i] != $node){ // $this->Value($node); // } return $this->tree[$node]; } /** * TODO: assignment * @param int $node The ordinal number of a node in a tree * @param int $value Preparatory variables for assignment * @param return $result Return the node in the tree to update the data value */ public function Assign($node,$v){ if($this->MaxSize>100 || $this->tree[$this->leftChild] == '#' || $this->tree[$this->rightChild] == '#'){ return ; } $this->temp = $this->tree[$node]; $this->tree[$node] = $v; return $this->tree[$node]; } } $tree = new Tree(20); echo "<pre/>"; print_r($tree); //Print the original class array echo "<br/>"."---------------"."<br>"; echo $tree->Value(1). "<br/>"; echo $tree->Value(2). "<br/>"; echo $tree->Assign(1,'A'). "<br/>";//Change the array element numbered 1 print_r($tree);//Print the updated class array
4. Binary Tree Sorting
5. Implementation of Binary Tree Application-Infinite Pole Classification (Reference-Recursion)
$items = array( 1 => array('id' => 1, 'pid' => 0, 'name' => 'Jiangxi Province'), 2 => array('id' => 2, 'pid' => 0, 'name' => 'Heilongjiang Province'), 3 => array('id' => 3, 'pid' => 1, 'name' => 'Nanchang City'), 4 => array('id' => 4, 'pid' => 2, 'name' => 'Harbin City'), 5 => array('id' => 5, 'pid' => 2, 'name' => 'Jixi City'), 6 => array('id' => 6, 'pid' => 4, 'name' => 'xiangfang district'), 7 => array('id' => 7, 'pid' => 4, 'name' => 'Nangang District'), 8 => array('id' => 8, 'pid' => 6, 'name' => 'Hexing Road'), 9 => array('id' => 9, 'pid' => 7, 'name' => 'West Dazhi Street'), 10 => array('id' => 10, 'pid' => 8, 'name' => 'Northeast Forestry University'), 11 => array('id' => 11, 'pid' => 9, 'name' => 'Harbin Institute of Technology'), 12 => array('id' => 12, 'pid' => 8, 'name' => 'harbin normal university'), 13 => array('id' => 13, 'pid' => 1, 'name' => 'Ganzhou City'), 14 => array('id' => 14, 'pid' => 13, 'name' => 'Ganxian'), 15 => array('id' => 15, 'pid' => 13, 'name' => 'Yudu County'), 16 => array('id' => 16, 'pid' => 14, 'name' => 'Maodian Town'), 17 => array('id' => 17, 'pid' => 14, 'name' => 'Datian Township'), 18 => array('id' => 18, 'pid' => 16, 'name' => 'Yiyuan Village'), 19 => array('id' => 19, 'pid' => 16, 'name' => 'Shangba Village'), ); /** *TODO:Implementing Infinite Pole Classification by Reference * */ function tree_Classify1($items){ $tree=array(); $packData=array(); foreach ($items as $data) { $packData[$data['id']] = $data; } foreach ($packData as $key =>$val){ if($val['pid']==0){//Representatives and nodes $tree[]=& $packData[$key]; }else{ //Find its parent class $packData[$val['pid']]['son'][]=& $packData[$key]; } } return $tree; } /** *TODO:Implementing Infinite Pole Classification by Recursive Method * */ function tree_Classify2($items,$child='_child',$root = 0){ $tree=array(); foreach($items as $key=> $val){ if($val['pid']==0){ //Get all subclasses of the current $pid unset($items[$key]); if(! empty($items)){ $child=make_tree1($items,$child,$val['id']); if(!empty($child)){ $val['_child']=$child; } } $tree[]=$val; } } return $tree; } echo "<pre>"; print_r(make_tree1($items,$child='_child',$root=0));