`

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
<?
    /**
     * 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语言实现二叉树线索化

    ### C语言实现二叉树线索化 #### 一、引言 在计算机科学领域中,二叉树是一种常见的数据结构,被广泛应用于多种算法和数据处理任务中。线索化二叉树是二叉树的一种变形,它通过对空指针进行重新利用来提高二叉树的...

    C++线索二叉树类实现

    在C++中实现线索二叉树需要理解二叉树的基本概念以及链式存储结构。本文将深入探讨线索二叉树的原理和C++实现。 首先,我们要明确二叉树的基本概念。二叉树是由n(n&gt;=0)个有限节点组成的数据结构,这些节点通过边...

    数据结构5.10二叉树线索链表存储结构

    为了实现线索链表,每个结点除了原有的数据域和左右子树指针外,还需要增加两个标志位 `ltag` 和 `rtag` 来区分左右子树指针是普通指针还是线索指针。 - **ltag**: 如果为 0 表示左子树指针指向左孩子;如果为 1 ...

    二叉树的中序线索化和遍历

    我们将首先介绍二叉树的基本概念,然后讨论中序线索化算法的实现细节。最后,我们将讨论如何使用线索二叉树进行中序遍历。 二叉树的基本概念 ---------------- 二叉树是一种树形数据结构,它的每个节点最多有两个...

    二叉树的线索化实现

    线索二叉树是二叉树的一种特殊形式,它通过在二叉树的节点中添加额外的信息(线索)来辅助遍历,特别是对于中序遍历,可以实现连续的线性访问。 线索化的过程是将非空二叉树转换为线索二叉树,以便在不使用栈或队列...

    二叉树的线索化(中序线索二叉树)

    二叉树的线索化是一种将非线性结构转化为线性结构的技术,主要目的是为了提高二叉树的遍历效率,特别是对于中序遍历。...总的来说,理解和实现线索二叉树是深入理解数据结构和算法的重要一步,对提升编程技能大有裨益。

    线索化二叉树的实现

    "线索化二叉树的实现" 在计算机科学中,二叉树是一种重要的数据结构,它广泛应用于各种领域,如数据库、文件系统、编译器等。线索化二叉树是一种特殊的二叉树,它在二叉树的每个节点中添加了指向其前驱和后继节点的...

    线索二叉树的建立、删除、插入、恢复线索

    线索二叉树的恢复线索可以通过遍历二叉树并将每个结点的空指针域修改为指向其前驱和后继结点的指针来实现。该过程可以分为以下步骤: 1. 对二叉树进行遍历,访问每个结点。 2. 对每个结点,如果其左子树为空,则将...

    线索二叉树(数据结构课设)

    提供的“线索二叉树”文件可能包含了实现线索二叉树的C++代码,包括节点定义、插入、删除、遍历等操作。这样的代码实例对于学习者来说是非常宝贵的资源,可以通过阅读和运行代码来加深对线索二叉树的理解。 总结来...

    c++线索二叉树源代码

    在C++中实现线索二叉树,首先需要定义一个结构体来表示二叉树的节点,包含数据、左孩子指针、右孩子指针以及前后线索。例如: ```cpp struct ThreadNode { int data; ThreadNode* lchild; ThreadNode* rchild; ...

    中序线索二叉树(建立二叉树,线索化,输出二叉树)

    中序线索二叉树(建立二叉树,线索化,输出二叉树)

    xml实现二叉树排序

    在这里,我们将深入探讨如何利用XML来实现二叉树排序的过程。 首先,我们要理解二叉树的基本概念。一个二叉树由根节点开始,可以有零个、一个或两个子节点,分别称为左子节点和右子节点。二叉排序树是一种特殊的...

    二叉树的线索化 C++代码

    ### 二叉树的线索化及其C++实现 #### 一、什么是二叉树的线索化? 二叉树的线索化是一种对二叉树进行特殊处理的方法,它通过对二叉树节点指针域的改造来使得能够高效地进行中序遍历等操作。在未经过线索化的二叉树...

    线索化二叉树C实现代码

    下面是一个简单的C语言实现线索化二叉树的例子,这里仅给出中序遍历的线索化过程: ```c typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; bool isThreadLeft; // 标志位,...

    设计程序实现二叉树结点的类型定义和对二叉树的基本操作

    以上内容覆盖了如何设计并实现二叉树结点的类型定义以及对二叉树的基本操作,包括二叉树的构建、初始化、以及不同类型的遍历。通过这些实践,可以帮助学习者更好地理解和掌握二叉树这一数据结构。

    第五章树与二叉树4线索二叉树.ppt

    数据结构 树与二叉树 线索二叉树 关于树与二叉树的线索二叉树小节课件

    Java实现二叉树中序线索化(图形界面 含代码)

    Java实现二叉树中序线索化 左键画节点 右键画跟 点可以拖动 两个节点可以连线 确认进行线索化 并画出线索

    C++数据结构-二叉树和线索二叉树

    基于二叉链表的二叉树,实现了二叉树的多种操作:添加、删除、拷贝、清空、树深度计算、父节点...使用模板偏特化继承并实现了线索二叉树,实现了中序线索建立、遍历算法和迭代器。程序编码风格良好,关键算法注释详细。

    二叉树线索化中序遍历

    "threadtree1"这个文件可能是实现二叉树线索化中序遍历的代码示例或者测试用例。在实际编程中,通常会包含一个二叉树节点的结构定义,以及线索化和中序遍历的函数。通过分析和运行这个文件,你可以更深入地理解线索...

    数据结构--二叉树--线索化二叉树

    线索化二叉树是一种特殊的二叉树,它通过在二叉链表的空指针位置附加线索,帮助我们在非递归方式下实现二叉树的遍历。中序遍历是二叉树遍历的一种,按照“左子树-根节点-右子树”的顺序访问节点。 中序线索化二叉树...

Global site tag (gtag.js) - Google Analytics