SPL(Standard PHP Library，PHP标准库)中并无树和图数据结构的实现，考虑到实用性，同时呼应《算法导论》10.4节，我们此处将有根树（二叉树及分支数无限制的有根树）以链状方式存储，并给出常用的增删改查操作实现。
//BiNode
/**
* tree node
*/
class BiNode
{ public $data;
public $lchild;
public $rchild;
function __construct($data)
{ $this->data=$data;
$this->lchild=null;
$this->rchild=null;
}
}
//php 二叉树的创建 先根/中根/后跟递归遍历 层次遍历 二叉树的高度
<?php
require_once(__DIR__."/BiNode.php");
/**
* (binary) tree realization using php
* store it in the form of linkedList
*/
class BinaryTree
{
private $root;
private static $count;//二叉树中结点个数
function __construct()
{
$this->root=null;//指向根结点，初始化为空
self::$count=0;
}
//清空二叉树
public function clearBiTree(){
$this->clearTree($this->root);
self::$count=0;
}
private function clearTree($root){
if ($root) {
if ($root->lchild) {
$this->clearTree($root->lchild);
}
if ($root->rchild) {
$this->clearTree($root->rchild);
}
unset($root);
}
}
//ps: 简书的代码格式太混乱了，可能是我没get到正确的使用方式，这里就直接截图了。
//创建二叉树 以先序遍历次序:如果某节点为空，标记为NULL
//分支数无限制的有根树
分支数无限制的有根树可采用“左孩子，右兄弟”的二叉链表表示方法：即left_child指向节点x最左的孩子；right_child指向节点x紧右边的兄弟。事实上，这种将普通树采用二叉链表的存储方式，即是将普通树转换为二叉树的方法：
①树中所有相同双亲结点的兄弟节点之间加一条连线
②对树中不是双亲结点第一个孩子的结点，只保留新添加的该结点与左兄弟结点之间的连线，删去该结点与双亲结点之间的连线
③整理所有保留和添加的的连线，使每个结点的第一个孩子结点连线位于左孩子指针位置，使每个结点的右兄弟结点连线位于右孩子指针位置。
普通树的遍历方式有两种：深度优先（对树而言又可再细分为先根优先和后根优先）和广度优先遍历。
深度优先遍历从某个顶点出发，首先访问这个顶点，然后找出刚 访问这个结点的第一个未被访问的邻结点，然后再以此邻结点为顶点，继续找它的下一个新
的顶点进行访问，重复此步骤，直到所有结点都被访问完为止。
广度优先遍历从某个顶点出发，首先访问这个顶点，然后找出这个结点的所有未被访问的邻接点，访问完后再访问这些结点中第一个邻接点的所有结点，重复此方法，直到所有结点都被访问完为止。
tips：树的广度优先遍历其实就是层次遍历，而树的深度先根遍历就是其对应二叉树的先根遍历；树的深度后根遍历就是其对应二叉树的中根遍历。
网友评论