淺談如何輸出二叉樹圖像

蘇慧哲 劉杰

摘要：數據結構內容的高抽象性、強邏輯性和算法復雜性始終是學生學習的一個難點。為便于學生理解算法，將算法結果可視化，即輸出直觀的圖像。以建立并輸出二叉樹的圖像為例介紹如何層次遍歷輸出描述二叉樹的DOT文件，在Graphviz軟件中查看二叉樹圖像結果。

關鍵詞：二叉樹;層次遍歷;結果可視化;dot;graphviz

中圖分類號：G642? ? ? ?文獻標識碼：A? ? ? ? 文章編號：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

在計算機科學與技術中，數據結構介于數學、計算機軟硬件之間，由于其獨特的地位使其成為計算機專業的核心基礎課程。數據結構課程偏重理論，內容抽象，注重理解，同時又要求學生能夠將抽象的思維轉化為在計算機可以操作的具體實踐，因此數據結構是一門理論性和實踐性都很強的課程[1]，其概念多、內容多、高抽象性、強邏輯性和算法復雜性始終是學生學習的一個難點[2]。

在教學過程中發現大部分學生的C語言掌握得不夠扎實，尤其是指針部分，算法沒有理解透徹。如果在教學過程中演示程序能直接輸出直觀的圖形化結果，這樣可以幫助學生調動和激發學生學習的積極性。

在數據結構中，樹是非常重要的非線性結構，二叉樹是一種特殊的樹，遍歷二叉樹是二叉樹的最基本的操作[3]。根據遍歷序列來確定構造唯一的二叉樹，是二叉樹遍歷算法的最基礎的應用。以二叉樹為例，先根據先序遍歷的字符序列建立二叉鏈表，然后輸出二叉樹的圖形。

為方便輸出圖形，只關注遍歷算法，不用思考計算輸出圖形的坐標位置，因此不考慮在命令行中打印二叉樹，而是采用DOT圖形描述語言。DOT是純文本圖像描述語言，文件擴展名通常是.dot，需要有專門的程序處理這些文件并將其渲染成為圖片。Graphviz是貝爾實驗室開發的一個開源的圖像可視化的軟件，它使用dot作為腳本語言，然后使用布局引擎來解析此腳本，并完成自動布局。

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

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

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

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

2 輸出二叉樹

要輸出二叉樹，采用層次遍歷，即需要鏈隊列結構來實現，因此先聲明鏈隊列每個結點的抽象數據類型LKQueNode，包括兩個成員，指向二叉鏈表的結點類型bitree的data指針和指向LKQueNode類型的指針。為方便操作鏈隊列，再聲明鏈隊列的抽象數據類型LKQue，包括兩個指向鏈隊列隊頭隊尾的front和rear指針。代碼如圖4所示。

輸出描述圖像的DOT腳本文件應是可以被Graphviz渲染得到一個二叉樹。根據DOT語法，主函數有2種，graph是無向圖，digraph是有向圖。在無向圖中用—表述結點之間的關系，在有向圖中用—>表述前一個結點指向后一個結點。要繪制的二叉樹結點之間的連線并無箭頭，因此選擇無向圖graph，用—描述結點之間的關系，DOT腳本內容如圖5所示.

程序執行完畢輸出一個文件，需要用到FILE文件類型以及打開文件fopen、關閉文件fclose和寫文件fprintf函數。輸出時采用鏈隊列實現層次遍歷，從而可以從上到下從左到右輸出所有結點，和與該結點有關聯關系的左右孩子結點的關系。代碼如圖6所示。

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

3 主函數

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

4 運行結果

先序遍歷字符序列為AB#D##C##，執行結果如圖13所示。

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

5 改進輸出圖像

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

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

最后用graphviz軟件打開該文件，可以看到渲染得到的二叉樹圖像，D結點是B結點的右孩子，滿足要求。如圖17所示。

為便于學生理解數據結構的算法，將算法結果可視化，輸出直觀的圖像。以構建二叉樹輸出二叉樹的圖像為例，無須思考在命令行中輸出圖像的坐標位置，層次遍歷輸出描述二叉樹的DOT文件，在Graphviz軟件中查看二叉樹圖像結果。

參考文獻：

[1] 劉中華，王琳.數據結構教學改革與探索[J].科教文匯（下旬刊），2018（7）.

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

[3] 嚴蔚敏，李冬梅，吳偉民.數據結構（C語言）：第二版[M].北京：人民郵電出版社，2015.

[通聯編輯：王力]