SPL(Standard PHP Library歪脏，PHP標準庫)中并無樹和圖數(shù)據(jù)結構的實現(xiàn)疑俭，考慮到實用性，同時呼應《算法導論》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;//二叉樹中結點個數(shù)
? ?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到正確的使用方式，這里就直接截圖了舟误。
//創(chuàng)建二叉樹 以先序遍歷次序:如果某節(jié)點為空葡秒，標記為NULL
//分支數(shù)無限制的有根樹
分支數(shù)無限制的有根樹可采用“左孩子，右兄弟”的二叉鏈表表示方法：即left_child指向節(jié)點x最左的孩子嵌溢；right_child指向節(jié)點x緊右邊的兄弟眯牧。事實上，這種將普通樹采用二叉鏈表的存儲方式赖草，即是將普通樹轉換為二叉樹的方法：
①樹中所有相同雙親結點的兄弟節(jié)點之間加一條連線
②對樹中不是雙親結點第一個孩子的結點学少，只保留新添加的該結點與左兄弟結點之間的連線，刪去該結點與雙親結點之間的連線
③整理所有保留和添加的的連線秧骑，使每個結點的第一個孩子結點連線位于左孩子指針位置版确，使每個結點的右兄弟結點連線位于右孩子指針位置。?
普通樹的遍歷方式有兩種：深度優(yōu)先（對樹而言又可再細分為先根優(yōu)先和后根優(yōu)先）和廣度優(yōu)先遍歷乎折。
深度優(yōu)先遍歷從某個頂點出發(fā)绒疗，首先訪問這個頂點，然后找出剛 訪問這個結點的第一個未被訪問的鄰結點骂澄，然后再以此鄰結點為頂點吓蘑，繼續(xù)找它的下一個新
的頂點進行訪問，重復此步驟坟冲，直到所有結點都被訪問完為止磨镶。
廣度優(yōu)先遍歷從某個頂點出發(fā)溃蔫，首先訪問這個頂點，然后找出這個結點的所有未被訪問的鄰接點棋嘲，訪問完后再訪問這些結點中第一個鄰接點的所有結點酒唉，重復此方法，直到所有結點都被訪問完為止沸移。
tips：樹的廣度優(yōu)先遍歷其實就是層次遍歷痪伦，而樹的深度先根遍歷就是其對應二叉樹的先根遍歷；樹的深度后根遍歷就是其對應二叉樹的中根遍歷雹锣。
