以任意結(jié)點為根的準(zhǔn)二叉樹自動布局算法設(shè)計

姜學(xué)東 孫海民

(河北民族師范學(xué)院 數(shù)學(xué)與計算機科學(xué)學(xué)院，河北 承德 067000）

以任意結(jié)點為根的準(zhǔn)二叉樹自動布局算法設(shè)計

姜學(xué)東 孫海民

(河北民族師范學(xué)院 數(shù)學(xué)與計算機科學(xué)學(xué)院，河北 承德 067000）

在開發(fā)數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)軟件時，用戶提出這樣的需求：任意次以任意結(jié)點為根實現(xiàn)準(zhǔn)二叉樹結(jié)點的自動布局。通過分析發(fā)現(xiàn)，對準(zhǔn)二叉樹進(jìn)行圖的廣度優(yōu)先遍歷算法是解決問題的關(guān)鍵。首先將準(zhǔn)二叉樹看作圖建立鄰接表，然后對其進(jìn)行廣度優(yōu)先遍歷，建立準(zhǔn)二叉樹的三叉鏈表和自動布局鏈表，最后對二叉樹進(jìn)行先根遍歷，根據(jù)三叉鏈表中結(jié)點的父子兄弟關(guān)系，計算自動布局鏈表中的結(jié)點位置，從而實現(xiàn)結(jié)點的自動布局。使用該軟件變了學(xué)生對二叉樹的習(xí)慣性感知，對理解二叉樹的概念和有關(guān)遍歷算法有著極大的促進(jìn)作用。

數(shù)據(jù)結(jié)構(gòu)；算法；二叉樹；自動布局；三叉鏈表

1、引言

《數(shù)據(jù)結(jié)構(gòu)》課程在計算機科學(xué)中占有十分重要的地位[1]。但學(xué)生學(xué)習(xí)該課程時往往感覺很困難。數(shù)據(jù)結(jié)構(gòu)及其算法的教學(xué)難點在于它們的抽象性和動態(tài)性[2]。在學(xué)習(xí)或使用數(shù)據(jù)結(jié)構(gòu)及其程序設(shè)計時學(xué)習(xí)效果差、程序開發(fā)低效等現(xiàn)象普遍存在，造成這種現(xiàn)象的一個很主要的原因在于沒有實現(xiàn)數(shù)據(jù)結(jié)構(gòu)可視化，在程序設(shè)計過程中不能直觀形象地顯現(xiàn)所建立的數(shù)據(jù)結(jié)構(gòu)[3]。為此，人們開發(fā)數(shù)據(jù)結(jié)構(gòu)軟件以幫助學(xué)生對課程中算法的理解。

在開發(fā)二叉樹數(shù)據(jù)算法演示學(xué)習(xí)軟件時，為了幫助學(xué)習(xí)者深入理解二叉樹各種算法，我們沒有在軟件中預(yù)設(shè)二叉樹，而是由學(xué)生使用該軟件自己創(chuàng)建二叉樹，他們可以根據(jù)自己知識經(jīng)驗進(jìn)行數(shù)據(jù)建模，二叉樹結(jié)點的數(shù)量、位置和模型復(fù)雜程度由學(xué)生自己設(shè)定。軟件中對二叉樹的數(shù)據(jù)建模規(guī)則設(shè)計如下：

1.1 鼠標(biāo)雙擊界面創(chuàng)建二叉樹結(jié)點。

1.2 鼠標(biāo)單擊結(jié)點后，拖動鼠標(biāo)到另一個結(jié)點內(nèi)，則創(chuàng)建邊。

1.3 每條邊必須與兩個結(jié)點相連。不存在沒有結(jié)點相連，或者只有一個結(jié)點相連的邊。

1.4 用戶可以創(chuàng)建任意多個結(jié)點，但與每個結(jié)點相連的邊不超過3條，沒有邊與之相連的結(jié)點，稱為游離結(jié)點。

1.5 用戶數(shù)據(jù)建模時不規(guī)定根結(jié)點及結(jié)點的父子關(guān)系，數(shù)據(jù)建模完成后，由用戶指定某個結(jié)點為根結(jié)點，但不指定子結(jié)點的父子兄弟關(guān)系，數(shù)據(jù)建模如圖1所示。

圖1 準(zhǔn)二叉樹

由于二叉樹的結(jié)點數(shù)量、位置和模型復(fù)雜程度由學(xué)生自己設(shè)計，所以數(shù)據(jù)建模結(jié)果可能是二叉樹，也可能不是；同時，模型中沒有確定結(jié)點的父子兄弟關(guān)系，因此稱之為準(zhǔn)二叉樹。

2、需求分析

對于一顆準(zhǔn)二叉樹圖1所示，用戶在進(jìn)行算法演示時如先根遍歷，則需要明確根結(jié)點是哪個結(jié)點，該軟件在數(shù)據(jù)建模完成后，并沒有指定根結(jié)點。二叉樹的根結(jié)點是由學(xué)生任意指定的，A、B、C、D、E都可以指定為根結(jié)點。該軟件之所以這樣設(shè)計的目的之一，是要打破學(xué)習(xí)者的思維定勢，改變他們認(rèn)為根節(jié)點總是在頂端或者底端位置的希望習(xí)慣。目的之二是，通對同一顆準(zhǔn)二叉樹，以不同結(jié)點為根，進(jìn)行算法演示能夠加深學(xué)生對算法的理解，拓展他們的思維空間。因此，我們提出該軟件能夠?qū)σ活w準(zhǔn)二叉樹任意次以任意結(jié)點為根，實現(xiàn)結(jié)點自動布局。為達(dá)到這個目的軟件必須實現(xiàn)如下功能：

