江順亮 任燕

摘要：二叉樹在數(shù)據(jù)結(jié)構(gòu)的教學(xué)中是非常重要的一類非線性結(jié)構(gòu)，在上機(jī)編程和調(diào)試的過程中如何快速有效直觀地顯示這類非線性結(jié)構(gòu)直接影響著教與學(xué)的效率，為此提出了一種文本模式的二叉樹結(jié)構(gòu)顯示方法；該方法利用_、/和三種特殊字符把子結(jié)點(diǎn)和父結(jié)點(diǎn)連接起來，使用隊(duì)列對二叉樹進(jìn)行層序輸出。在隊(duì)列中采用空指針NULL代表空結(jié)點(diǎn)，同時(shí)用一個(gè)新結(jié)點(diǎn)end表示每一層的結(jié)束。該方法不僅適用于順序存儲的二叉樹也適用于鏈?zhǔn)酱鎯Φ亩鏄?，進(jìn)行適當(dāng)修改也可順利地顯示3階B_樹，因此可以作為數(shù)據(jù)結(jié)構(gòu)教與學(xué)的有效手段之一。

關(guān)鍵詞：二叉樹；顯示；文本模式

中圖分類號：TP311文獻(xiàn)標(biāo)識碼：A文章編號：1009-3044(2012)16-3856-05

Text-mode Display of Binary Tree

JIANG Shun-liang, REN Yang

(Department of Computer Science and Technology, School of Information Engineering, Nanchang University, Nanchang 330031, China) Abstract: Binary tree is very important nonlinear structure in the data structures, how to display the binary tree effectively is essential to the related teaching and learning. A text-mode display method for binary tree was proposed, three characters (‘_,‘/and‘) were used to connect the parent and children nodes, queue technique was used to export binary tree by level-order, the empty node is represented by the NULL pointer and one new node is created to denote the end of one level in the level-order queue. The method is usable for both of sequence and linked binary trees, is applicable for display of 3-order B_tree by small modification, and is valuable to improve the teaching and learning.

Key words: Binary tree; display; Text-mode

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科的16門核心課程之一[1]，它對培養(yǎng)學(xué)生的兩項(xiàng)專業(yè)能力：算法設(shè)計(jì)與分析的能力、程序設(shè)計(jì)能力[1]是非常重要的。數(shù)據(jù)結(jié)構(gòu)也是全國碩士研究生入學(xué)統(tǒng)一考試計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科綜合專業(yè)的重要部分，其分?jǐn)?shù)占總分的近三分之一。二叉樹是數(shù)據(jù)結(jié)構(gòu)中非?；A(chǔ)的非線性結(jié)構(gòu)，對學(xué)好其它非線性結(jié)構(gòu)具有重要的作用。非線性結(jié)構(gòu)的算法與程序設(shè)計(jì)對于初學(xué)者來說是比較抽象的，即使象二叉樹這樣簡單與基礎(chǔ)的非線性結(jié)構(gòu)，要掌握它也不是一件容易的事；學(xué)好它離不開動腦與動手，上機(jī)編程和調(diào)試相關(guān)算法非常重要，但是學(xué)生不易直觀檢查計(jì)算結(jié)果，這會影響調(diào)試的效率。

檢查二叉樹結(jié)果可以通過輸出二叉樹的遍歷結(jié)果來進(jìn)行，尤其是層序遍歷[2]；也可以在集成開發(fā)環(huán)境中通過監(jiān)視(Watch)追蹤左右子樹，這不直觀也非常繁瑣。圖形顯示二叉樹是比較直觀和形象的[3]，因此在教學(xué)中可以采用圖形顯示[4-5]，比如圖1；但是它的缺點(diǎn)也很明顯，要求學(xué)生掌握一定的圖形編程，而不少學(xué)生在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的時(shí)候圖形編程基礎(chǔ)比較弱，因此教與學(xué)往往是在命令行的方式下進(jìn)行輸出，即通過printf或cout進(jìn)行輸出（C/C++語言），所以采用圖形輸出進(jìn)行數(shù)據(jù)結(jié)構(gòu)教學(xué)有一定的局限性。

