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

2020-03-22 17:30:40

字体：大中小

来源：转载

供稿：网友

本文实例讲述了PHP实现的线索二叉树及二叉树遍历方法。分享给大家供大家参考，具体如下： require 'biTree.php'; $str = 'ko#be8#tr####acy#####'; $tree = new BiTree($str); $tree- createThreadTree(); echo $tree- threadList() . "/n";从第一个结点开始遍历线索二叉树 echo $tree- threadListReserv();从最后一个结点开始反向遍历
private $headNode = NULL; //线索二叉树的头结点 private $preNode = NULL;//遍历线索化二叉树时保存前一个遍历的结点 html' target='_blank'>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 = //注意传引用 $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程序设计有所帮助。PHP教程

郑重声明：本文版权归原作者所有，转载文章仅为传播更多信息之目的，如作者信息标记有误，请第一时间联系我们修改或删除，多谢。

上一篇：PHP实现的HashTable及说明

下一篇：关于PHP中Session文件过多的问题及session文件保存位置