PHP教程之PHP完成二叉树/线索二叉树
到现在，对排版还是不很熟练，经常会排不好。 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 <? //结点类 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; } } ?> 接触MYSQL，开始设计数据库程序 其实没啥难的，多练习，练习写程序，真正的实践比看100遍都有用。不过要熟悉引擎 php里的数组为空的时候是不能拿来遍历的；（这个有点低级啊，不过我刚被这个边界问题墨迹了好长一会） 其实没啥难的，多练习，练习写程序，真正的实践比看100遍都有用。不过要熟悉引擎 我学习了一段时间后，我发现效果并不好（估计是我自身的问题）。因为一个人的精力总是有限的，同时学习这么多，会导致每个的学习时间都得不到保证。 当留言板完成的时候，下步可以把做1个单人的blog程序，做为目标， 个人呢觉得，配wamp 最容易漏的一步就是忘了把$PHP$目录下的libmysql.dll拷贝到windows系统目录的system32目录下，还有重启apache。 php里的数组为空的时候是不能拿来遍历的；（这个有点低级啊，不过我刚被这个边界问题墨迹了好长一会） 首先声明：我是一个菜鸟，是一个初学者。学习了一段php后总是感觉自己没有提高，无奈。经过反思我认为我学习过程中存在很多问题，我改变了学习方法后自我感觉有了明显的进步。 实践是检验自己会不会的真理。 有位前辈曾经跟我说过，phper 至少要掌握200个函数 编起程序来才能顺畅点，那些不熟悉的函数记不住也要一拿手册就能找到。所以建议新手们没事就看看php的手册（至少array函数和string函数是要记牢的）。 环境搭建好,当你看见你的浏览器输出“it works\\\\\\\"时你一定是喜悦的。在你解决问题的时候，我强烈建议多读php手册。 当留言板完成的时候，下步可以把做1个单人的blog程序，做为目标， 先学习php和mysql,还有css(html语言很简单)我认为现在的效果比以前的方法好。 个人呢觉得，配wamp 最容易漏的一步就是忘了把$PHP$目录下的libmysql.dll拷贝到windows系统目录的system32目录下，还有重启apache。 Apache不是非得用80或者8080端口的，我刚开始安得时候就是80端口老占用，就用了个 81端口，结果照常，就是输localhost的时候，应该输入为 localhost:81 说php的话，首先得提一下数组，开始的时候我是最烦数组的，总是被弄的晕头转向，不过后来呢，我觉得数组里php里最强大的存储方法，所以建议新手们要学好数组。 如果你已经到这种程度了，那么你已经可以做我的老师了。其实php也分很多的区域， 对于懒惰的朋友，我推荐php的集成环境xampp或者是wamp。这两个软件安装方便，使用简单。但是我还是强烈建议自己动手搭建开发环境。 基础有没有对学习php没有太大区别，关键是兴趣。
页:
[1]