回来更新一波，最近刷《剑指offer》，才又发现树真是一个大头，二叉树的题目和变化运用好多啊～
/*** PHP二叉树算法* Created on 2017-5-6* Update on 2017-8-10* Author entner* Email 1185087164@qq.com*/
引子
很多人说二叉树没什么卵用，我觉得是他的工资和公司让他跨不过这个坎；还有很多人学了一些树的知识，发现也用不上，我想说的是，读一本书体现不了这本书的价值，要多读几本才会把你和别人的差别体现出来。
二叉树是严格定义的，有很好的对称性和比较高的数据关联度，对数据的存储和计算，有很好的演示作用，比如完全二叉树：当然，二叉树更适合链表存储，效率更高，总的来说，以二叉树为基础我们可以衍生出许多神奇的运用，举几个常用的场景为我说的话正言：
- 编译器表达式处理
- 快速查找与排序
- 文件压缩
- 文件系统管理
-
游戏场景划分、监测、渲染
我承认，上面好多东西你并不会直接接触，但是，我们关键是去学习一种思维和设计，退一万步也可以增加一点见识：）
一、二叉树抽象数据类型操作条目
关于书的操作太多了，我只列一些常用的(这些都是常考的知识点)，有兴趣的相信也有技能去淘到“好货” -InitTree 构造空树 -PreTra 返回树中某结点的值 -InTra 给树中某结点赋值为value -LevelTra 返回某非根结点的双亲，否则返回空 -LeftChild 返回某非叶结点的最左孩子，否则返回空
二、默写二叉树常用数据结构
默写会让你记忆更深刻，同时也会锻炼抽象的逻辑思维，一边看不懂，就多看几遍，再查一查相关资料，应该问题不大，你甚至可以找张纸默写一下。
/** *InitTree 初始化树* * Typedef int TElementType //构造一个数据类型 Typedef Struct Tree{ //构造二叉树抽象数据类型 TElementType data; //声明一个数组，先构建一个树 Struct Tree *leftChild; //左孩子节点 Struct Tree *rightChild; //右孩子节点 }Tree;*／/** * Value 获取树的结点(前序遍历) * Return 返回获取的结点值 Status Value（Tree *T，int e）{ if(T == null){ return error; } e = T->Value(T->leftChild); e = T->Value(T->rightChild); return e; } *//** * Assign 给树中某结点赋值为v(前序遍历) * Return 返回赋值后的结点值 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; } */ 三、二叉树结构基本实现
/*** PHP二叉树算法* Created on 2017-8-7* Author entner* Email 1185087164@qq.com*//* 假设我构造一颗如下的二叉树 A B C # D # # # #*/error_reporting(E_ALL ^ E_WARNING);Class BinaryTree{ public $lChild; public $rChild; public $value; /* 初始化构造空树 */ public function __construct($data = null){ $this->value = $data; } /** * TODO:构建二叉树 * @param $root object 二叉树 */ public function preOrderCreateBT(&$root){ while(!is_null($elem = array_shift($this->value))){ $root = ''; if($elem == null){ #判断：当数组为空时 return $root; }else if($elem == '#'){ #判断：当数组为无效单元时，该节点是虚节点(无孩子节点)，退出当前递归，执行下一个递归 $root->value = '#'; return ; }else{ $root->value = $elem; $this->preOrderCreateBT($root->lChild); $this->preOrderCreateBT($root->rChild); } } return $root; } /** * TODO:先序遍历二叉树 * @param $tree object 二叉树 * @param $temp array 二叉树输出节点存储数组 */ public function printBTPreOrder($tree,&$temp){ if($tree != null){ $temp[] = $tree->data; $this->printBTPreOrder($tree->lChild,$temp); $this->printBTPreOrder($tree->rChild,$temp); }else{ return ; } return $temp; } /** * TODO:中序遍历二叉树 * @param $tree object 二叉树 * @param $temp array 二叉树输出节点存储数组 */ public function printBTInOrder($tree,&$temp){ if($tree != null){ $this->printBTInOrder($tree->lChild,$temp); $temp[] = $tree->data; $this->printBTInOrder($tree->rChild,$temp); }else{ return; } return $temp; } /** * TODO:后序遍历二叉树 * @param $tree object 二叉树 * @param $temp array 二叉树输出节点存储数组 */ public function printBTPosOrder($tree,&$temp){ if($tree != null){ $this->printBTPosOrder($tree->lChild,$temp); $this->printBTPosOrder($tree->rChild,$temp); $temp[] = $tree->data; }else{ return; } return $temp; } /** * TODO:层序遍历二叉树（需要将书中节点放入队中） * */ function PrintFromTopToBottom(&$root){ // write code here $queueVal = array(); $queue = array(); if($root == null){ return $queueVal; #注意当二叉树为空树时，应该返回空数组 } array_push($queue,$root); while($queue){ $node = array_shift($queue); array_push($queueVal,$node->value); if($node->lChild != null){ array_push($queue,$node->lChild); } if($node->rChild != null){ array_push($queue,$node->rChild); } } return $queueVal;} /** * TODO:树的深度 * */ public function treeDeepth(&$root){ if($root == null){ return 0; } if($root != null){ $ld = $this->treeDeepth($root->lChild) + 1; $rd = $this->treeDeepth($root->rChild) + 1; } $max = max($ld,$rd); return $max; }}$node = array( 0=>'A', 1=>'B', 2=>'#', 3=>'D', 4=>'#', 5=>'#', 6=>'C', 7=>'#', 8=>'#', );$object = new BinaryTree($node);$tree = $object->preOrderCreateBT();echo "";print_r($tree);echo $object->treeDeepth($tree) . "";print_r($object->PrintFromTopToBottom($tree));以下为效果图：分别是构造树的结构、树的深度、层序遍历输出![图片描述][3]
四、二叉排序树
/***FindBitTree 二叉树查找*@param T BItTree 代指二叉树及其元素结点*@param key int 树中某结点*@param f point 指向该结点父结点*@param p point 指向该元素结点或空*@param return bool true|false status SearchBST(BitTree T,int key,BitTree f = null,BitTree p){ if(!T){ p = f; return false; } if(key == T->data){ p = T；//其实就是根结点 return true； }else if(key data){ SearchBST(T->lChild,int key,T,p); }else if(key >T->data){ SearchBST(T->rChild,int key,T,p); } }*//**InsertBitTree 二叉树插入 *【如果当前树中没有key元素，则插入，插入的结点一定是叶子结点】*@param T BItTree 代指二叉树及其元素结点*@param key int 树中某结点*@param return bool true|false status InsertBST(BitTree T，int key){ if(SearchBST(T,key,NULL,&p) == false){ s->data = key; s->lChild = s->rChild = NULL; if(!p){ T= s; }else if(key < p->data){ p->lChild = s; }else{ p->rChild = s; } return true; } return false; }*/ 五、树应用实现-无限极分类（引用&递归）
$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:通过引用方式实现无限极分类* */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){//代表跟节点 $tree[]=& $packData[$key]; }else{ //找到其父类 $packData[$val['pid']]['son'][]=& $packData[$key]; } } return $tree;}/***TODO:通过递归方式实现无限极分类* */function tree_Classify2($items,$child='_child',$root = 0){ $tree=array(); foreach($items as $key=> $val){ if($val['pid']==0){ //获取当前$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 "";print_r(make_tree1($items,$child='_child',$root=0));`` [1]: /img/bV7ljv [2]: /img/bV7ljz