2.1 對用戶的數(shù)據(jù)建模結(jié)果進(jìn)行有效性判斷。用戶選定根結(jié)點后，判斷準(zhǔn)二叉樹是否為二叉樹。如果不是二叉樹則提示用戶。

2.2 識別根結(jié)點，判斷結(jié)點的父子兄弟關(guān)系，實現(xiàn)結(jié)點自動布局。不論數(shù)據(jù)建模中結(jié)點的布局如何，該軟件總能夠使得其以規(guī)則的形式分布。根結(jié)點處于最上方；同層的結(jié)點處于同一水平位置；不同層結(jié)點在垂直方向上等間距；子結(jié)點以父結(jié)點的中垂線為軸對稱分布。如圖2所示圖1二叉樹以“A”為根結(jié)點的自動布局。

圖2 以A為根結(jié)點自動布局

2.3 建一個數(shù)據(jù)結(jié)構(gòu)來保存自動布局的二叉樹。數(shù)據(jù)建模后，用戶可以對該模型多次以任意結(jié)點為根，實現(xiàn)結(jié)點自動布局，所以不能修改用原來數(shù)據(jù)建模。如圖3所示圖1二叉樹以“e”為根結(jié)點的自動布局。

圖3 以E為根結(jié)點自動布局

3、算法分析

3.1 建立三叉鏈表

準(zhǔn)二叉樹結(jié)點的自動布局以建立它的三叉鏈表為基礎(chǔ)。根據(jù)規(guī)則，數(shù)據(jù)建模完成后，用戶選擇其中一個結(jié)點作為根，依據(jù)如下條件對準(zhǔn)二叉樹的有效性判斷：

（1）與根相連的邊數(shù)是否小于3？

（2）是否為連通？

（3）是否不存在回路？

如果滿足這三個條件，表明這是一顆二叉樹。先不考慮這三個判斷，首先分析如果一顆準(zhǔn)二叉樹滿足上述條件，怎樣建立三叉鏈表并實現(xiàn)結(jié)點的自動化布局。根據(jù)規(guī)則，以用戶選中的結(jié)點為根，通過根結(jié)點可以找到與之相連的邊，通過邊就可以找到另一端的結(jié)點，這個結(jié)點就是根的孩子，同理可以找到根的另一個孩子(如果有的話)。這樣就得到二叉樹的第二層結(jié)點。同樣的方法找到第三層結(jié)點，第四層結(jié)點……這樣就可以確定結(jié)點間的父子關(guān)系。然后，通過子結(jié)點之間的物理位置來確定子結(jié)點的兄弟關(guān)系（當(dāng)為一個子結(jié)點時，通過父子間物理位置，來確定是左孩子還是右孩子）。這樣就確定了這顆準(zhǔn)二叉樹每個結(jié)點的父子兄弟關(guān)系，也就可以建立它的三叉鏈表。