采用該文方法把搜索的結(jié)果用特定字符*標(biāo)識出來如圖6。哈夫曼樹是一種最優(yōu)二叉樹，帶權(quán)的初始結(jié)點(diǎn)都在葉子上，構(gòu)造過程中新建的結(jié)點(diǎn)都是分支結(jié)點(diǎn)；哈夫曼樹可以采用順序存儲[6]，該文方法略作修改即可應(yīng)用于順序存儲，用特殊字符@標(biāo)識分支結(jié)點(diǎn)顯示的哈夫曼樹如圖7。平衡二叉樹是一種優(yōu)化后的二叉排序樹，它的左右子樹的高度不超過1，每個(gè)結(jié)點(diǎn)有一個(gè)平衡因子表示左右子樹的平衡情況，可以用更為直觀的符號表示平衡因子，即>代表1、=代表0和<代表-1，顯示時(shí)把數(shù)據(jù)域后面的空格減少一個(gè)，用于輸出平衡因子的代表符號，顯示結(jié)果如圖8。B_樹是一種多路平衡查找樹，可用于外部文件的動態(tài)查找，B_樹的插入與刪除算法比較復(fù)雜，非常適合學(xué)生的編程技能訓(xùn)練，在調(diào)試過程中如何快速有效地檢查結(jié)果比較麻煩，采用該文的方法經(jīng)適當(dāng)?shù)匦薷目梢苑奖愕仫@示3階B_樹。為了顯示3階B_樹，增加一個(gè)符號|指向中間的子樹，最重要的修改是顯示起始位置的計(jì)算，另外用字符~替代了字符_，此時(shí)第一行連接符包括/、|和，第二行包括~、/、|和四種字符，這樣顯示的效果也非常好，如圖9。

二叉樹結(jié)構(gòu)的文本模式顯示方法使用了_、/和三種字符來顯示二叉樹的結(jié)構(gòu)，由于不涉及圖形操作，該方法有很強(qiáng)的可移植性，不論TC環(huán)境或者VS環(huán)境，該文提供的代碼都可直接使用。該文的方法也可方便地改為獨(dú)立的函數(shù)，也方便其它的語言實(shí)現(xiàn)。該方法方便了樹型數(shù)據(jù)結(jié)構(gòu)程序的調(diào)試，不僅可以應(yīng)用于各種二叉樹，也可應(yīng)用于三叉樹，比如3階B_樹。由于直觀地顯示了二叉樹的結(jié)構(gòu)，因而可以提高教與學(xué)的效率。同時(shí)，算法也使用了隊(duì)列，對學(xué)生鞏固已學(xué)過的數(shù)據(jù)結(jié)構(gòu)知識非常有幫助。

[1]中國計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科教程2002研究組.中國計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科教程2002[M].北京:清華大學(xué)出版社,2002.

[2]葉品菊,吳斌,胡遠(yuǎn)望,等.直觀顯示二叉樹結(jié)構(gòu)的算法[J].江南大學(xué)學(xué)報(bào):自然科學(xué)版,2008,7(1):60-63.

[3]劉福君,李華,王玉森,等.基于二叉樹的故障樹畫樹算法研究[J].計(jì)算機(jī)技術(shù)與發(fā)展, 2006,16(7):117-118.

[4]劉惠敏,董毅.動態(tài)模擬二叉樹的建立[J].黃岡職業(yè)技術(shù)學(xué)院學(xué)報(bào),2004,6(1):75-76.

[5]白雪峰,李沛.二叉排序樹的建立及對其中序遍歷的動態(tài)模擬[J].電腦知識與技術(shù),2005,12(8):84-86.

[6]任燕.數(shù)據(jù)結(jié)構(gòu)C++語言描述[M].北京:清華大學(xué)出版社,2010.