回来更新一波，最近刷了《剑指offer》，才发现树真的好大头，有二叉树的很多话题和变化~/***PHP二叉树算法*创建于2017-5-6*更新于2017-8-10*作者entner*Email1185087164@qq.com*/Introduction很多人说二叉树没用，我觉得是他的工资和公司让他过不了这个坎；还有很多人学了一些关于树的知识，发现自己并不需要。我想说的是，读一本书并不能体现这本书的价值。表现出与他人的不同。二叉树定义严格，对称性好，数据相关性比较高，对数据存储和计算有很好的示范作用，比如完全二叉树：当然二叉树更适合链表存储，效率更高。总的来说，基于二叉树，我们可以衍生出很多神奇的应用。下面举几个常用的场景来论证我说的：编译表达式处理快速搜索排序文件压缩文件系统管理游戏场景划分，监控，Rendering我承认上面很多东西你不会直接接触，但是关键就是学习一种思维和设计，退一步就能有一点感悟：）1.二叉树抽象数据类型操作书上关于操作的条目太多了，我只列举一些常用的那些（这些都是经常考的知识点），有兴趣的相信自己也有找到“好产品”的本领——InitTree构造一棵空树——PreTra返回树中某个节点的值——InTra给树中的节点赋值-LevelTra返回非根节点的父节点，否则返回空-LeftChild返回非叶节点的最左子节点，否则返回空锻炼你的抽象逻辑思维。不懂就多看几遍，再查相关资料。应该问题不大。你甚至可以找一张纸，默默地写下来。/***InitTree初始化树**TypedefintTElementType//构造一个数据类型TypedefStructTree{//构造一个二叉树抽象数据类型TElementTypedata;//声明一个数组，先构造一棵树StructTree*leftChild;//左子节点StructTree*rightChild;//右子节点}Tree;*／/***Value获取树的节点（前序遍历）*Return返回获取的节点值StatusValue(Tree*T,inte){if(T==null){返回错误；}e=T->Value(T->leftChild);e=T->Value(T->rightChild);返回e;}*//***AssignAssignv到树中的一个节点（前序遍历）*return返回分配的节点值StatusAssign(Tree*T,inte,TElementTypev){if(T==null){return错误;}e=T->Assign(T->leftChild);e=T->Assign(T->rightChild);e=v;返回e;}*/3。二叉树结构的基本实现/***PHP二叉树算法*创建于2017-8-7*作者entner*Email1185087164@qq.com*//*假设我构造一棵二叉树ABC#D####*/error_reporting(E_ALL^E_WARNING);ClassBinaryTree{public$lChild;公共$rChild；公共价值；/*初始化并构造一棵空树*/publicfunction__construct($data=null){$this->value=$data;}/***TODO:构建二叉树*@param$rootobject二叉树*/publicfunctionpreOrderCreateBT(&$root){while(!is_null($elem=array_shift($this->value))){$root='';if($elem==null){#判断：当数组为空时return$root;}elseif($elem=='#'){#判断：当数组为无效单元时，节点为虚节点（无子节点），退出当前递归，执行下一次递归$root->值='#';返回;}else{$root->value=$elem;$this->preOrderCreateBT($root->lChild);$this->preOrderCreateBT($root->rChild);}}返回$root;}/***TODO:按预序遍历二叉树*@param$treeobject二叉树*@param$temparray二叉树输出节点存储数组*/publicfunctionprintBTPreOrder($tree,&$temp){if($tree!=null){$temp[]=$tree->data;$this->printBTPreOrder($tree->lChild,$temp);$this->printBTPreOrder($tree->rChild,$temp);}else{返回;}返回$temp;}/***TODO:按顺序遍历二叉树*@param$treeobject二叉树*@param$temparray二叉树输出节点存储数组*/publicfunctionprintBTInOrder($tree,&$temp){if($tree!=null){$this->printBTInOrder($tree->lChild,$temp);$temp[]=$tree->data;$this->printBTInOrder($tree->rChild,$temp);}else{返回；}返回$temp;}/***TODO:后序遍历二叉树*@param$treeobject二叉树*@param$temparray二叉树输出节点存储数组*/publicfunctionprintBPTosOrder($tree,&$temp){if($tree!=null){$this->printBTPosOrder($tree->lChild,$temp);$this->printBTPosOrder($tree->rChild,$temp);$temp[]=$tree->data;}else{返回；}返回$temp;}/***TODO:分层遍历二叉树（需要将书中的节点放入队列中）**/functionPrintFromTopToBottom(&$root){//在这里写代码$queueVal=array();$队列=数组();如果（$root==null）{返回$queueVal；#注意当二叉树为空时，应该返回一个空数组}array_push($queue,$root);while($queue){$node=array_shift($queue);array_push($queueVal,$node->value);如果($node->lChild!=null){array_push($queue,$node->lChild);}if($node->rChild!=null){array_push($queue,$node->rChild);}}return$queueVal;}/***TODO:树的深度**/publicfunctiontreeDeepth(&$root){if($root==null){return0;}如果($root!=null){$ld=$this->treeDeepth($root->lChild)+1;$rd=$this->treeDeepth($root->rChild)+1;}$max=最大值($ld,$rd);返回$最大值；}}$node=array(0=>'A',1=>'B',2=>'#',3=>'D',4=>'#',5=>'#',6=>'C',7=>'#',8=>'#',);$object=newBinaryTree($node);$tree=$object->preOrderCreateBT();echo"
";print_r($tree);echo$object->treeDeepth($tree)。"
";print_r($object->PrintFromTopToBottom($tree));下面是效果图：构造树的结构，树的深度，层次遍历的输出！[图片说明][3]4.二叉排序树/***FindBitTree二叉树搜索*@paramTBItTree指的是二叉树及其元素Node*@paramkeyint树中的一个节点*@paramfpointpoints到节点的父节点*@paramp指向元素节点或为空*@paramreturnbooltrue|falsestatusSearchBST(BitTreeT,intkey,BitTreef=null,BitTreep){if(!T){p=f;返回假；}if(key==T->data){p=T;//其实就是根节点returntrue;}elseif(keydata){SearchBST(T->lChild,intkey,T,p);}elseif(key>T->data){SearchBST(T->rChild,intkey,T,p);}*//**InsertBitTree二叉树插入*【如果当前树中没有关键元素，则Insert，插入的节点必须是叶节点】*@paramTBItTree指的是二叉树及其元素节点*@paramkeyint树中的一个节点*@paramreturnbooltrue|falsestatusInsertBST(BitTreeT,intkey){if(SearchBST(T,key,NULL,&p)==false){s->data=钥匙;s->lChild=s->rChild=NULL;如果(!p){T=s;}elseif(key data){p->lChild=s;}else{p->rChild=s;}返回真；}返回假；&recursion)$items=array(1=>array('id'=>1,'pid'=>0,'name'=>'江西省'),2=>array('id'=>2,'pid'=>0,'name'=>'黑龙江'),3=>array('id'=>3,'pid'=>1,'name'=>'南昌'),4=>array('id'=>4,'pid'=>2,'name'=>'哈尔滨'),5=>array('id'=>5,'pid'=>2,'name'=>'鸡西'),6=>array('id'=>6,'pid'=>4,'name'=>'香坊区'),7=>array('id'=>7,'pid'=>4,'name'=>'南港区'),8=>array('id'=>8,'pid'=>6,'name'=>'和兴路'),9=>array('id'=>9,'pid'=>7,'name'=>'西大直街'),10=>array('id'=>10,'pid'=>8,'name'=>'东北林业大学'),11=>array('id'=>11,'pid'=>9,'name'=>'哈尔滨工业大学'),12=>array('id'=>12,'pid'=>8,'name'=>'哈尔滨师范大学'),13=>array('id'=>13,'pid'=>1,'name'=>'赣州市'),14=>array('id'=>14,'pid'=>13,'name'=>'甘县'),15=>array('id'=>15,'pid'=>13,'name'=>'于都县'),16=>数组('id'=>16,'pid'=>14,'name'=>'茅店镇'),17=>array('id'=>17,'pid'=>14,'name'=>'大田乡'),18=>array('id'=>18,'pid'=>16,'name'=>'宜园村'),19=>array('id'=>19,'pid'=>16,'name'=>'上坝Village');/***TODO:通过引用实现无限分类**/functiontree_Classify1($items){$tree=array();$packData=array();foreach($itemsas$data){$packData[$data['id']]=$data;}foreach($packDataas$key=>$val){if($val['pid']==0){//表示根节点$tree[]=&$packData[$key];}else{//找到它的父类$packData[$val['pid']]['son'][]=&$packData[$key];}}return$tree;}/***TODO:通过递归实现无限分类**/functiontree_Classify2($items,$child='_child',$root=0){$tree=array();foreach($itemsas$key=>$val){if($val['pid']==0){//获取当前$pid的所有子类unset($items[$key]);如果（！空（$items））{$child=make_tree1($items,$child,$val['id']);如果(!empty($child)){$val['_child']=$child;}}$tree[]=$val;}}return$tree;}echo" ";print_r(make_tree1($items,$child='_child',$root=0));``[1]:/img/bV7ljv[2]:/img/bV7ljz