分析發(fā)現(xiàn)，這種方法實際是按照二叉樹層次遍歷來建立三叉鏈表。那么，使用怎樣的算法對二叉樹進(jìn)行層次遍歷？樹是圖的一種形式，對準(zhǔn)二叉樹的層次遍歷就可以首先把它看作是圖，建立鄰接表。然后對它進(jìn)行圖的廣度優(yōu)先遍歷，這樣就得了到建立三叉鏈表的算法。

進(jìn)一步分析，對準(zhǔn)二叉樹進(jìn)行廣度優(yōu)先遍后，如果還存在沒有被遍歷的結(jié)點，則該準(zhǔn)二叉樹是非連通圖。如果遍歷過程中遇到遍歷過的結(jié)點，那么該結(jié)點應(yīng)該是鄰接表中當(dāng)前頭結(jié)點的父結(jié)點。如果不是，則此準(zhǔn)二叉樹一定存在回路。至于對與根結(jié)點相連的邊不能超過3條的判斷是很容易的。這樣就解決了對數(shù)據(jù)建模有效性的判斷問題。

3.2 結(jié)點自動布局

在既定的條件下，視圖高度和寬度都已確定，二叉樹結(jié)點位置不應(yīng)該超出這個范圍。Windows GDI繪圖時，默認(rèn)映射模式MM_TEXT，其坐標(biāo)原點為窗口左上角，水平軸向右遞增，垂直軸向下遞增[3]。假設(shè)視圖有效畫圖高度為H，寬度為W。對準(zhǔn)二叉樹進(jìn)行廣度優(yōu)先遍歷后，可知該二叉樹的深度N，則結(jié)點的水平位置：

xParent父結(jié)點水平位置，L結(jié)點所處層數(shù)，正負(fù)符號取決于結(jié)點是左/右孩子。當(dāng)為根結(jié)點時，xParent值為W。將視圖高度平均N等分后，得到結(jié)點的垂直位置：

為避免子結(jié)點相互重疊必須設(shè)計結(jié)點的大小。二叉樹最高層結(jié)點數(shù)量為2N-1個，所以結(jié)點最大寬度為W／2N-1，最大高度為H／N。在程序中可預(yù)設(shè)結(jié)點的寬度和高度，當(dāng)預(yù)設(shè)結(jié)點寬度和高度超過實際計算值時，就使用實際值繪制結(jié)點，否則使用預(yù)設(shè)值繪圖。

廣度優(yōu)先遍歷后，根據(jù)二叉樹深度，確定結(jié)點寬度和高度。然后再對該二叉樹進(jìn)行先根遍歷，根據(jù)上面的公式設(shè)置結(jié)點位置，從而實現(xiàn)結(jié)點的自動布局。

3.3 自動布局鏈表

為實現(xiàn)對同一顆準(zhǔn)二叉樹能夠任意次的，以不同結(jié)點為根進(jìn)行自動化布局。必須再設(shè)計出一個用于結(jié)點自動布局的鏈表，并使之與數(shù)據(jù)建中的結(jié)點保持一一的對應(yīng)關(guān)系。為便于在遍歷中查找對應(yīng)的結(jié)點，在建立自動布局鏈表結(jié)點、鄰接表頭結(jié)點和表結(jié)點時，要使它們與數(shù)據(jù)建模中結(jié)點的ID相等。自動布局鏈表的建立過程，如圖3所示。

圖4 自動布局鏈表的建立過程

4、算法實現(xiàn)的設(shè)計

該軟件基于MFC類庫開發(fā)，使用SDI文檔視圖結(jié)構(gòu)作為開發(fā)框架。在程序中設(shè)計數(shù)據(jù)建模和結(jié)點自動布局兩個界面，數(shù)據(jù)建模完成后，學(xué)生選中某個結(jié)點作為根結(jié)點，在右鍵菜單中添加自動布局命令。單該命令后，隱藏數(shù)據(jù)建模界面，顯示結(jié)點自動布局界面。當(dāng)關(guān)閉自動布局界面后，顯示數(shù)據(jù)建模界面，學(xué)生可以選擇另外一個結(jié)點創(chuàng)建二叉樹結(jié)點自動布局。

