淺談如何輸出二叉樹(shù)圖像

蘇慧哲 劉杰

摘要：數(shù)據(jù)結(jié)構(gòu)內(nèi)容的高抽象性、強(qiáng)邏輯性和算法復(fù)雜性始終是學(xué)生學(xué)習(xí)的一個(gè)難點(diǎn)。為便于學(xué)生理解算法，將算法結(jié)果可視化，即輸出直觀的圖像。以建立并輸出二叉樹(shù)的圖像為例介紹如何層次遍歷輸出描述二叉樹(shù)的DOT文件，在Graphviz軟件中查看二叉樹(shù)圖像結(jié)果。

關(guān)鍵詞：二叉樹(shù);層次遍歷;結(jié)果可視化;dot;graphviz

中圖分類號(hào)：G642? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A? ? ? ? 文章編號(hào)：1009-3044（2018）36-0247-03

Abstract： High abstraction， strong logic and complex algorithm of data structure are always difficult for students to learn. In order to facilitate students to understand the algorithm， the algorithm results are visualized， that is， the output of intuitive images.Taking the image of building and outputting binary tree as an example， this paper introduces how to output the DOT file of describing binary tree hierarchically and view the result of binary tree image in Graphviz software.

Key words： binary tree; hierarchy traversal; result visualization; dot; graphviz

在計(jì)算機(jī)科學(xué)與技術(shù)中，數(shù)據(jù)結(jié)構(gòu)介于數(shù)學(xué)、計(jì)算機(jī)軟硬件之間，由于其獨(dú)特的地位使其成為計(jì)算機(jī)專業(yè)的核心基礎(chǔ)課程。數(shù)據(jù)結(jié)構(gòu)課程偏重理論，內(nèi)容抽象，注重理解，同時(shí)又要求學(xué)生能夠?qū)⒊橄蟮乃季S轉(zhuǎn)化為在計(jì)算機(jī)可以操作的具體實(shí)踐，因此數(shù)據(jù)結(jié)構(gòu)是一門(mén)理論性和實(shí)踐性都很強(qiáng)的課程[1]，其概念多、內(nèi)容多、高抽象性、強(qiáng)邏輯性和算法復(fù)雜性始終是學(xué)生學(xué)習(xí)的一個(gè)難點(diǎn)[2]。

在教學(xué)過(guò)程中發(fā)現(xiàn)大部分學(xué)生的C語(yǔ)言掌握得不夠扎實(shí)，尤其是指針部分，算法沒(méi)有理解透徹。如果在教學(xué)過(guò)程中演示程序能直接輸出直觀的圖形化結(jié)果，這樣可以幫助學(xué)生調(diào)動(dòng)和激發(fā)學(xué)生學(xué)習(xí)的積極性。

在數(shù)據(jù)結(jié)構(gòu)中，樹(shù)是非常重要的非線性結(jié)構(gòu)，二叉樹(shù)是一種特殊的樹(shù)，遍歷二叉樹(shù)是二叉樹(shù)的最基本的操作[3]。根據(jù)遍歷序列來(lái)確定構(gòu)造唯一的二叉樹(shù)，是二叉樹(shù)遍歷算法的最基礎(chǔ)的應(yīng)用。以二叉樹(shù)為例，先根據(jù)先序遍歷的字符序列建立二叉鏈表，然后輸出二叉樹(shù)的圖形。

為方便輸出圖形，只關(guān)注遍歷算法，不用思考計(jì)算輸出圖形的坐標(biāo)位置，因此不考慮在命令行中打印二叉樹(shù)，而是采用DOT圖形描述語(yǔ)言。DOT是純文本圖像描述語(yǔ)言，文件擴(kuò)展名通常是.dot，需要有專門(mén)的程序處理這些文件并將其渲染成為圖片。Graphviz是貝爾實(shí)驗(yàn)室開(kāi)發(fā)的一個(gè)開(kāi)源的圖像可視化的軟件，它使用dot作為腳本語(yǔ)言，然后使用布局引擎來(lái)解析此腳本，并完成自動(dòng)布局。

因此根據(jù)先序遍歷，建立唯一二叉樹(shù)，然后層次遍歷輸出描述二叉樹(shù)的DOT腳本文件，接下來(lái)用Graphviz圖像可視化軟件打開(kāi)輸出的DOT腳本文件，渲染即可得到二叉樹(shù)圖像。

1 根據(jù)先序遍歷的字符序列建立二叉鏈表

首先聲明二叉鏈表每個(gè)結(jié)點(diǎn)的抽象數(shù)據(jù)類型bitree，包括三個(gè)成員，一個(gè)數(shù)據(jù)data和左右兩個(gè)指針lchild，rchild，還有指向該結(jié)點(diǎn)類型的指針Bitree。代碼如圖1所示。

然后根據(jù)給定的先序遍歷得到的字符序列如AB#D##C##，一個(gè)一個(gè)掃描，遞歸建立二叉鏈表。構(gòu)造的二叉鏈表如圖2所示，代碼如圖3所示。

2 輸出二叉樹(shù)

要輸出二叉樹(shù)，采用層次遍歷，即需要鏈隊(duì)列結(jié)構(gòu)來(lái)實(shí)現(xiàn)，因此先聲明鏈隊(duì)列每個(gè)結(jié)點(diǎn)的抽象數(shù)據(jù)類型LKQueNode，包括兩個(gè)成員，指向二叉鏈表的結(jié)點(diǎn)類型bitree的data指針和指向LKQueNode類型的指針。為方便操作鏈隊(duì)列，再聲明鏈隊(duì)列的抽象數(shù)據(jù)類型LKQue，包括兩個(gè)指向鏈隊(duì)列隊(duì)頭隊(duì)尾的front和rear指針。代碼如圖4所示。

