原理：左節(jié)點(diǎn) < 根節(jié)點(diǎn) < 右節(jié)點(diǎn),中序遍歷是一個(gè)升序數(shù)組，二叉搜索樹利于查找，其查找原理是二分查找
代碼：
class BTree{
? ? public $root;
? ? public function __construct($val=null){
? ? ? ? $this->root = new \App\Server\xc\BNode($val);
? ? }
? ? //添加元素
? ? public function add($val){
? ? ? ? $root = $this->root;
? ? ? ? while($root){
? ? ? ? ? ? if($root->val > $val){
? ? ? ? ? ? ? ? if(!$root->left){
? ? ? ? ? ? ? ? ? ? $root->left = new \App\Server\xc\BNode($val);
? ? ? ? ? ? ? ? ? ? return ;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? $root = $root->left;
? ? ? ? ? ? ? ? continue;
? ? ? ? ? ? }
? ? ? ? ? ? if($root->val < $val){
? ? ? ? ? ? ? ? if(!$root->right){
? ? ? ? ? ? ? ? ? ? $root->right = new \App\Server\xc\BNode($val);
? ? ? ? ? ? ? ? ? ? return ;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? $root = $root->right;
? ? ? ? ? ? ? ? continue;
? ? ? ? ? ? }
? ? ? ? ? ? return ;
? ? ? ? }
? ? }
? ? //刪除元素
? ? public function delete($val){
? ? ? ? $root = $this->root;
? ? ? ? $prv = null;
? ? ? ? while($root){
? ? ? ? ? ? if($root->val > $val){
? ? ? ? ? ? ? ? $prv = $root;
? ? ? ? ? ? ? ? $root = $root->left;
? ? ? ? ? ? ? ? continue;
? ? ? ? ? ? }
? ? ? ? ? ? if($root->val < $val){
? ? ? ? ? ? ? ? $prv = $root;
? ? ? ? ? ? ? ? $root = $root->right;
? ? ? ? ? ? ? ? continue;
? ? ? ? ? ? }
? ? ? ? ? ? if(!$root->left){
? ? ? ? ? ? ? ? if($prv->val > $root->right->val){
? ? ? ? ? ? ? ? ? ? $prv->left = $root->right;
? ? ? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? ? ? $prv->right = $root->right;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? return;
? ? ? ? ? ? }
? ? ? ? ? ? if(!$root->right){
? ? ? ? ? ? ? ? if($prv->val > $root->left->val){
? ? ? ? ? ? ? ? ? ? $prv->left = $root->left;
? ? ? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? ? ? $prv->right = $root->left;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? return;
? ? ? ? ? ? }
? ? ? ? ? ? $right = $root->right;
? ? ? ? ? ? $left = $root->left;
? ? ? ? ? ? if($prv->val > $root->val){
? ? ? ? ? ? ? ? $prv->left = $left;
? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? $prv->right = $left;
? ? ? ? ? ? }
? ? ? ? ? ? while($left->right){
? ? ? ? ? ? ? ? $left = $left->right;
? ? ? ? ? ? }
? ? ? ? ? ? $left->right = $right;
? ? ? ? ? ? return;
? ? ? ? }
? ? }
? ? //查找元素
? ? public function select($root,$val){
? ? ? ? if(!$root){
? ? ? ? ? ? return false;
? ? ? ? }
? ? ? ? if($root->val == $val){
? ? ? ? ? ? return true;
? ? ? ? }
? ? ? ? if($val < $root->val){
? ? ? ? ? if($this->select($root->left,$val)){
? ? ? ? ? ? ? return true;
? ? ? ? ? }
? ? ? ? }else{
? ? ? ? ? ? if($this->select($root->right,$val)){
? ? ? ? ? ? ? ? return true;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return false;
? ? }
? ? //將二叉搜索樹轉(zhuǎn)化成升序列表(中序遍歷)
? ? public function topList($root,&$list=[]){
? ? ? ? if(!$root){
? ? ? ? ? ? return $list;
? ? ? ? }
? ? ? ? $this->topList($root->left,$list);
? ? ? ? $list[] = $root->val;
? ? ? ? $this->topList($root->right,$list);
? ? ? ? return $list;
? ? }
? ? //前序遍歷
? ? public function beforeList($root,&$list=[]){
? ? ? ? if(!$root){
? ? ? ? ? ? return $list;
? ? ? ? }
? ? ? ? $list[] = $root->val;
? ? ? ? $this->beforeList($root->left,$list);
? ? ? ? $this->beforeList($root->right,$list);
? ? ? return $list;
? ? }
? ? //后序遍歷
? ? public function afterList($root,&$list=[]){
? ? ? ? if(!$root){
? ? ? ? ? ? return $list;
? ? ? ? }
? ? ? ? $this->afterList($root->left,$list);
? ? ? ? $this->afterList($root->right,$list);
? ? ? ? $list[] = $root->val;
? ? ? ? return $list;
? ? }
? ? //將二叉搜索樹轉(zhuǎn)化成降序列表
? ? public function downList($root,&$list=[]){
? ? ? ? if(!$root){
? ? ? ? ? ? return $list;
? ? ? ? }
? ? ? ? $this->downList($root->right,$list);
? ? ? ? $list[] = $root->val;
? ? ? ? $this->downList($root->left,$list);
? ? ? ? return $list;
? ? }
? ? //前序遍歷(迭代)
? ? public function beforeListByIteration($root){
? ? ? ? if(!$root) return [];
? ? ? ? $stack = [];
? ? ? ? $list = [];
? ? ? ? $stack[] = $root;
? ? ? ? while (!empty($stack)){
? ? ? ? ? $root = array_pop($stack);
? ? ? ? ? $list[] = $root->val;
? ? ? ? ? if($root->right){
? ? ? ? ? ? ? array_push($stack,$root->right);
? ? ? ? ? }
? ? ? ? ? if($root->left){
? ? ? ? ? ? ? array_push($stack,$root->left);
? ? ? ? ? }
? ? ? ? }
? ? ? ? return $list;
? ? }
? ? //前序遍歷(迭代)
? ? public function beforeListByIteration2($root){
? ? ? ? if(!$root) return [];
? ? ? ? $list = [];
? ? ? ? $stack = [];
? ? ? ? while ($root || !empty($stack)){
? ? ? ? ? ? while($root){
? ? ? ? ? ? ? ? $list[] = $root->val;
? ? ? ? ? ? ? ? array_push($stack,$root);
? ? ? ? ? ? ? ? $root = $root->left;
? ? ? ? ? ? }
? ? ? ? ? ? if(!empty($stack)){
? ? ? ? ? ? ? ? $root = array_pop($stack);
? ? ? ? ? ? ? ? $root = $root->right;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return $list;
? ? }
? ? //中序遍歷(迭代)
? ? public function sequenceListByIteration($root){
? ? ? ? if(!$root) return [];
? ? ? ? $list = [];
? ? ? ? $stack = [];
? ? ? ? while ($root || !empty($stack)){
? ? ? ? ? ? while($root){
? ? ? ? ? ? ? ? array_push($stack,$root);
? ? ? ? ? ? ? ? $root = $root->left;
? ? ? ? ? ? }
? ? ? ? ? ? if(!empty($stack)){
? ? ? ? ? ? ? ? $root = array_pop($stack);
? ? ? ? ? ? ? ? $list[] = $root->val;
? ? ? ? ? ? ? ? $root = $root->right;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return $list;
? ? }
? ? //后序遍歷(迭代) 當(dāng)左右節(jié)點(diǎn)為空或者左右節(jié)點(diǎn)都已經(jīng)訪問(wèn)的情況下才訪問(wèn)當(dāng)前節(jié)點(diǎn)，否則將左右節(jié)點(diǎn)壓入棧
? ? public function afterListByIteration($root){
? ? ? ? if(!$root) return [];
? ? ? ? $list = [];
? ? ? ? $stack = [];
? ? ? ? $pre = '';
? ? ? ? array_push($stack,$root);
? ? ? ? while($stack){
? ? ? ? ? ? //先獲取棧頂元素判斷是否左右節(jié)點(diǎn)是否被訪問(wèn)或?yàn)榭?/p>
? ? ? ? ? ? $cur = $stack[count($stack)-1];
? ? ? ? ? ? //當(dāng)前一個(gè)訪問(wèn)的是當(dāng)前節(jié)點(diǎn)的左|右節(jié)點(diǎn)，說(shuō)明當(dāng)前節(jié)點(diǎn)的左右節(jié)點(diǎn)已訪問(wèn)，則訪問(wèn)當(dāng)前節(jié)點(diǎn)
? ? ? ? ? ? if((!$cur->left && !$cur->right) || ($pre && ($pre==$cur->left || $pre == $cur->right))){
? ? ? ? ? ? ? ? $list[] = $cur->val;
? ? ? ? ? ? ? ? $pre = $cur;
? ? ? ? ? ? ? ? array_pop($stack);
? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? //先插入右節(jié)點(diǎn)在插入左節(jié)點(diǎn)，棧的特性
? ? ? ? ? ? ? ? array_push($stack,$cur->right);
? ? ? ? ? ? ? ? array_push($stack,$cur->left);
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return $list;
? ? }
}
