二叉樹(shù)結(jié)構(gòu)的文本模式顯示

江順亮 任燕

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

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

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

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

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

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

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

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

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

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

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

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