輸出描述圖像的DOT腳本文件應(yīng)是可以被Graphviz渲染得到一個(gè)二叉樹(shù)。根據(jù)DOT語(yǔ)法，主函數(shù)有2種，graph是無(wú)向圖，digraph是有向圖。在無(wú)向圖中用—表述結(jié)點(diǎn)之間的關(guān)系，在有向圖中用—>表述前一個(gè)結(jié)點(diǎn)指向后一個(gè)結(jié)點(diǎn)。要繪制的二叉樹(shù)結(jié)點(diǎn)之間的連線并無(wú)箭頭，因此選擇無(wú)向圖graph，用—描述結(jié)點(diǎn)之間的關(guān)系，DOT腳本內(nèi)容如圖5所示.

程序執(zhí)行完畢輸出一個(gè)文件，需要用到FILE文件類型以及打開(kāi)文件fopen、關(guān)閉文件fclose和寫(xiě)文件fprintf函數(shù)。輸出時(shí)采用鏈隊(duì)列實(shí)現(xiàn)層次遍歷，從而可以從上到下從左到右輸出所有結(jié)點(diǎn)，和與該結(jié)點(diǎn)有關(guān)聯(lián)關(guān)系的左右孩子結(jié)點(diǎn)的關(guān)系。代碼如圖6所示。

其中InitQueue（）、EmptyQueue（）、EnQueue（）、OutQueue（）和GetHead（）分別是隊(duì)列的初始化、判斷隊(duì)列是否為空、入隊(duì)、出隊(duì)、取隊(duì)首元素的隊(duì)列基本操作。具體代碼分別如圖7，圖8，圖9，圖10，圖11所示。

3 主函數(shù)

先定義一個(gè)二叉鏈表Bitree變量T，然后在命令行中提示用戶輸入先序遍歷得到的字符序列，用‘#代表空，接著根據(jù)用戶輸入的結(jié)點(diǎn)序列構(gòu)造二叉鏈表，最后層次遍歷輸出tree.dot文件。代碼如圖12所示。

4 運(yùn)行結(jié)果

先序遍歷字符序列為AB#D##C##，執(zhí)行結(jié)果如圖13所示。

程序執(zhí)行完后，在與該源程序相同路徑下找到生成的tree.dot文件。然后用graphviz軟件打開(kāi)該文件，可以看到渲染得到的二叉樹(shù)圖像。代碼如圖14所示。

5 改進(jìn)輸出圖像

但是二叉樹(shù)嚴(yán)格區(qū)分左右子樹(shù)，D結(jié)點(diǎn)從這張圖中看不出是B結(jié)點(diǎn)的左孩子還是右孩子，因此采用隱藏結(jié)點(diǎn)的方法可以使得D結(jié)點(diǎn)顯示為B結(jié)點(diǎn)的右孩子。修改輸出函數(shù)PrintTree（）。層次遍歷到某結(jié)點(diǎn)時(shí)，如果該結(jié)點(diǎn)的左孩子不為空，且右孩子為空，則也要輸出該結(jié)點(diǎn)的右孩子和邊，因?yàn)閷?shí)際上并沒(méi)有右孩子所以就用該結(jié)點(diǎn)加r來(lái)表示該結(jié)點(diǎn)的右孩子，然后隱藏右孩子結(jié)點(diǎn)和邊;同理，如果該結(jié)點(diǎn)的右孩子不為空，且左孩子為空，則也要輸出該結(jié)點(diǎn)的左孩子和邊，而該結(jié)點(diǎn)實(shí)際并不存在的左孩子就加l來(lái)表示，然后隱藏左孩子結(jié)點(diǎn)和邊。隱藏結(jié)點(diǎn)和邊均用[style=invis]實(shí)現(xiàn)。最后注意輸出順序永遠(yuǎn)是左孩子在前，右孩子在后。代碼如圖15所示。

先序遍歷字符序列依然是AB#D##C##，程序執(zhí)行完后，在與該源程序相同路徑下找到生成的tree.dot文件，文件內(nèi)容如圖16所示。

最后用graphviz軟件打開(kāi)該文件，可以看到渲染得到的二叉樹(shù)圖像，D結(jié)點(diǎn)是B結(jié)點(diǎn)的右孩子，滿足要求。如圖17所示。

為便于學(xué)生理解數(shù)據(jù)結(jié)構(gòu)的算法，將算法結(jié)果可視化，輸出直觀的圖像。以構(gòu)建二叉樹(shù)輸出二叉樹(shù)的圖像為例，無(wú)須思考在命令行中輸出圖像的坐標(biāo)位置，層次遍歷輸出描述二叉樹(shù)的DOT文件，在Graphviz軟件中查看二叉樹(shù)圖像結(jié)果。

參考文獻(xiàn)：

[1] 劉中華，王琳.數(shù)據(jù)結(jié)構(gòu)教學(xué)改革與探索[J].科教文匯（下旬刊），2018（7）.

[2] 元昌安，彭昱忠，覃曉，陸建波.地方高校雙創(chuàng)型IT專業(yè)人才培養(yǎng)模式的研究與實(shí)踐[M].北京：北京理工大學(xué)出版社，2016.

[3] 嚴(yán)蔚敏，李冬梅，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言）：第二版[M].北京：人民郵電出版社，2015.

[通聯(lián)編輯：王力]