php实现二叉树,线索二叉树
createthreadtree(); echo $tree->threadlist() . \n;从第一个结点开始遍历线索二叉树 echo $tree->threadlistreserv();从最后一个结点开始反向遍历?>
bitree.phpdata = $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; } }?>