本文實例講述了PHP實現的線索二叉樹及二叉樹遍歷方法。分享給大家供大家參考，具體如下：
<?php require 'biTree.php'; $str = 'ko#be8#tr####acy#####'; $tree = new BiTree($str); $tree->createThreadTree(); echo $tree->threadList() . "/n";從第一個結點開始遍歷線索二叉樹 echo $tree->threadListReserv();從最后一個結點開始反向遍歷?>
biTree.php：
<? /** * PHP實現二叉樹 * * @author zhaojiangwei * @since 2011/10/25 10:32 */ //結點類 class Node{ private $data = NULL; private $left = NULL; private $right = NULL; private $lTag = 0; private $rTag = 0; public function Node($data = false){ $this->data = $data; } //我不喜歡使用魔術方法 public function getData(){ return $this->data; } public function setData($data){ $this->data = $data; } public function getLeft(){ return $this->left; } public function setLeft($left){ $this->left = $left; } public function getRight(){ return $this->right; } public function setRight($right){ $this->right = $right; } public function getLTag(){ return $this->lTag; } public function setLTag($tag){ $this->lTag = $tag; } public function getRTag(){ return $this->rTag; } public function setRTag($tag){ $this->rTag = $tag; } } //線索二叉樹類 class BiTree{ private $datas = NULL;//要導入的字符串; private $root = NULL; //根結點 private $leafCount = 0;//葉子結點個數 private $headNode = NULL; //線索二叉樹的頭結點 private $preNode = NULL;//遍歷線索化二叉樹時保存前一個遍歷的結點 public function BiTree($datas){ is_array($datas) || $datas = str_split($datas); $this->datas = $datas; $this->backupData = $this->datas; $this->createTree(TRUE); } //前序遍歷創建樹 //$root 判斷是不是要創建根結點 public function createTree($root = FALSE){ if(emptyempty($this->datas)) return NULL; $first = array_shift($this->datas); if($first == '#'){ return NULL; }else{ $node = new Node($first); $root && $this->root = $node; $node->setLeft($this->createTree()); $node->setRight($this->createTree()); return $node; } } //返回二叉樹葉子結點的個數 public function getLeafCount(){ $this->figureLeafCount($this->root); return $this->leafCount; } private function figureLeafCount($node){ if($node == NULL) return false; if($this->checkEmpty($node)){ $this->leafCount ++; }else{ $this->figureLeafCount($node->getLeft()); $this->figureLeafCount($node->getRight()); } } //判斷結點是不是葉子結點 private function checkEmpty($node){ if($node->getLeft() == NULL && $node->getRight() == NULL){ return true; } return false; } //返回二叉樹深度 public function getDepth(){ return $this->traversDepth($this->root); } //遍歷求二叉樹深度 public function traversDepth($node){ if($node == NULL){ return 0; } $u = $this->traversDepth($node->getLeft()) + 1; $v = $this->traversDepth($node->getRight()) + 1; return $u > $v ? $u : $v; } //返回遍歷結果,以字符串的形式 //$order 按遍歷形式返回,前中后 public function getList($order = 'front'){ if($this->root == NULL) return NULL; $nodeList = array(); switch ($order){ case "front": $this->frontList($this->root, $nodeList); break; case "middle": $this->middleList($this->root, $nodeList); break; case "last": $this->lastList($this->root, $nodeList); break; default: $this->frontList($this->root, $nodeList); break; } return implode($nodeList); } //創建線索二叉樹 public function createThreadTree(){ $this->headNode = new Node(); $this->preNode = & $this->headNode; $this->headNode->setLTag(0); $this->headNode->setLeft($this->root); $this->headNode->setRTag(1); $this->threadTraverse($this->root); $this->preNode->setRight($this->headNode); $this->preNode->setRTag(1); $this->headNode->setRight($this->preNode); } //線索化二叉樹 private function threadTraverse($node){ if($node != NULL){ if($node->getLeft() == NULL){ $node->setLTag(1); $node->setLeft($this->preNode); }else{ $this->threadTraverse($node->getLeft()); } if($this->preNode != $this->headNode && $this->preNode->getRight() == NULL){ $this->preNode->setRTag(1); $this->preNode->setRight($node); } $this->preNode = & $node;//注意傳引用 $this->threadTraverse($node->getRight()); } } //從第一個結點遍歷中序線索二叉樹 public function threadList(){ $arr = array(); for($node = $this->getFirstThreadNode($this->root); $node != $this->headNode; $node = $this->getNextNode($node)){ $arr[] = $node->getData(); } return implode($arr); } //從尾結點反向遍歷中序線索二叉樹 public function threadListReserv(){ $arr = array(); for($node = $this->headNode->getRight(); $node != $this->headNode; $node = $this->getPreNode($node)){ $arr[] = $node->getData(); } return implode($arr); } //返回某個結點的前驅 public function getPreNode($node){ if($node->getLTag() == 1){ return $node->getLeft(); }else{ return $this->getLastThreadNode($node->getLeft()); } } //返回某個結點的后繼 public function getNextNode($node){ if($node->getRTag() == 1){ return $node->getRight(); }else{ return $this->getFirstThreadNode($node->getRight()); } } //返回中序線索二叉樹的第一個結點 public function getFirstThreadNode($node){ while($node->getLTag() == 0){ $node = $node->getLeft(); } return $node; } //返回中序線索二叉樹的最后一個結點 public function getLastThreadNode($node){ while($node->getRTag() == 0){ $node = $node->getRight(); } return $node; } //前序遍歷 private function frontList($node, & $nodeList){ if($node !== NULL){ $nodeList[] = $node->getData(); $this->frontList($node->getLeft(), $nodeList); $this->frontList($node->getRight(), $nodeList); } } //中序遍歷 private function middleList($node, & $nodeList){ if($node != NULL){ $this->middleList($node->getLeft(), $nodeList); $nodeList[] = $node->getData(); $this->middleList($node->getRight(), $nodeList); } } //后序遍歷 private function lastList($node, & $nodeList){ if($node != NULL){ $this->lastList($node->getLeft(), $nodeList); $this->lastList($node->getRight(), $nodeList); $nodeList[] = $node->getData(); } } public function getData(){ return $this->data; } public function getRoot(){ return $this->root; } }?> 
