PHP实现的线索二叉树及二叉树遍历方法详解

本文实例讲述了PHP实现的线索二叉树及二叉树遍历方法。分享给大家供大家参考，具体如下：

<?phprequire "biTree.php";$str = "ko#be8#tr####acy#####";$tree = new BiTree（$str）;$tree->createThreadTree（）;echo $tree->threadList（） . "
";从第一个结点开始遍历线索二叉树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;}}?>

更多关于PHP相关内容感兴趣的读者可查看本站专题：《PHP数据结构与算法教程》、《PHP运算与运算符用法总结》、《PHP网络编程技巧总结》、《PHP基本语法入门教程》、《php操作office文档技巧总结（包括word,excel,access,ppt）》、《php日期与时间用法总结》、《php面向对象程序设计入门教程》、《php字符串（string）用法总结》、《php+mysql数据库操作入门教程》及《php常见数据库操作技巧汇总》
希望本文所述对大家PHP程序设计有所帮助。