- 浏览: 136828 次
- 性别:
- 来自: 北京
文章分类
最新评论
<?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 1344直接上代码. #include <stdio.h> ... -
nginx hash源码分析
2013-02-05 19:05 1222HASH是NGINX核心数据结构之一.见几个链接.分析的很详细 ... -
贪心算法与动态规划的区别
2012-11-24 21:07 31811.贪心算法和动态规划区别 贪心算法是自顶向下的,它会先做在 ... -
PHP实现各种排序
2011-11-23 17:32 932<?php /** * 各种排序 * @aut ... -
PHP实现平衡二叉树(AVL树)
2011-11-20 17:20 2933<?php require 'bstOrder ... -
PHP实现克鲁斯卡尔(kruscal)算法
2011-11-05 21:18 1178<?php require 'edge.php ... -
PHP实现图的邻接矩阵及普里姆(prim算法),弗洛伊德(floyd),迪杰斯特拉(dijkstra)算法
2011-11-02 18:35 4630<?php require 'mGraph.p ... -
php实现图的邻接表,关键路径,拓朴排序
2011-11-02 18:30 1825<?php //调用 require ... -
php 实现KMP算法
2011-10-23 12:32 1842<?php /** * KMP算法的P ... -
php实现单链表(静态链表)
2011-10-21 14:40 1811<?php /* * 单链表的PH ...
相关推荐
### C语言实现二叉树线索化 #### 一、引言 在计算机科学领域中,二叉树是一种常见的数据结构,被广泛应用于多种算法和数据处理任务中。线索化二叉树是二叉树的一种变形,它通过对空指针进行重新利用来提高二叉树的...
在C++中实现线索二叉树需要理解二叉树的基本概念以及链式存储结构。本文将深入探讨线索二叉树的原理和C++实现。 首先,我们要明确二叉树的基本概念。二叉树是由n(n>=0)个有限节点组成的数据结构,这些节点通过边...
为了实现线索链表,每个结点除了原有的数据域和左右子树指针外,还需要增加两个标志位 `ltag` 和 `rtag` 来区分左右子树指针是普通指针还是线索指针。 - **ltag**: 如果为 0 表示左子树指针指向左孩子;如果为 1 ...
我们将首先介绍二叉树的基本概念,然后讨论中序线索化算法的实现细节。最后,我们将讨论如何使用线索二叉树进行中序遍历。 二叉树的基本概念 ---------------- 二叉树是一种树形数据结构,它的每个节点最多有两个...
线索二叉树是二叉树的一种特殊形式,它通过在二叉树的节点中添加额外的信息(线索)来辅助遍历,特别是对于中序遍历,可以实现连续的线性访问。 线索化的过程是将非空二叉树转换为线索二叉树,以便在不使用栈或队列...
二叉树的线索化是一种将非线性结构转化为线性结构的技术,主要目的是为了提高二叉树的遍历效率,特别是对于中序遍历。...总的来说,理解和实现线索二叉树是深入理解数据结构和算法的重要一步,对提升编程技能大有裨益。
"线索化二叉树的实现" 在计算机科学中,二叉树是一种重要的数据结构,它广泛应用于各种领域,如数据库、文件系统、编译器等。线索化二叉树是一种特殊的二叉树,它在二叉树的每个节点中添加了指向其前驱和后继节点的...
线索二叉树的恢复线索可以通过遍历二叉树并将每个结点的空指针域修改为指向其前驱和后继结点的指针来实现。该过程可以分为以下步骤: 1. 对二叉树进行遍历,访问每个结点。 2. 对每个结点,如果其左子树为空,则将...
提供的“线索二叉树”文件可能包含了实现线索二叉树的C++代码,包括节点定义、插入、删除、遍历等操作。这样的代码实例对于学习者来说是非常宝贵的资源,可以通过阅读和运行代码来加深对线索二叉树的理解。 总结来...
在C++中实现线索二叉树,首先需要定义一个结构体来表示二叉树的节点,包含数据、左孩子指针、右孩子指针以及前后线索。例如: ```cpp struct ThreadNode { int data; ThreadNode* lchild; ThreadNode* rchild; ...
中序线索二叉树(建立二叉树,线索化,输出二叉树)
在这里,我们将深入探讨如何利用XML来实现二叉树排序的过程。 首先,我们要理解二叉树的基本概念。一个二叉树由根节点开始,可以有零个、一个或两个子节点,分别称为左子节点和右子节点。二叉排序树是一种特殊的...
### 二叉树的线索化及其C++实现 #### 一、什么是二叉树的线索化? 二叉树的线索化是一种对二叉树进行特殊处理的方法,它通过对二叉树节点指针域的改造来使得能够高效地进行中序遍历等操作。在未经过线索化的二叉树...
下面是一个简单的C语言实现线索化二叉树的例子,这里仅给出中序遍历的线索化过程: ```c typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; bool isThreadLeft; // 标志位,...
以上内容覆盖了如何设计并实现二叉树结点的类型定义以及对二叉树的基本操作,包括二叉树的构建、初始化、以及不同类型的遍历。通过这些实践,可以帮助学习者更好地理解和掌握二叉树这一数据结构。
数据结构 树与二叉树 线索二叉树 关于树与二叉树的线索二叉树小节课件
Java实现二叉树中序线索化 左键画节点 右键画跟 点可以拖动 两个节点可以连线 确认进行线索化 并画出线索
基于二叉链表的二叉树,实现了二叉树的多种操作:添加、删除、拷贝、清空、树深度计算、父节点...使用模板偏特化继承并实现了线索二叉树,实现了中序线索建立、遍历算法和迭代器。程序编码风格良好,关键算法注释详细。
"threadtree1"这个文件可能是实现二叉树线索化中序遍历的代码示例或者测试用例。在实际编程中,通常会包含一个二叉树节点的结构定义,以及线索化和中序遍历的函数。通过分析和运行这个文件,你可以更深入地理解线索...
线索化二叉树是一种特殊的二叉树,它通过在二叉链表的空指针位置附加线索,帮助我们在非递归方式下实现二叉树的遍历。中序遍历是二叉树遍历的一种,按照“左子树-根节点-右子树”的顺序访问节点。 中序线索化二叉树...