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

php  /  管理员 发布于 7年前   132

本文实例讲述了PHP实现的线索二叉树及二叉树遍历方法。分享给大家供大家参考，具体如下：

createThreadTree();  echo $tree->threadList() . "\n";从第一个结点开始遍历线索二叉树  echo $tree->threadListReserv();从最后一个结点开始反向遍历?>

biTree.php：

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 Class&Object -- PHP 自排序二叉树的深入解析
• PHP实现二叉树的深度优先与广度优先遍历方法
• php实现的二叉树遍历算法示例
• PHP构造二叉树算法示例
• PHP实现绘制二叉树图形显示功能详解【包括二叉搜索树、平衡树及红黑树】
• PHP实现从上往下打印二叉树的方法
• PHP基于非递归算法实现先序、中序及后序遍历二叉树操作示例
• PHP获取二叉树镜像的方法
• PHP实现判断二叉树是否对称的方法
• PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解
• PHP排序二叉树基本功能实现方法示例