<?php
class tree
{
private $data = [];
private $size = 0;
function __construct($data){
is_array($data) && $this->init($data);
}
public function init(array $data){
$this->data = $data;
$this->size = count($data);
}
public function getRoot(){
return $this->getNodeByIndex(0);
}
public function getNodeByIndex(int $index){
return $this->data[$index] ? ["index" => $index, "value" => $this->data[$index]] : false;
}
public function leftChild(int $index){
return $this->getNodeByIndex($index*2 + 1);
}
public function rightChild(int $index){
return $this->getNodeByIndex($index*2 + 2);
}
private function setNodeByIndex(int $index, $value){
if(!isset($this->data[$index])) $this->size++;
$this->data[$index] = $value;
}
public function setLeftChild(int $index, $value){
$this->setNodeByIndex($index*2 + 1, $value);
}
public function setRightChild(int $index, $value){
$this->setNodeByIndex($index*2 + 2, $value);
}
public function preOrder(){
$queue = [];
if($this->getRoot() === false) return [];
$node = false;
$queue[] = $this->getRoot();
while (!empty($queue)){
$node = array_pop($queue);
print $node["value"]." ";
$left = $this->leftChild($node["index"]);
$right = $this->rightChild($node["index"]);
if(false !== $right){
$queue[] = $right;
}
if(false !== $left){
$queue[] = $left;
}
}
}
public function postOrder(){
$queue = [];
if($this->getRoot() === false) return [];
$node = false;
$queue[] = $this->getRoot();
$res = [];
while (!empty($queue)){
$node = array_pop($queue);
array_unshift($res, $node["value"]);
$right = $this->rightChild($node["index"]);
$left = $this->leftChild($node["index"]);
if(false !== $left){
$queue[] = $left;
}
if(false !== $right){
$queue[] = $right;
}
}
var_dump($res);
}
public function postOrderWithoutStack(){
if($this->getRoot() === false) return '';
$currentIndex = 0;
$currentAction = "down";
$lastIndex = false;
while ($currentIndex >= 0 && ($currentIndex !== $lastIndex)){
if($this->leftChild($currentIndex) === false && $this->rightChild($currentIndex) === false){
$currentAction = 'up';
$lastIndex = $currentIndex;
if($this->getNodeByIndex($currentIndex) !== false) print $this->getNodeByIndex($currentIndex)["value"]." ";
$currentIndex = intval(($currentIndex-1)/2);
}
if($currentAction == 'down'){//下沉
$lastIndex = $currentIndex;
$currentIndex = $currentIndex*2+1;
}else {//回溯
if($lastIndex == $currentIndex*2+2){//上一个节点是当前右孩子
print $this->getNodeByIndex($currentIndex)['value']." ";
$lastIndex = $currentIndex;
$currentIndex = intval(($currentIndex-1)/2);
}
else if($lastIndex == $currentIndex*2+1){//上一个节点是当前左孩子
if($this->rightChild($currentIndex) !== false){//当前节点有右孩子
$lastIndex = $currentIndex;
$currentIndex = $currentIndex*2+2;
$currentAction = 'down';
}else {
print $this->getNodeByIndex($currentIndex)['value']." ";
$lastIndex = $currentIndex;
$currentIndex = intval(($currentIndex-1)/2);
}
}
}
}
}
public function preOrderWithoutStack(){
if($this->getRoot() === false) return '';
$currentIndex = 0;
$currentAction = "down";
$lastIndex = false;
while ($currentIndex >= 0 && ($currentIndex !== $lastIndex)){
if($this->leftChild($currentIndex) === false && $this->rightChild($currentIndex) === false){
$currentAction = 'up';
$lastIndex = $currentIndex;
if($this->getNodeByIndex($currentIndex) !== false) print $this->getNodeByIndex($currentIndex)["value"]." ";
$currentIndex = intval(($currentIndex-1)/2);
}
if($currentAction == 'down'){//下沉
$lastIndex = $currentIndex;
if($this->getNodeByIndex($currentIndex) !== false) print $this->getNodeByIndex($currentIndex)["value"]." ";
$currentIndex = $currentIndex*2+1;
}else {//回溯
if($lastIndex == $currentIndex*2+2){//上一个节点是当前右孩子
$lastIndex = $currentIndex;
$currentIndex = intval(($currentIndex-1)/2);
}
else if($lastIndex == $currentIndex*2+1){//上一个节点是当前左孩子
if($this->rightChild($currentIndex) !== false){//当前节点有右孩子
$lastIndex = $currentIndex;
$currentIndex = $currentIndex*2+2;
$currentAction = 'down';
}else {
$lastIndex = $currentIndex;
$currentIndex = intval(($currentIndex-1)/2);
}
}
}
}
}
public function middleOrderWithoutStack(){
if($this->getRoot() === false) return '';
$currentIndex = 0;
$currentAction = "down";
$lastIndex = false;
while ($currentIndex >= 0 && ($currentIndex !== $lastIndex)){
if($this->leftChild($currentIndex) === false && $this->rightChild($currentIndex) === false){
$currentAction = 'up';
$lastIndex = $currentIndex;
if($this->getNodeByIndex($currentIndex) !== false) print $this->getNodeByIndex($currentIndex)["value"]." ";
$currentIndex = intval(($currentIndex-1)/2);
}
if($currentAction == 'down'){//下沉
$lastIndex = $currentIndex;
$currentIndex = $currentIndex*2+1;
}else {//回溯
if($lastIndex == $currentIndex*2+2){//上一个节点是当前右孩子
$lastIndex = $currentIndex;
$currentIndex = intval(($currentIndex-1)/2);
}
else if($lastIndex == $currentIndex*2+1){//上一个节点是当前左孩子
print $this->getNodeByIndex($currentIndex)["value"]." ";
if($this->rightChild($currentIndex) !== false){//当前节点有右孩子
$lastIndex = $currentIndex;
$currentIndex = $currentIndex*2+2;
$currentAction = 'down';
}else {
$lastIndex = $currentIndex;
$currentIndex = intval(($currentIndex-1)/2);
}
}
}
}
}
public function middleOrder(){
$queue = [];
if($this->getRoot() === false) return [];
$node = false;
$queue[] = $this->getRoot();
$currentIndex = 0;
while ($node !== false || !empty($queue)){
if(false !== $this->leftChild($currentIndex)){
$node = $this->leftChild($currentIndex);
$queue[] = $node;
$currentIndex = $node["index"];
continue;
}
else{
$n = array_pop($queue);
print $n['value']." ";
//$currentIndex = $n["index"];
$node = $this->rightChild($n["index"]);
if($node !== false) {
$queue[] = $node;
$currentIndex = $node["index"];
}
}
}
}
}
$x = new tree([1,2,3,4,5,6,7,8,9,10]);
$x->setRightChild(9,'a');
$x->setLeftChild(20,'b');
$x->setRightChild(6,'c');
$x->middleOrderWithoutStack();
网友评论