最近老師布置了一個作業(yè)：理解并實現(xiàn)平衡二叉樹和紅黑樹，本來老師是說用C#寫的，但是我學的C#基本都還給老師了，怎么辦？那就用現(xiàn)在最熟悉的語言PHP來寫吧！
有一個問題來了，書上在講解樹的時候基本上會給出形象的樹形圖。但是當我們自己試著實現(xiàn)某種樹，在調(diào)試、輸出的時候確只能以字符的形式順序地輸出。這給調(diào)試等方面帶來了很大的不便。然后在各種百度之后，我發(fā)現(xiàn)利用PHP實現(xiàn)二叉樹的圖形顯示的資源幾乎是零！好吧，那我就自己個兒實現(xiàn)一個！
?php
/**
* author:LSGOZJ
* description: 繪制二叉樹圖像
*/
class image
{
//樹相關設置
//每層之間的間隔高度
private $level_high = 100;
//最底層葉子結(jié)點之間的寬度
private $leaf_width = 50;
//結(jié)點圓的半徑
private $rad = 20;
//根節(jié)點離邊框頂端距離
private $leave = 20;
//樹（保存樹對象的引用）
private $tree;
//樹的層數(shù)
private $level;
//完全二叉樹中最底層葉子結(jié)點數(shù)量（計算圖像寬度時用到，論如何實現(xiàn)圖片大小自適應）
private $maxCount;
//圖像相關設置
//畫布寬度
private $width;
//畫布高度
private $height;
//畫布背景顏色（RGB）
private $bg = array(
220, 220, 220
);
//節(jié)點顏色（搜索二叉樹和平衡二叉樹時用）
private $nodeColor = array(
255, 192, 203
);
//圖像句柄
private $image;
/**
* 構(gòu)造函數(shù)，類屬性初始化
* @param $tree 傳遞一個樹的對象
* @return null
*/
public function __construct($tree)
{
$this->tree = $tree;
$this->level = $this->getLevel();
$this->maxCount = $this->GetMaxCount($this->level);
$this->width = ($this->rad * 2 * $this->maxCount) + $this->maxCount * $this->leaf_width;
$this->height = $this->level * ($this->rad * 2) + $this->level_high * ($this->level - 1) + $this->leave;
//1.創(chuàng)建畫布
$this->image = imagecreatetruecolor($this->width, $this->height); //新建一個真彩色圖像，默認背景是黑色
//填充背景色
$bgcolor = imagecolorallocate($this->image, $this->bg[0], $this->bg[1], $this->bg[2]);
imagefill($this->image, 0, 0, $bgcolor);
}
/**
* 返回傳進來的樹對象對應的完全二叉樹中最底層葉子結(jié)點數(shù)量
* @param $level 樹的層數(shù)
* @return 結(jié)點數(shù)量
*/
function GetMaxCount($level)
{
return pow(2, $level - 1);
}
/**
* 獲取樹對象的層數(shù)
* @param null
* @return 樹的層數(shù)
*/
function getLevel()
{
return $this->tree->Depth();
}
/**
* 顯示二叉樹圖像
* @param null
* @return null
*/
public function show()
{
$this->draw($this->tree->root, 1, 0, 0);
header("Content-type:image/png");
imagepng($this->image);
imagedestroy($this->image);
}
/**
* （遞歸）畫出二叉樹的樹狀結(jié)構(gòu)
* @param $root，根節(jié)點（樹或子樹） $i，該根節(jié)點所處的層 $p_x，父節(jié)點的x坐標 $p_y,父節(jié)點的y坐標
* @return null
*/
private function draw($root, $i, $p_x, $p_y)
{
if ($i = $this->level) {
//當前節(jié)點的y坐標
$root_y = $i * $this->rad + ($i - 1) * $this->level_high;
//當前節(jié)點的x坐標
if (!is_null($parent = $root->parent)) {
if ($root == $parent->left) {
$root_x = $p_x - $this->width / (pow(2, $i));
} else {
$root_x = $p_x + $this->width / (pow(2, $i));
}
} else {
//根節(jié)點
$root_x = (1 / 2) * $this->width;
$root_y += $this->leave;
}
//畫結(jié)點（確定所畫節(jié)點的類型（平衡、紅黑、排序）和方法）
$method = 'draw' . get_class($this->tree) . 'Node';
$this->$method($root_x, $root_y, $root);
//將當前節(jié)點和父節(jié)點連線（黑色線）
$black = imagecolorallocate($this->image, 0, 0, 0);
if (!is_null($parent = $root->parent)) {
imageline($this->image, $p_x, $p_y, $root_x, $root_y, $black);
}
//畫左子節(jié)點
if (!is_null($root->left)) {
$this->draw($root->left, $i + 1, $root_x, $root_y);
}
//畫右子節(jié)點
if (!is_null($root->right)) {
$this->draw($root->right, $i + 1, $root_x, $root_y);
}
}
}
/**
* 畫搜索二叉樹結(jié)點
* @param $x，當前節(jié)點的x坐標 $y，當前節(jié)點的y坐標 $node，當前節(jié)點的引用
* @return null
*/
private function drawBstNode($x, $y, $node)
{
//節(jié)點圓的線顏色
$black = imagecolorallocate($this->image, 0, 0, 0);
$nodeColor = imagecolorallocate($this->image, $this->nodeColor[0], $this->nodeColor[1], $this->nodeColor[2]);
//畫節(jié)點圓
imageellipse($this->image, $x, $y, $this->rad * 2, $this->rad * 2, $black);
//節(jié)點圓顏色填充
imagefill($this->image, $x, $y, $nodeColor);
//節(jié)點對應的數(shù)字
imagestring($this->image, 4, $x, $y, $node->key, $black);
}
/**
* 畫平衡二叉樹結(jié)點
* @param $x，當前節(jié)點的x坐標 $y，當前節(jié)點的y坐標 $node，當前節(jié)點的引用
* @return null
*/
private function drawAvlNode($x, $y, $node)
{
$black = imagecolorallocate($this->image, 0, 0, 0);
$nodeColor = imagecolorallocate($this->image, $this->nodeColor[0], $this->nodeColor[1], $this->nodeColor[2]);
imageellipse($this->image, $x, $y, $this->rad * 2, $this->rad * 2, $black);
imagefill($this->image, $x, $y, $nodeColor);
imagestring($this->image, 4, $x, $y, $node->key . '(' . $node->bf . ')', $black);
}
/**
* 畫紅黑樹結(jié)點
* @param $x，當前節(jié)點的x坐標 $y，當前節(jié)點的y坐標 $node，當前節(jié)點的引用
* @return null
*/
private function drawRbtNode($x, $y, $node)
{
$black = imagecolorallocate($this->image, 0, 0, 0);
$gray = imagecolorallocate($this->image, 180, 180, 180);
$pink = imagecolorallocate($this->image, 255, 192, 203);
imageellipse($this->image, $x, $y, $this->rad * 2, $this->rad * 2, $black);
if ($node->IsRed == TRUE) {
imagefill($this->image, $x, $y, $pink);
} else {
imagefill($this->image, $x, $y, $gray);
}
imagestring($this->image, 4, $x, $y, $node->key, $black);
}
}
更多關于PHP相關內(nèi)容感興趣的讀者可查看本站專題：《PHP數(shù)據(jù)結(jié)構(gòu)與算法教程》、《php程序設計算法總結(jié)》、《php字符串(string)用法總結(jié)》、《PHP數(shù)組(Array)操作技巧大全》、《PHP常用遍歷算法與技巧總結(jié)》及《PHP數(shù)學運算技巧總結(jié)》
