首页 / 算法 / PHP实现的线索二叉树及二叉树遍历方法详解_php技巧

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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了PHP实现的线索二叉树及二叉树遍历方法详解_php技巧，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5976字，纯文字阅读大概需要9分钟。

内容图文

本文实例讲述了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(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;
    }
  }
?>

更多关于PHP相关内容感兴趣的读者可查看本站专题：《PHP数据结构与算法教程》、《PHP运算与运算符用法总结》、《PHP网络编程技巧总结》、《PHP基本语法入门教程》、《php操作office文档技巧总结(包括word,excel,access,ppt)》、《php日期与时间用法总结》、《php面向对象程序设计入门教程》、《php字符串(string)用法总结》、《php+mysql数据库操作入门教程》及《php常见数据库操作技巧汇总》

希望本文所述对大家PHP程序设计有所帮助。

内容总结

以上是互联网集市为您收集整理的PHP实现的线索二叉树及二叉树遍历方法详解_php技巧全部内容，希望文章能够帮你解决PHP实现的线索二叉树及二叉树遍历方法详解_php技巧所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/265555.html

来源：【匿名】

【上一篇】php数组冒泡排序算法实例_php技巧【下一篇】浅谈php实现映射的两种方法（链表和二叉树）

更多 ►

【PHP实现的线索二叉树及二叉树遍历方法详解_php技巧】教程文章相关的互联网学习教程文章

研磨数据结构与算法-12遍历二叉树【代码】

