回来更新一波，最近刷了《剑指offer》，才发现树真的好大头，有二叉树的话题和变化很多~/***PHP二叉树算法*创建于2017-5-6*更新于2017-8-10*作者entner*Email1185087164@qq.com*/介绍很多人说那个二叉树没用，我觉得是他的工资，公司让他过不了这个坎；还有很多人学了一些关于树的知识，发现自己并不需要。我想说的是，读一本书并不能体现这本书的价值。表现出与他人的不同。二叉树定义严格，对称性好，数据相关性比较高，对数据存储和计算有很好的示范作用，比如完全二叉树：当然二叉树更适合链表存储，效率更高。总的来说，基于二叉树，我们可以衍生出很多神奇的应用。下面举几个常用的场景来论证我说的：编译表达式处理快速搜索排序文件压缩文件系统管理游戏场景划分，监控，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_NOTICE);$data=array(0=>'A',1=>'B',2=>'#',3=>'D',4=>'#',5=>'#',6=>'C',7=>'#',8=>'#',);类BTNode{public$data;公共$lChild；公共$rChild；公共函数__construct($data=null){$this->data=$data;}}类二叉树{public$root;公共$btData；公共函数__construct($data=null){$this->root=null;$this->btData=$data;//$this->preOrderCreateBT($this->root);}公共函数preOrderCreateBT(&$root=null){$elem=array_shift($this->btData);//去掉数组头部分，作为结果返回if($elem==null){#判断：数组为空时return;}elseif($elem=='#'){#判断：当数组为无效单元时，该节点为虚节点，退出本次递归，执行下一次递归$root='#';返回$根；}else{$root=newBTNode();$root->data=$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->数据；}else{返回；}返回$temp;}/***TODO:按顺序遍历二叉树（需要将书本中的节点放入队列中）**/functionPrintFromTopToBottom(&$root){//在这里写代码if($root==null){返回;}$队列=数组（）；array_push($queue,$root);while(!is_null($node=array_shift($queue))){echo$node->data.'';if($node->left!=null){array_push($queue,$node->lChild);}if($node->left!=null){一个rray_push($queue,$node->rChild);}}}}$object=newBinaryTree($data);$tree=$object->preOrderCreateBT($root);echo"
";print_r($tree);die;4.二叉排序树/***FindBitTree二叉树搜索*@paramTBItTree指的是二叉树及其元素节点*@paramkeyint树中的一个节点*@paramfpoint指向该节点的父节点*@paramppoint指向元素节点ornull*@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二叉树插入*【如果没有key元素，插入的节点必须是叶子节点】*@paramTBItTree指的是二叉树及其元素节点*@paramkeyintanode在树中*@paramreturnbooltrue|falsestatusInsertBST(BitTreeT,intkey){if(SearchBST(T,key,NULL,&p)==false){s->data=key;s->lChild=s->rChild=NULL;如果(!p){T=s;}elseif(keydata){p->lChild=s;}else{p->rChild=s;}返回真；}返回假；}*/五、树的应用实现——无限分类（参考&递归）$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=>array('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'=>'上坝村');/***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]);如果(!empty($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));``