本文實例講述了PHP實現(xiàn)繪制二叉樹圖形顯示功能。分享給大家供大家參考,具體如下:
前言:
最近老師布置了一個作業(yè):理解并實現(xiàn)平衡二叉樹和紅黑樹,本來老師是說用C#寫的,但是我學(xué)的C#基本都還給老師了,怎么辦?那就用現(xiàn)在最熟悉的語言PHP來寫吧!
有一個問題來了,書上在講解樹的時候基本上會給出形象的樹形圖。但是當(dāng)我們自己試著實現(xiàn)某種樹,在調(diào)試、輸出的時候確只能以字符的形式順序地輸出。這給調(diào)試等方面帶來了很大的不便。然后在各種百度之后,我發(fā)現(xiàn)利用PHP實現(xiàn)二叉樹的圖形顯示的資源幾乎是零!好吧,那我就自己個兒實現(xiàn)一個!
效果顯示:
如果我是直接在這一步擺代碼的話,估計大家會比較煩悶,那我就直接上結(jié)果吧,后面在補(bǔ)代碼,先激發(fā)激發(fā)大家的閱讀興趣:
1、搜索二叉樹:
2、平衡二叉樹:
3、紅黑樹:
上代碼:
我們給圖片創(chuàng)建一個類吧,顯得稍微的小高級:
image.php 文件:
<?php /** * author:LSGOZJ * description: 繪制二叉樹圖像 */ class image { //樹相關(guān)設(shè)置 //每層之間的間隔高度 private $level_high = 100; //最底層葉子結(jié)點(diǎn)之間的寬度 private $leaf_width = 50; //結(jié)點(diǎn)圓的半徑 private $rad = 20; //根節(jié)點(diǎn)離邊框頂端距離 private $leave = 20; //樹(保存樹對象的引用) private $tree; //樹的層數(shù) private $level; //完全二叉樹中最底層葉子結(jié)點(diǎn)數(shù)量(計算圖像寬度時用到,論如何實現(xiàn)圖片大小自適應(yīng)) private $maxCount; //圖像相關(guān)設(shè)置 //畫布寬度 private $width; //畫布高度 private $height; //畫布背景顏色(RGB) private $bg = array( 220, 220, 220 ); //節(jié)點(diǎn)顏色(搜索二叉樹和平衡二叉樹時用) 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); //新建一個真彩色圖像,默認(rèn)背景是黑色 //填充背景色 $bgcolor = imagecolorallocate($this->image, $this->bg[0], $this->bg[1], $this->bg[2]); imagefill($this->image, 0, 0, $bgcolor); } /** * 返回傳進(jìn)來的樹對象對應(yīng)的完全二叉樹中最底層葉子結(jié)點(diǎn)數(shù)量 * @param $level 樹的層數(shù) * @return 結(jié)點(diǎn)數(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é)點(diǎn)(樹或子樹) $i,該根節(jié)點(diǎn)所處的層 $p_x,父節(jié)點(diǎn)的x坐標(biāo) $p_y,父節(jié)點(diǎn)的y坐標(biāo) * @return null */ private function draw($root, $i, $p_x, $p_y) { if ($i <= $this->level) { //當(dāng)前節(jié)點(diǎn)的y坐標(biāo) $root_y = $i * $this->rad + ($i - 1) * $this->level_high; //當(dāng)前節(jié)點(diǎn)的x坐標(biāo) 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é)點(diǎn) $root_x = (1 / 2) * $this->width; $root_y += $this->leave; } //畫結(jié)點(diǎn)(確定所畫節(jié)點(diǎn)的類型(平衡、紅黑、排序)和方法) $method = 'draw' . get_class($this->tree) . 'Node'; $this->$method($root_x, $root_y, $root); //將當(dāng)前節(jié)點(diǎn)和父節(jié)點(diǎn)連線(黑色線) $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é)點(diǎn) if (!is_null($root->left)) { $this->draw($root->left, $i + 1, $root_x, $root_y); } //畫右子節(jié)點(diǎn) if (!is_null($root->right)) { $this->draw($root->right, $i + 1, $root_x, $root_y); } } } /** * 畫搜索二叉樹結(jié)點(diǎn) * @param $x,當(dāng)前節(jié)點(diǎn)的x坐標(biāo) $y,當(dāng)前節(jié)點(diǎn)的y坐標(biāo) $node,當(dāng)前節(jié)點(diǎn)的引用 * @return null */ private function drawBstNode($x, $y, $node) { //節(jié)點(diǎn)圓的線顏色 $black = imagecolorallocate($this->image, 0, 0, 0); $nodeColor = imagecolorallocate($this->image, $this->nodeColor[0], $this->nodeColor[1], $this->nodeColor[2]); //畫節(jié)點(diǎn)圓 imageellipse($this->image, $x, $y, $this->rad * 2, $this->rad * 2, $black); //節(jié)點(diǎn)圓顏色填充 imagefill($this->image, $x, $y, $nodeColor); //節(jié)點(diǎn)對應(yīng)的數(shù)字 imagestring($this->image, 4, $x, $y, $node->key, $black); } /** * 畫平衡二叉樹結(jié)點(diǎn) * @param $x,當(dāng)前節(jié)點(diǎn)的x坐標(biāo) $y,當(dāng)前節(jié)點(diǎn)的y坐標(biāo) $node,當(dāng)前節(jié)點(diǎn)的引用 * @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é)點(diǎn) * @param $x,當(dāng)前節(jié)點(diǎn)的x坐標(biāo) $y,當(dāng)前節(jié)點(diǎn)的y坐標(biāo) $node,當(dāng)前節(jié)點(diǎn)的引用 * @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); } }
好,現(xiàn)在我們來看看在客戶端如何調(diào)用:
【網(wǎng)站聲明】本站除付費(fèi)源碼經(jīng)過測試外,其他素材未做測試,不保證完整性,網(wǎng)站上部分源碼僅限學(xué)習(xí)交流,請勿用于商業(yè)用途。如損害你的權(quán)益請聯(lián)系客服QQ:2655101040 給予處理,謝謝支持。