SPL(Standard PHP Library，PHP標(biāo)準(zhǔn)庫)中并無樹和圖數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)，考慮到實用性，同時呼應(yīng)《算法導(dǎo)論》10.4節(jié)，我們此處將有根樹（二叉樹及分支數(shù)無限制的有根樹）以鏈狀方式存儲，并給出常用的增刪改查操作實現(xiàn)。
//BiNode
/**
* tree node
*/
class BiNode
{?public $data;
? public $lchild;
? public $rchild;
? function __construct($data)
? { ?$this->data=$data;
? ? ?$this->lchild=null;
? ? ?$this->rchild=null;
? ?}
}
//php 二叉樹的創(chuàng)建 先根/中根/后跟遞歸遍歷 ?層次遍歷 二叉樹的高度
<?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;//二叉樹中結(jié)點(diǎn)個數(shù)
? ?function __construct()
? ?{
? ? ? ?$this->root=null;//指向根結(jié)點(diǎn)，初始化為空
? ? ? ?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到正確的使用方式，這里就直接截圖了。
//創(chuàng)建二叉樹 以先序遍歷次序:如果某節(jié)點(diǎn)為空，標(biāo)記為NULL
//分支數(shù)無限制的有根樹
分支數(shù)無限制的有根樹可采用“左孩子，右兄弟”的二叉鏈表表示方法：即left_child指向節(jié)點(diǎn)x最左的孩子；right_child指向節(jié)點(diǎn)x緊右邊的兄弟。事實上，這種將普通樹采用二叉鏈表的存儲方式，即是將普通樹轉(zhuǎn)換為二叉樹的方法：
①樹中所有相同雙親結(jié)點(diǎn)的兄弟節(jié)點(diǎn)之間加一條連線
②對樹中不是雙親結(jié)點(diǎn)第一個孩子的結(jié)點(diǎn)，只保留新添加的該結(jié)點(diǎn)與左兄弟結(jié)點(diǎn)之間的連線，刪去該結(jié)點(diǎn)與雙親結(jié)點(diǎn)之間的連線
③整理所有保留和添加的的連線，使每個結(jié)點(diǎn)的第一個孩子結(jié)點(diǎn)連線位于左孩子指針位置，使每個結(jié)點(diǎn)的右兄弟結(jié)點(diǎn)連線位于右孩子指針位置。?
普通樹的遍歷方式有兩種：深度優(yōu)先（對樹而言又可再細(xì)分為先根優(yōu)先和后根優(yōu)先）和廣度優(yōu)先遍歷。
深度優(yōu)先遍歷從某個頂點(diǎn)出發(fā)，首先訪問這個頂點(diǎn)，然后找出剛 訪問這個結(jié)點(diǎn)的第一個未被訪問的鄰結(jié)點(diǎn)，然后再以此鄰結(jié)點(diǎn)為頂點(diǎn)，繼續(xù)找它的下一個新
的頂點(diǎn)進(jìn)行訪問，重復(fù)此步驟，直到所有結(jié)點(diǎn)都被訪問完為止。
廣度優(yōu)先遍歷從某個頂點(diǎn)出發(fā)，首先訪問這個頂點(diǎn)，然后找出這個結(jié)點(diǎn)的所有未被訪問的鄰接點(diǎn)，訪問完后再訪問這些結(jié)點(diǎn)中第一個鄰接點(diǎn)的所有結(jié)點(diǎn)，重復(fù)此方法，直到所有結(jié)點(diǎn)都被訪問完為止。
tips：樹的廣度優(yōu)先遍歷其實就是層次遍歷，而樹的深度先根遍歷就是其對應(yīng)二叉樹的先根遍歷；樹的深度后根遍歷就是其對應(yīng)二叉樹的中根遍歷。
