二叉樹是數(shù)據(jù)結構中不可忽略的部分酝蜒，但是相關的書籍上很少有用php來實現(xiàn)二叉樹的匕荸，下面是我用php參考C++實現(xiàn)二叉樹的代碼
一森逮、二叉樹的數(shù)組實現(xiàn)方式
<?php
/**
* 二叉樹數(shù)組表示
*/
class BinaryTree {
private $size, $array = array();
//創(chuàng)建樹并初始化節(jié)點
function __construct($size, $root) {
$this->size = $size;
for ($i = 0; $i < $size; $i++) {
$this->array[$i] = 0;
}
$this->array[0] = $root;
}
//查詢節(jié)點
function searchNode($nodeCode) {
if ($nodeCode >= $this->size || $nodeCode < 0) {
return false;
} else {
if ($this->array[$nodeCode] == 0) {
return null;
} else {
return $this->array[$nodeCode];
}
}
}
//增加樹節(jié)點
function addNode($nodeCode, $place, $nodeValue) {
if ($nodeCode >= $this->size || $nodeCode < 0) {
return false;
} else {
//判斷插入節(jié)點是左孩子還是右孩子
if ($place == 0) {
//判斷該位置是否為空谜喊，為空進行插入操作
if ($this->array[$nodeCode * 2 + 1] == 0) {
//判斷該節(jié)點是否是新的葉子節(jié)點，如果是枢赔，則對相應位置進行補0操作
if ($nodeCode * 2 + 1 >= $this->size) {
for ($i = $this->size; $i < $nodeCode * 2 + 1; $i++) {
$this->array[$i] = 0;
}
$this->size = $nodeCode * 2 + 2;
$this->array[$nodeCode * 2 + 1] = $nodeValue;
} else {
$this->array[$nodeCode * 2 + 1] = $nodeValue;
}
} else {
return false;
}
} elseif ($place == 1) {
if ($this->array[$nodeCode * 2 + 2] == 0) {
//判斷該節(jié)點是否是新的葉子節(jié)點，如果是拥知，則對相應位置進行補0操作
if ($nodeCode * 2 + 2 >= $this->size) {
for ($i = $this->size; $i < $nodeCode * 2 + 1; $i++) {
$this->array[$i] = 0;
}
$this->size = $nodeCode * 2 + 3;
$this->array[$nodeCode * 2 + 2] = $nodeValue;
} else {
$this->array[$nodeCode * 2 + 2] = $nodeValue;
}
} else {
return false;
}
}
}
}
//刪除樹節(jié)點
function deleteNode($nodeCode) {
if ($nodeCode >= $this->size || $nodeCode < 0) {
return false;
} else {
$this->array[$nodeCode] = 0;
}
}
//遍歷樹
function showTree() {
var_dump($this->array);
}
//銷毀樹
function __destruct() {
unset($this->array);
}
}
這種實現(xiàn)方式主要是將二叉樹中的節(jié)點存儲在數(shù)組中踏拜，通過數(shù)組下標索引進而對二叉樹的相關節(jié)點進行操作
二、二叉樹的鏈表實現(xiàn)方式
<?php
error_reporting(E_ALL ^ E_NOTICE);
/**
* 二叉樹的節(jié)點類
*/
class Node {
//索引 值 左孩子 右孩子 父節(jié)點
public $index, $data, $lChild, $rChild, $parentNode;
function __construct($index, $data, Node $parentNode = null, Node $lChild = null, Node $rChild = null) {
//構造函數(shù) 用來初始化節(jié)點
$this->index = $index;
$this->data = $data;
$this->lChild = $lChild;
$this->rChild = $rChild;
$this->parentNode = $partentNode;
}
function SearchNode($nodeIndex) {
//節(jié)點的搜索方法
if ($this->index == $nodeIndex) {
return $this;
}
if ($this->lChild != null) {
if ($this->lChild->index == $nodeIndex) {
return $this->lChild;
} else {
$tempNode = $this->lChild->SearchNode($nodeIndex);
if ($tempNode != null) {
return $tempNode;
}
}
}
if ($this->rChild != null) {
if ($this->rChild->index == $nodeIndex) {
return $this->rChild;
} else {
$tempNode = $this->rChild->SearchNode($nodeIndex);
if ($tempNode != null) {
return $tempNode;
}
}
}
return null;
}
function DeleatNode() {
//節(jié)點的刪除
if ($this->lChild != null) {
$this->lChild->DeleatNode();
}
if ($this->rChild != null) {
$this->rChild->DeleatNode();
}
if ($this->parentNode != null) {
if ($this->parentNode->lChild == $this) {
$this->parentNode->lChild = null;
} elseif ($this->parentNode->rChild == $this) {
$this->partentNode->rChild = null;
}
}
unset($this);
}
function PreOrderTraversal() {
//節(jié)點的前序遍歷
echo $this->data;
if ($this->lChild != null) {
$this->lChild->PreOrderTraversal();
}
if ($this->rChild != null) {
$this->rChild->PreOrderTraversal();
}
}
function InOrderTraversal() {
//節(jié)點的中序遍歷
if ($this->lChild != null) {
$this->lChild->InOrderTraversal();
}
echo $this->data;
if ($this->rChild != null) {
$this->rChild->InOrderTraversal();
}
}
function PostOrderTraversal() {
//節(jié)點的后序遍歷
if ($this->lChild != null) {
$this->lChild->PostOrderTraversal();
}
if ($this->rChild != null) {
$this->rChild->PostOrderTraversal();
}
echo $this->data;
}
}
class Tree {
private $root;
//構造樹并初始化根節(jié)點
function __construct($index, $data) {
$this->root = new Node($index, $data);
}
//搜索節(jié)點
function SearchNode($nodeIndex) {
return $this->root->SearchNode($nodeIndex);
}
//增加節(jié)點
function AddNode($nodeIndex, $direction, Node $node) {
$searchResult = $this->root->SearchNode($nodeIndex);
if ($searchResult != null) {
if ($direction == 0) {
$searchResult->lChild = $node;
$searchResult->lChild->parentNode = $searchResult;
} elseif ($direction == 1) {
$searchResult->rChild = $node;
$searchResult->rChild->parentNode = $searchResult;
}
} else {
return false;
}
}
//刪除節(jié)點
function DeleatNode($nodeIndex) {
if ($this->SearchNode($nodeIndex) != null) {
$this->SearchNode($nodeIndex)->DeleatNode();
}
}
//前序遍歷
function PreOrderTraversal() {
$this->root->PreOrderTraversal();
}
//中序遍歷
function InOrderTraversal() {
$this->root->InOrderTraversal();
}
//后序遍歷
function PostOrderTraversal() {
$this->root->PostOrderTraversal();
}
//析構函數(shù)
function __destruct() {
unset($this);
}
}
這種實現(xiàn)方式相對于以數(shù)組方式實現(xiàn)二叉樹來說稍微復雜一點低剔，首先速梗，創(chuàng)建一個節(jié)點類，節(jié)點類屬性有索引(index)户侥、數(shù)據(jù)(data)镀琉、左孩子峦嗤、右孩子蕊唐、父節(jié)點，再創(chuàng)建一個二叉樹類烁设，有些在二叉樹類中相對難以實現(xiàn)的方法我們可以放到節(jié)點類中去實現(xiàn)替梨。