4.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計

4.1.1 數(shù)據(jù)建模和自動布局鏈表

數(shù)據(jù)建模中結(jié)點和邊都從基類派生；結(jié)點中有一個成員變量保存該結(jié)點的位置信息，有一個管理與此結(jié)點相連的邊的數(shù)組；邊中保存與之相連的兩個結(jié)點；結(jié)點和邊通過一個CObList類對象管理；每個結(jié)點都有唯一的ID。根據(jù)廣度優(yōu)先遍歷的結(jié)點遍歷順序，依次創(chuàng)建自動布局結(jié)點，并使該結(jié)點數(shù)據(jù)與數(shù)據(jù)建模結(jié)點數(shù)據(jù)相同。在對二叉樹進(jìn)行先根遍歷中，根據(jù)結(jié)點的父子兄弟關(guān)系，重新計算結(jié)點的位置。

4.1.2 鄰接表

使用鄰接表作二叉樹的圖的存儲結(jié)構(gòu)，設(shè)計表結(jié)點（CNode）、頭結(jié)點（CHead）和鄰接表（CGraph）三個類。在表結(jié)點和頭結(jié)點類中包含成員m_iID作為結(jié)點的唯一標(biāo)識，在廣度優(yōu)先遍歷中使用該變量，查找相應(yīng)的結(jié)點；包含m_bWisited變量作為該結(jié)點是否被遍歷過的標(biāo)記。在鄰接表中使用HeadList鏈表來管理頭結(jié)點，在頭結(jié)點中使用NodeList鏈表來管理與之相連的表結(jié)點。

圖5 鄰接表類圖

4.1.3 三叉鏈表結(jié)點類

設(shè)計三叉鏈表的結(jié)點類（CBTNode），其成員變量包括：層數(shù)、標(biāo)識、左孩子、右孩子、父結(jié)點和一個指向自動布局鏈表結(jié)點(CBinaryTreeNode)的指針。通過該指針得到與三叉鏈表結(jié)點對應(yīng)的自動布局鏈表中的結(jié)點。在該類中設(shè)計SetBinaryTreeNodePosition(CPoint posParent， BOOL bLeft)函數(shù)，實現(xiàn)計算自動布局鏈表中結(jié)點位置的功能。函數(shù)第一個參數(shù)是父結(jié)點在自動布局界面中的位置，第二個參數(shù)指出該結(jié)點是左孩子還是右孩子。

圖6 三叉鏈表結(jié)點類

4.2 廣度優(yōu)先遍歷算法

對準(zhǔn)二叉樹進(jìn)行廣度優(yōu)先遍歷[4]的算法如圖4所示。圖中有一個大循環(huán)——隊，存儲未被遍歷的鄰接表的頭結(jié)點。在遍歷中從隊中取出隊頭，從頭結(jié)點中得到表結(jié)點鏈表，從表結(jié)點鏈表中再取出表結(jié)點。如果此表結(jié)點沒有被訪問過，則將與表結(jié)點ID相等的頭結(jié)點入隊，繼續(xù)循環(huán)。如果表結(jié)點已被訪問，且不是當(dāng)前頭結(jié)點的父結(jié)點，則該二叉樹中存在回路。當(dāng)隊為空時，遍歷結(jié)束。遍歷結(jié)束后，如果圖中還存在沒有被遍歷的頭結(jié)點，則準(zhǔn)二叉樹為非連通圖。

圖7 準(zhǔn)二叉樹的廣度優(yōu)先遍歷算法

在圖4中，通過鄰接表可以確定結(jié)點的父子關(guān)系。結(jié)點的兄弟關(guān)系通過如下方法確定。首先判斷父結(jié)點是否已經(jīng)存在左（右）孩子，如果存在則在數(shù)據(jù)建模鏈表中找到該結(jié)點，比較它們的位置確定兄弟關(guān)系；如果父結(jié)點沒有孩子，則通過比較父子在數(shù)據(jù)建模鏈表中結(jié)點的位置，確定該結(jié)點是左/右孩子。

