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(empty($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; } }?>