- 浏览: 134535 次
- 性别:
- 来自: 北京
文章分类
最新评论
<?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; } } ?>
发表评论
文章已被作者锁定,不允许评论。
-
c实现bitmap
2013-05-14 14:34 1306直接上代码. #include <stdio.h> ... -
nginx hash源码分析
2013-02-05 19:05 1186HASH是NGINX核心数据结构之一.见几个链接.分析的很详细 ... -
贪心算法与动态规划的区别
2012-11-24 21:07 31341.贪心算法和动态规划区别 贪心算法是自顶向下的,它会先做在 ... -
PHP实现各种排序
2011-11-23 17:32 892<?php /** * 各种排序 * @aut ... -
PHP实现平衡二叉树(AVL树)
2011-11-20 17:20 2893<?php require 'bstOrder ... -
PHP实现克鲁斯卡尔(kruscal)算法
2011-11-05 21:18 1145<?php require 'edge.php ... -
PHP实现图的邻接矩阵及普里姆(prim算法),弗洛伊德(floyd),迪杰斯特拉(dijkstra)算法
2011-11-02 18:35 4606<?php require 'mGraph.p ... -
php实现图的邻接表,关键路径,拓朴排序
2011-11-02 18:30 1797<?php //调用 require ... -
php 实现KMP算法
2011-10-23 12:32 1809<?php /** * KMP算法的P ... -
php实现单链表(静态链表)
2011-10-21 14:40 1780<?php /* * 单链表的PH ...
相关推荐
通过c语言实现二叉树的线索化,其中分四个子函数。
PHP实现二叉树图
线索二叉树的一些基本功能 遍历 二叉树线索化 等等
本节主要讲述二叉树的线索链表存储结构和相关操作
中序线索二叉树(建立二叉树,线索化,输出二叉树)
二叉树的中序线索化,包括进行线索化和遍历线索二叉树。
线索化二叉树的实现 很详细,二叉树各种遍历算法
数据结构 树与二叉树 线索二叉树 关于树与二叉树的线索二叉树小节课件
运用xml相关技术,实现二叉树的排序。先输入一组数字,排序之后插入到数据库,最后通过xml导出。
二叉树的线索化,和遍历线索化二叉树 二叉树的线索化,和遍历线索化二叉树 二叉树的线索化,和遍历线索化二叉树
Java实现二叉树中序线索化 左键画节点 右键画跟 点可以拖动 两个节点可以连线 确认进行线索化 并画出线索
基于二叉链表的二叉树,实现了二叉树的多种操作:添加、删除、拷贝、清空、树深度计算、父节点...使用模板偏特化继承并实现了线索二叉树,实现了中序线索建立、遍历算法和迭代器。程序编码风格良好,关键算法注释详细。
自己做的线索二叉树,数据结构课设的时候可以参考哦!编译过的cpp文件。欢迎下载!
设计程序实现二叉树结点的类型定义和对二叉树的基本操作。该程序包括二叉树结构类型以及每一种操作的具体的函数定义和主函数。 1 按先序次序建立一个二叉树 2按(A:先序 B:中序 C:后序 )遍历输出二叉树的所有结点
线索二叉树的实现 C#实现 线索二叉树的实现 C#实现
java使用jtree动态实现二叉树,包含二叉树的插入删除很查找
线索二叉树的建立 删除 插入 恢复线索
可实现以下功能: ************Menu************ 1---建立二叉树 2---前序遍历(递归) 3---前序遍历(非递归) 4---中序遍历(递归) 5---中序遍历(非递归) 6---后序遍历(递归) 7---后序遍历(非递归)...
数据结构 线索二叉树 严蔚敏 数据结构 线索二叉树 严蔚敏 数据结构 线索二叉树 严蔚敏 数据结构 线索二叉树 严蔚敏 数据结构 线索二叉树 严蔚敏 数据结构 线索二叉树 严蔚敏
包含两种线索化二叉树方法,具体如下: 1.利用结点中的空指针域,使其指向后继结点; 2.利用线性表保存二叉树的遍历顺序。