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; } } ?>
![VIP课程(WEB全栈开发)](http://m.sbmmt.com/img/upload/course/000/000/071/628e00599d7e4913.png)
相关文章推荐
• 【腾讯云】年中优惠,「专享618元」优惠券!• 20+值得了解的PHP面试题(附答案分析)• 使用 MySQL 开始 PHP 会话_PHP• GD输出汉字的函数的分析_PHP• PHP中 ADOdb 类库介绍(二)_PHP• 用PHP5进行三层开发_PHP独孤九贱(3)_JavaScript视频教程
javascript是运行在浏览器上的脚本语言,连续多年,被评为全球最受欢迎的编程语言。是前端开发必备三大法器中,最具杀伤力。如果前端开发是降龙十八掌,好么javascript就是第18掌:亢龙有悔。没有它,你的前端生涯是不完整的。《php.cn独孤九贱(3)-JavaScript视频教程》课程特色:php中文网原创幽默段子系列课程,以恶搞,段子为主题风格的php视频教程!轻松的教学风格,简短的教学模式,让同学们在不知不觉中,学会了javascript知识。
JavaScript教程125816次播放
独孤九贱(6)_jQuery视频教程
jQuery是一个快速、简洁的JavaScript框架。设计的宗旨是“write Less,Do More”,即倡导写更少的代码,做更多的事情。它封装JavaScript常用的功能代码,提供一种简便的JavaScript设计模式,优化HTML文档操作、事件处理、动画设计和Ajax交互。 核心特性可以总结为:具有独特的链式语法和短小清晰的多功能接口;具有高效灵活的css选择器,并且可对CSS选择器进行扩展;拥有便捷的插件扩展机制和丰富的插件。兼容各种主流浏览器,如IE 6.0+、FF 1.5+、Safari 2.0+、Opera 9.0+等,是全球最流行的前端开发框架之一。PHP中文网根据最新版本,独家录制jQuery最新视频教程,回馈PHP中文网的新老用户。
jQuery教程104062次播放
jQuery与Ajax基础与实战
jQuery是最流行的JS函数库,封装了许多实用的功能,其中最引人入胜的就是Ajax。 jQuery中的Ajax操作,语法简单,操作方便,使Ajax从未如此轻松,前端人员从此不再为与服务器异步交互而发愁,本套课程,精选了最常用的几个方法,从基本的语法到每个参数,再到具体实例进行了全面的讲解。
AJAX教程5148次播放
Git教程(60分钟全程无废话版)
Git 是一个开源的分布式版本控制系统,用于敏捷高效地处理任何或小或大的项目。 Git 是 Linus Torvalds 为了帮助管理 Linux 内核开发而开发的一个开放源码的版本控制软件。 Git 与常用的版本控制工具 CVS, Subversion 等不同,它采用了分布式版本库的方式,不必服务器端软件支持
JavaScript教程4431次播放