確定了二叉樹結(jié)點的父子兄弟關(guān)系后，根據(jù)二叉樹的深度，重新設(shè)計自動布局鏈表結(jié)點的大小。然后，再對二叉樹進(jìn)行先根遍歷，根據(jù)前面得到的公式(1)(2)重新計算自動布局鏈表結(jié)點的位置。從而實現(xiàn)結(jié)點自動布局。

5、結(jié)論

該文改變了學(xué)生對二叉樹習(xí)慣性感知，對理解二叉樹的概念和有關(guān)遍歷算法有著極大的促進(jìn)作用。通過對準(zhǔn)二叉樹進(jìn)行圖的廣度優(yōu)先遍歷，建立其三叉鏈表和自動布局鏈表。又通過對其先序遍歷，計算自動布局鏈表的結(jié)點位置，從而實現(xiàn)結(jié)點的自動布局。

[1]熊岳山,陳懷義.《數(shù)據(jù)結(jié)構(gòu)》教材改革的設(shè)想[J].高等教育研究學(xué)報,2000,(2):62.

[2]楊曉波.數(shù)據(jù)結(jié)構(gòu)可視化CAI系統(tǒng)的設(shè)計與實現(xiàn)[J].計算機應(yīng)用與軟件,2008,(9):196.

[3]楊曉波,王聰華.COM組件技術(shù)在數(shù)據(jù)結(jié)構(gòu)可視化中的應(yīng)用[J].微計算機信息，2007,(6-3):233.

[4]Jeff Prosise.MFC Windows程序設(shè)計[M].北京博彥科技發(fā)展有限責(zé)任公司譯.北京:清華大學(xué)出版社,2001.

[5]嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京:清華大學(xué)出版社,1997.

On Laying Out a Quasi-Binary Tree Rooted on Any Node

JIANG Xue-dong; SUN Hai-min
(Network Information Center, Chengde Teachers’ College, Chengde, 067000, China)

How to lay out a quasi-binary tree rooted on any node automatically many times is the problem the author encountered in his software development. It’s critical to carry out the algorithm of breadth-first search on the quasi-binary tree. First, the quasi-binary tree is considered as a graph and adjacency list is created for it. Second, it is traversed by using the algorithm of breadth-first search. The trinary linked list and automatic layout linked list are created during the traversal. Finally, it is traversed by using the algorithm of preorder traversal. The position of the node of the automatic layout linked list is calculated by the relationship of parent-child and being brothers of the corresponding node in the trinary linked list. The software changes students' perception about the binary tree and promotes their understanding of the concepts and algorithms of it.

Data Structure; Algorithm; Binary tree; Laying out automatically; Trinary linked list

O1-8

A

2095-3763(2017)04-0121-06

10.16729/j.cnki.jhnun.2017.04.018

2017-08-24

姜學(xué)東（1980- ），男，黑龍江拜泉人，河北民族師范學(xué)院數(shù)學(xué)與計算機科學(xué)學(xué)院，講師(實驗師)，碩士，主要研究方向為計算機網(wǎng)絡(luò)系統(tǒng)與計算機信息管理系統(tǒng)；孫海民（1970- ），男，河北承德人，滿族，副教授，碩士研究生，主要研究方向為計算機網(wǎng)絡(luò)系統(tǒng)與計算機教育應(yīng)用。

2017年承德市科技局項目“承德市基于LBS的承德避暑山莊景區(qū)游客移動服務(wù)系統(tǒng)設(shè)計與開發(fā)”（編號：201702B008）；2017年河北省教育廳資助科研項目“Flattening特點的大學(xué)課程學(xué)習(xí)過程性評價系統(tǒng)研發(fā)”（編號：Z2017154）；2017年河北省科學(xué)技術(shù)研究與發(fā)展計劃科普專項項目“智慧教育知識科普網(wǎng)建設(shè)” (編號17K50320D）；2015年度承德市教育科學(xué)研究“十二五”規(guī)劃專項課題“承德高校翻轉(zhuǎn)課堂實施路徑研究”（編號：1501001）。

責(zé)任編輯：宋 爽