/**

*?ClearBiTree()?清空二叉樹

*?CreateBiTree()?創建二叉樹

*?BiTreeEmpty()?判斷二叉樹是否為空

*?BiTreeDepth()?返回二叉樹的深度

*?root()?返回二叉樹的根

*?Parent()?返回給定元素的雙親

*?LeftChild()?要返回左孩子的元素

*?RightChild()?要返回右孩子的元素

*?LeftSibling()?要返回左兄弟的元素

*?RightSibling()?要返回右兄弟的元素

*?Insert($data)?插入節點——遞歸算法

*?insert2($data)?插入節點——非遞歸算法

*?DeleteSubtree($elem,$LR)?刪除某個節點的左(右)子樹

*?PreOrderTraverse()?先序遍歷——遞歸算法

*?InOrderTraverse()?中序遍歷——遞歸算法

*?PostOrderTraverse()?后序遍歷——非遞歸算法

*?preOrderTraverse2()?先序遍歷——非遞歸算法

*?preOrderTraverse3()?先序遍歷——非遞歸算法

*?inOrderTraverse2()?中序遍歷——非遞歸算法

*?inOrderTraverse3()?中序遍歷——非遞歸算法

*?postOrderTraverse2()?后序遍歷——非遞歸算法

*/

class?BiNode{

public?$data;

public?$lchild;

public?$rchild;

public?function?__construct($data){

$this->data=$data;?//節點數據

$this->lchild=null;//左孩子的指針

$this->rchild=null;//右孩子的指針

}

}