节点：/* * 二叉树节点 */public class Node {//数据项public long data;//数据项public String sData;//左子节点public Node leftChild;//右子节点public Node rightChild;/** * 构造方法 * @param data */public Node(long data,String sData) {this.data = data;this.sData = sData;}}二叉树：/* * 二叉树类 */public class Tree {//根节点public Node root;/** * 插入节点 * @param value */public void insert(long value,Str...

每天刷个算法题20160521：二叉树高度（递归与非递归）

版权所有。所有权利保留。欢迎转载，转载时请注明出处：http://blog.csdn.net/xiaofei_it/article/details/51502727为了防止思维僵化，每天刷个算法题。已经刷了几天了，现在发点代码。我已经建了一个开源项目，每天的题目都在里面：https://github.com/Xiaofei-it/Algorithms绝大部分算法都是我自己写的，没有参考网上通用代码。读者可能会觉得有的代码晦涩难懂，因为那是我自己的理解。最近几天都是在写一些原来的东西，大多数是...

Python -二叉树创建与遍历算法(很详细）【代码】

树表示由边连接的节点。它是一个非线性的数据结构。它具有以下特性。一个节点被标记为根节点。除根节点之外的每个节点都与一个父节点关联。每个节点可以有一个arbiatry编号的chid节点。我们使用前面讨论的os节点概念在python中创建了一个树数据结构。我们将一个节点指定为根节点，然后将更多的节点添加为子节点。下面是创建根节点的程序。创建树创建根我们只需要创建一个节点类并向节点添加赋值。这就变成了只有根节点的树。 1clas...

[算法题] 重建二叉树【代码】

题目描述输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。题目思路本题就是按照建立二叉树的思路建立就行了。先序遍历的第一个是根节点，然后在中序遍历找到该根节点，以此为界，中序遍历的左边是它的左子树的中序遍历，同样地找到该左子树在先序遍历中对应的先序遍历顺序。对于右子树也是一样的方法。本体采用递归，递归就要先写出终止条件。Python代码这个题...

新手算法学习之路----二叉树（二叉树最大路径和）【代码】

摘抄自：https://segmentfault.com/a/1190000003554858#articleHeader2题目：Given a binary tree, find the maximum path sum.The path may start and end at any node in the tree.For example: Given the below binary tree, 1/ 2 3 Return 6.思路：首先我们分析一下对于指定某个节点为根时，最大的路径和有可能是哪些情况。第一种是左子树的路径加上当前节点，第二种是右子树的路径加上当前节点，第三种是左右子树的路径加上...

【数据算法】Java实现二叉树存储以及遍历【代码】

二叉树在java中我们使用数组的形式保存原数据，这个数组作为二叉树的数据来源，后续对数组中的数据进行节点化操作。步骤就是原数据：数组节点化数据：定义 Node节点对象存储节点对象：通过LinkedList保存Node节点对象在操作过程中我们需要将当前结点和前一节点、后一节点进行关系绑定 package tree; import java.util.LinkedList; import java.util.List; /** * 功能：把一个数组的值存入二叉树中，然后进行3种方式的遍历 *...

二叉树三种遍历算法的递归和非递归实现（C++）

struct BinaryTreeNode {int m_nValue;BinaryTreeNode* m_pLeft;BinaryTreeNode* m_pRight; }; //递归前序遍历 void PreOrder(BinaryTreeNode* pNode) {if(pNode!=NULL){cout<<pNode->m_nValue<<endl;PreOrder(pNode->m_pLeft);PreOrder(pNode->m_pRight);} } //非递归前序遍历 /* 根据前序遍历访问的顺序，优先访问根结点，然后再分别访问左孩子和右孩子。即对于任一结点，其可看做是根结点，因此可以直接访问，访问完之后，若其...

二叉树中序遍历Joseph M. Morris算法【代码】

二叉树中序遍历，一种方法是递归，leetcode上的非递归方法有一种是用栈实现的，想来也没多大优化，手动递归比自动递归也快不了多少。还有一种不用栈的非递归方法，是Joseph M. Morris发明的，这位元老就是KMP算法中的M。下面代码来自贴吧大神，经测试可用。我还没研究具体是个怎么回事，时间上能达到100%vector<int> inorderTraversal(TreeNode* p) {vector<int> res;TreeNode* r = nullptr;while (p) {TreeNode* q = p->left;if (...

数据结构+算法第二天排序算法二叉树排序二叉树【代码】【图】

顺序查找查找原理:从列表中的第一个元素开始,我们按照基本的元素排序,简单的从一个元素移动到另一个元素,直到找到我们要找的元素或是遍历完整个列表.实例代码:def search(item,alist):find=Falselength=len(alist)for i in range(length):if alist[i] == item:find=Truereturn find对有序列表进行循环会提升查找的效率:def search(alist,item):find=Falselength=len(alist)pos=0stop=Falsewhile pos <=length andnot stop:if alist...

数据结构与算法系列----平衡二叉树（AVL树）【图】

一：背景平衡二叉树（又称AVL树）是二叉查找树的一个进化体，由于二叉查找树不是严格的O(logN)，所以引入一个具有平衡概念的二叉树，它的查找速度是O(logN)。所以在学习平衡二叉树之前，读者需要了解二叉查找树的实现，具体链接：二叉查找树那么平衡是什么意思？我们要求对于一棵二叉查找树，它的每一个节点的左右子树高度之差不超过1。（对于树的高度的约定：空节点高度是0；叶子节点高度是1。）例如下图：如果我们的二叉查找树是...

让我们来写个算法吧，（2）二叉树的前序，中序，后序遍历【代码】【图】

树的类结构publicclass TreeNode {TreeNode left;TreeNode right;int value;public TreeNode(int value ) {this.value = value;}}自己生成二叉树 private TreeNode createTreeNode() {TreeNode[] node = new TreeNode[10];// 以数组形式生成一棵完全二叉树for (int i = 0; i < 10; i++) {node[i] = new TreeNode(i);}for (int i = 0; i < 10; i++) {if (i * 2 + 1 < 10)node[i].left = node[i * 2 + 1];if (i * 2 + 2 < 10)node[i]...

数据结构与算法之美专栏学习笔记-二叉树基础(下）【代码】【图】

二叉查找树 Binary Search Tree 二叉查找树的定义二叉查找树又称二叉搜索树。其要求在二叉树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树的节点的值都大于这个节点的值。二叉查找树的查找操作二叉树类、节点类以及查找方法的代码实现先取根节点，如果它等于我们要查找的数据，那就返回。如果要查找的数据比根节点的值小，那就在左子树中递归查找；如果要查找的数据比根节点的值大，那就在右子树中...

剑指offer 6 重建二叉树【代码】

不用迭代器的代码class Solution { public:TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {TreeNode* root = NULL;int length_pre = pre.size();int length_vin = vin.size();if(length_pre <= 0 || length_vin <= 0)return root;return ConstructCore(pre,vin,0,length_pre-1,0,length_vin-1);}TreeNode* ConstructCore(vector<int> pre,vector<int> vin,int start_pre,int end_pre,int start_vin,int end_v...

二叉树的前中后序递归和非递归遍历操作【代码】

“遍历”是二叉树各种操作的基础，可以在遍历过程中对节点进行各种操作，如：求节点的双亲，求节点的孩子，判断节点的层次，当然，还有一些更重要的操作，例如，依据遍历序列建立二叉树，，再如，对建立的二叉树进行线索化，等等。二叉树的各种遍历操作必须了然于心，无论是递归的，还是非递归的。递归算法的优点是形式简单，当然，正如一句话所说“迭代是人，递归是神。”递归算法的整个详细过程还是很烧脑的，每一步都把未知当作...

4.3---建立高度最小二叉树【代码】

1，并没有把高度和建表结合了。而是最后才算。下一次可以想想怎么结合到一块去。1，建表（参考自书本）privatestatic TreeNode createMinimalBST(int arr[], int start, int end){if (end < start) {returnnull;}int mid = (start + end) / 2;TreeNode n = new TreeNode(arr[mid]);n.setLeftChild(createMinimalBST(arr, start, mid - 1));n.setRightChild(createMinimalBST(arr, mid + 1, end));return n;}publicstatic TreeNode ...

算法 - 最热教程

浅谈SQLServer查询优化器中的JOIN算法有没那种可逆算法是密文比明文短的呢？...javascript-类似Excel里面的NORMDIST函...C++中的分治算法及常见题目汇总压缩感知重构算法综述-学习笔记 c++中内置函数qsort（快速排序）和bsea...一、fpga图像处理算法整合基于遗传算法（deap）的非线性函数寻优...集成学习-Bagging集成学习算法随机森林...机器学习笔记（九）聚类算法及实践（K-...

首页 / 算法 / PHP实现的线索二叉树及二叉树遍历方法详解_php技巧

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

内容导读

内容图文

内容总结

内容备注

内容手机端

【PHP实现的线索二叉树及二叉树遍历方法详解_php技巧】教程文章相关的互联网学习教程文章

研磨数据结构与算法-12遍历二叉树【代码】

每天刷个算法题20160521：二叉树高度（递归与非递归）

Python -二叉树创建与遍历算法(很详细）【代码】

[算法题] 重建二叉树【代码】

新手算法学习之路----二叉树（二叉树最大路径和）【代码】

【数据算法】Java实现二叉树存储以及遍历【代码】

二叉树三种遍历算法的递归和非递归实现（C++）

二叉树中序遍历Joseph M. Morris算法【代码】

数据结构+算法第二天排序算法二叉树排序二叉树【代码】【图】

数据结构与算法系列----平衡二叉树（AVL树）【图】

让我们来写个算法吧，（2）二叉树的前序，中序，后序遍历【代码】【图】

数据结构与算法之美专栏学习笔记-二叉树基础(下）【代码】【图】

剑指offer 6 重建二叉树【代码】

二叉树的前中后序递归和非递归遍历操作【代码】

4.3---建立高度最小二叉树【代码】

PHP - 相关标签

算法 - 最新教程

算法 - 最热教程