class?LinkBiTree{

private??$root;?//二叉樹的根節點

private?static?$preArr;?//用于保存先序遍歷后的數據

private?static?$inArr;?//用于保存中序遍歷后的數據

private?static?$postArr;?//用于保存后序遍歷后的數據

private?static?$levelArr;?//用于保存后序遍歷后的數據

private?static?$count;?//記錄創建二叉樹結點的個數

const?MAX_LEVEL=2;//二叉樹最大的層數

public?static??$test;

public?function?__construct(){

$this->root=null;//指向根節點,初始化時為空樹

self::$count=0;

}

/**

*?清空二叉樹

*/

public?function?ClearBiTree(){

$this->clearTree($this->root);

}

/**

*?@param?$root?表示樹的根節點

*/

private?function?clearTree($root){

if($root){

if($root->lchild){

$this->clearTree($root->lchild);?//清空左子樹

}

if($root->rchild){

$this->clearTree($root->rchild);?//清空右子樹

}

unset($root);?//釋放根節點

$root=null;

}

}

//先序遍歷

public?function?PreOrderTraverse(){

$this->preTraverse($this->root);

return?self::$preArr;

}

private?function?preTraverse($root){

if($root){

self::$preArr[]=$root->data;?//先訪問根節點

$this->preTraverse($root->lchild);//再先序遍歷左子樹

$this->preTraverse($root->rchild);//最后先序遍歷右子樹

}

}

//中序遍歷

public?function??InOrderTraverse(){

$this->inTraverse($this->root);

return?self::$inArr;

}

private?function?inTraverse($root){

if($root){

$this->inTraverse($root->lchild);?//先中序遍歷左子樹

self::$inArr[]=$root->data;?//再訪問根節點

$this->inTraverse($root->rchild);//最后中序遍歷右子樹

}

}

//后序遍歷

public?function?PostOrderTraverse(){

$this->postTraverse($this->root);

return?self::$postArr;

}

private?function?postTraverse($root){

if($root){

$this->postTraverse($root->lchild);?//先后序遍歷左子樹

$this->postTraverse($root->rchild);?//再后序遍歷右子樹

self::$postArr[]=$root->data;?//最后再訪問根節點

}

}

//層序遍歷

public?function?LevelOrderTraverse(){

for($i=1;$i<=$this->BiTreeDepth();$i++){

$this->levelTraverse($this->root,$i);

}

return?self::$levelArr;

}

private?function?levelTraverse($root,$level){

if($root){

if($level==1){

self::$levelArr[]=$root->data;

}

$this->levelTraverse($root->lchild,$level-1);

$this->levelTraverse($root->rchild,$level-1);

}

}

//創建二叉樹

public?function?CreateBiTree(){

$this->createTree($this->root);

}

//此處使用先序輸入數據的方式來創建的

private?function?createTree(&$root){

$node=new?BiNode(mt_rand(1,20));

self::$count++;

if(self::$count<=pow(2,self::MAX_LEVEL)-1){

$root=$node;

self::$test[]=$root->data;

$this->createTree($root->lchild);

$this->createTree($root->rchild);

}

}

//判斷二叉樹是否為空

public?function?BiTreeEmpty(){

//????????if($this->root){

//????????????return?false;

//????????}else{

//????????????return?true;

//????????}

return?$this->root==null;

}

//返回二叉樹的深度

public?function?BiTreeDepth(){

return?$this->treeDepth($this->root);

}

private?function?treeDepth($root){

//求左子樹的深度

$arr=array();

$root=$this->root;

$level=0;

$num=0;

array_push($arr,$root);

while(count($arr)!=0){

$root=array_shift($arr);

$num++;

if($root->lchild){

array_push($arr,$root->lchild);

}

if($root->rchild){

array_push($arr,$root->rchild);

}

}

while($num>pow(2,$level-1)-1){

$level++;

}

$level--;

return?$level;

}

//返回二叉樹的根

public?function?Root(){

return?$this->root==null???'Null':$this->root->data;

}

//返回給定元素的雙親

//此處分別使用php內部的array_push()和array_shift()這兩個函數模擬隊列

/**

*?@param?$elem

*?@return?string

*?返回給定元素的雙親

*?思路：1.使用數組隊列來保存節點的指針

*???????2.將根節點從隊尾壓入數組隊列中

*???????3.然后取出隊首元素，使其左節點、右節點分別于給定的元素比較

*???????4.相等的就返回上一步中取出的隊首元素，否則，將此隊首元素的左右節點指針分別壓入隊尾

*???????5.重復第3步

*/

public?function?Parent($elem){

if($this->root){

$arr=array();//此處數組是當隊列來使用的，用于存放樹(包括子樹)的根指針

array_push($arr,$this->root);

while(count($arr)!=0){

$root=array_shift($arr);

if($root->lchild?&&?$root->lchild->data==$elem?||

$root->rchild?&&?$root->rchild->data==$elem){

return?$root->data;

}else{

if($root->lchild){

array_push($arr,$root->lchild);

}

if($root->rchild){

array_push($arr,$root->rchild);

}

}

}

}

return?false;

}

/**

*?@param?$elem?要返回左孩子的元素

*?@return?string

*?思路：同上

*/

public?function?LeftChild($elem){

if($this->root){

$arr=array();

array_push($arr,$this->root);

while(count($arr)!=0){

$root=array_shift($arr);

if($root->data==$elem?&&?$root->lchild){

return?$root->lchild->data;

}

if($root->lchild){

array_push($arr,$root->lchild);

}

if($root->rchild)?{

array_push($arr,?$root->rchild);

}

}

}

return?false;

}

/**

*?@param?$elem?要返回左孩子的元素

*?@return?string

*?思路：同上

*/

public?function?RightChild($elem){

if($this->root){

$arr=array();

array_push($arr,$this->root);

while(count($arr)!=0){

$root=array_shift($arr);

if($root->data==$elem?&&?$root->rchild){

return?$root->rchild->data;

}

if($root->lchild){

array_push($arr,$root->lchild);

}

if($root->rchild){

array_push($arr,$root->rchild);

}

}

}

return?false;

}

/**

*?@param?$elem?要返回左兄弟的元素

*?@return?string

*/

public?function?LeftSibling($elem){

$parent=$this->Parent($elem);

$leftChild=$this->LeftChild($parent);

$rightChild=$this->RightChild($elem);

if($rightChild==$elem?&&?$leftChild){

return?$leftChild;

}

return?'Error';

}

/**

*?@param?$elem?要返回右兄弟的元素

*?@return?string

*/

public?function?RightSibling($elem){

$parent=$this->Parent($elem);

$leftChild=$this->LeftChild($parent);

$rightChild=$this->RightChild($elem);

if($leftChild==$elem?&&?$rightChild){

return?$rightChild;

}

return?'Error';

}

/**

*?@param?$data?要插入的數據

*?思路：1.插入的數據比樹中的根(包括子樹)節點小時，就放在根節點的左子樹上；

*???????2.比根節點大時，插入到右子樹上；

*??注意：因為插入的位置不是葉節點就是只有左(或右)子樹的節點，所以可以得知此遞歸的出口肯定是某個節點的左(或右)子樹指針為空的時候。當此節點的左(右)都不為空的時候，遞歸就會持續下去，直到為左(右)子樹有一邊或全部為空的節點出現為止。

*/

public?function?Insert($data){

$node?=?new?BiNode($data);

$this->insertNode($node,$this->root);

}

private?function?insertNode($node,&$root){

if(!$root){

$root=$node;

}else{

if($node->data?>?$root->data){

$this->insertNode($node,$root->rchild);

}else?if($node->data?data){

$this->insertNode($node,$root->lchild);

}else{

return;

}

}

}

//非遞歸算法實現插入節點操作

public?function?insert2($data){

$node=new?BiNode($data);

if(!$this->root){

$this->root=$node;

}else?{

$arr?=?array();

array_push($arr,?$this->root);

while?(count($arr)?!=?0)?{

$root?=?array_shift($arr);

//表示如果要插入的數據$node->data大于根節點的數據$root->data并且根節點的

//左子樹為空的話，那么就將$node->data賦值給左子樹

if?($node->data?data?&&?!$root->lchild)?{

$root->lchild?=?$node;

break;

//此處為大于，思路與小于相似

}else?if($node->data?>?$root->data?&&?!$root->rchild){

$root->rchild?=?$node;

break;

}

//以下兩個if語句，表示如果上面的兩個條件都不滿足的話，那么就將跟的左右節點分別要入隊列，繼續循環

if($root->lchild){

array_push($arr,$root->lchild);

}

if($root->rchild){

array_push($arr,$root->rchild);

}

}

}

}

/**

*?@param?$elem?要刪除的那個節點的子樹

*?@param?$LR?表示是要刪除左子樹還是右子樹

*/

public?function?DeleteSubtree($elem,$LR){

if($this->root){

$arr=array();

array_push($arr,$this->root);

while(count($arr)!=0){

$root=array_shift($arr);

if($root->data==$elem?&&?$LR==0){

$root->lchild=null;

}

if($root->data==$elem?&&?$LR==1){

$root->rchild=null;

}

if($root->lchild){

array_push($arr,$root->lchild);

}

if($root->rchild){

array_push($arr,$root->rchild);

}

}

}

}

/*

以下是先序，中序，后序，層序的非遞歸實現算法

除了層序遍歷使用了隊列外，其他的是利用棧來實現的

思路:?1.輸出當前根節點

2.將當前根節點的右孩子做壓棧處理

3.將當前節點的右孩子作為新的根節點，如果為空的話，將棧頂元素彈出作為新的根節點。

4.重復1,2,3

*/

public?function?preOrderTraverse2(){

$arr=array();

$root=$this->root;

$arrPre=array();

while($root?||?count($arr)!=0){

$arrPre[]=$root->data;

if($root->rchild){

$rootR=$this->rchild;

array_push($arr,$rootR);

}

$root=$root->lchild;

if(!$root){

$root=array_pop($arr);

}

}

return?$arrPre;

}

/*

*?思路：1.將根節點壓棧

*???????2.彈出棧頂元素作為新的根節點

*???????3.根據棧——先進后出的特性，先進根節點的右孩子做壓棧處理，再將其左孩子做壓棧處理；

*???????4.重復2,3

*?注：此算法與上面的算法基本思想是相同的，只是細節處理上有所不同。

*/

public?function?preOrderTraverse3(){

$arr=array();

$root=$this->root;

array_push($arr,$root);

while(count($arr)!=0){

$root=array_pop($arr);

$arrPre[]=$root->data;

if($root->rchild){

array_push($arr,$root->rchild);

}

if($root->lchild){

array_push($arr,$root->lchild);

}

}

return?$arrPre;

}

//中序遍歷算法2

/*

*?思路：1.將根節點壓棧

*???????2.將根節點的左孩子作為新的根節點,對其進行遍歷

*???????3.如果左子樹遍歷完畢，就將棧中的左子樹結點彈出并輸出，然后將此彈出結點的右孩子作為新的根節點。

*???????4.重復1,2,3

*??注：此處或許有人對while循環的判斷條件有所不理解。因為假如說我們只用$root是否為空來作為判斷條件的話，那么當我們遍歷完左子樹后，程序就結束了，顯然不是我們要的結果；假如我們只用棧$arr是否為空為判斷條件的話，那么循環根本無法進行。

*

*/

public?function?inOrderTraverse2(){

$arr=array();

$root=$this->root;

while($root?||?count($arr)!=0){

if($root){

//根指針進棧，遍歷左子樹.此處之所以沒有在循環外先將整棵樹的根節點做壓棧處理，是因為，如果這樣做了，那么此處對左子樹的遍歷就會出現死循環，因為這是的判斷條件就是$root->lchild，而不是$root了，倘若還是$root那么棧中就會有兩個根(整棵樹)。

array_push($arr,$root);

$root=$root->lchild;

}else{

//根指針退棧，訪問根節點，遍歷右子樹

$root=array_pop($arr);

$arrIn[]=$root->data;

$root=$root->rchild;

}

}

return?$arrIn;

}

//中序遍歷算法3

/*

*?思路：1.先進根做壓棧處理

*???????2.遍歷左子樹

*???????3.取出棧頂元素并將輸出的節點作為新的根節點

*???????4.將根節點的右孩子壓棧并重新作為新的根節點

*???????5.重復2，3，4

*?注：此算法和上面的算法的整體思想是一樣的

*/

public?function?inOrderTraverse3(){

$arr?=?array();

$root?=?$this->root;

array_push($arr,$root);

while?(count($arr)?!=?0)?{

while($root){

array_push($arr,$root->lchild);

$root=$root->lchild;

}

array_pop($arr);

if(count($arr)!=0){

$root=array_pop($arr);

$arrIn[]=$root->data;

array_push($arr,$root->rchild);

$root=$root->rchild;

}

}

return?$arrIn;

}

//因為先序是根左右，而后序是左右根，如果將后序反轉180度的話，那么順序就是根右左.根據遞歸轉換為非遞歸(棧)的方法——如果一個函數內有多于一個的遞歸調用那么此時，棧的進入順序應該與遞歸調用的順序相反。因為棧的特性是先進后出。

//后序遍歷算法2

public?function?postOrderTraver2(){

$arr=array();

$root=$this->root;

array_push($arr,$root);

while(count($arr)!=0){

$root=array_pop($arr);

$arrPost[]=$root->data;

if($root->lchild){

array_push($arr,$root->lchild);

}

if($root->rchild){

array_push($arr,$root->rchild);

}

}

return?array_reverse($arrPost);

}

//層級遍歷算法2

public?function?levelOrderTraverse2(){

$arr=array();

$root=$this->root;

array_push($arr,$root);

while(count($arr)!=0){

$root=array_shift($arr);

$arrLevel[]=$root->data;

if($root->lchild){

array_push($arr,$root->lchild);

}

if($root->rchild){

array_push($arr,$root->rchild);

}

}

return?$arrLevel;

}

/*

*?遞歸轉非遞歸算法小結：

*??1.如果函數體內只有一個遞歸調用，那么直接使用棧或隊列等轉換即可；

*??2.如果有多個遞歸調用并且相鄰，比如先序和后序遍歷算法，那么轉為非遞歸算法時，先后順序要倒轉；

*??3.如果有多個遞歸但不相鄰，比如中序遍歷，那么就直接按照原先的順序依次轉換即可。但如果里面依然有部分相鄰，那么就按小結2操作。

*??4.轉換時，我們應該將哪些數據放入棧中呢。根據函數調用的原理，在調用一個函數時，內存中就會開辟一個棧空間，里面保存了函數的實參，局部變量和函數調用時的返回地址等，而我們要放入棧中的就是實參和局部變量(此處的局部變量是指后序遞歸要用到的局部變量)。

*/

}

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的php之二叉树,数据结构之二叉树——链式存储结构（php代码实现）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。