基于隊列的任意二叉樹層次問題算法設計

吳 志 福

(石家莊職業(yè)技術(shù)學院 組織部，河北 石家莊 050081)

在數(shù)據(jù)結(jié)構(gòu)中，樹是一種用途廣泛的結(jié)構(gòu).二叉樹是每個節(jié)點最多有兩個子樹的樹結(jié)構(gòu).在對任意二叉樹進行存儲的時候，普遍采用鏈式結(jié)構(gòu)存儲數(shù)據(jù)，在對鏈式結(jié)構(gòu)存儲的任意二叉樹進行操作的時候，常采用遞歸的方法來實現(xiàn).在求任意二叉樹的層次問題上，也采用遞歸方法來實現(xiàn).但遞歸方式算法復雜且不容易理解.對任意二叉樹的研究發(fā)現(xiàn)，對于涉及到任意二叉樹層次的計算，由于其結(jié)構(gòu)的特殊性，完全可以使用比較容易理解的隊列來解決.

1 二叉樹的存儲結(jié)構(gòu)

二叉樹的存儲方式有順序結(jié)構(gòu)和鏈式結(jié)構(gòu)兩種[1].在任意二叉樹的順序存儲結(jié)構(gòu)中，采用數(shù)組存放任意二叉樹的節(jié)點.二叉樹層次和數(shù)組下標表示為：

M=log2(n+1).

其中，M表示二叉樹層次，n表示數(shù)組的最大下標.

圖1為任意二叉樹結(jié)構(gòu)示意圖.采用順序結(jié)構(gòu)存儲時，利用數(shù)組存儲的結(jié)果見表1.

圖1 任意二叉樹結(jié)構(gòu)示意圖

數(shù)組下標存放節(jié)點數(shù)組下標存放節(jié)點數(shù)組下標存放節(jié)點1B14B47B52B25空8B63B36空??

從表1可以看出，雖然采用順序結(jié)構(gòu)存儲的任意二叉樹可以利用公式很方便地計算出任意二叉樹層次，但是利用數(shù)組存儲數(shù)據(jù)時，會存在大量空節(jié)點，造成空間的浪費，因此任意二叉樹存儲一般不采用順序結(jié)構(gòu)而采用鏈式結(jié)構(gòu).

在采用鏈式結(jié)構(gòu)存儲任意二叉樹時，由于二叉樹的每個結(jié)點最多有左右兩個孩子，因此，每個結(jié)點除了存儲自身的數(shù)據(jù)外，還設置兩個指針分別指向左孩子、右孩子的結(jié)點.鏈式結(jié)構(gòu)任意二叉樹存儲結(jié)點示意圖見圖2.

左孩子地址節(jié)點數(shù)據(jù)右孩子地址

圖2鏈式結(jié)構(gòu)任意二叉樹存儲結(jié)點示意圖

對于圖1所示任意二叉樹，其B1-B4節(jié)點的鏈式存儲結(jié)構(gòu)如圖3所示.

(1)B1節(jié)點存儲結(jié)構(gòu)

(2)B2節(jié)點存儲結(jié)構(gòu)

(3)B3節(jié)點存儲結(jié)構(gòu)

(4)B4節(jié)點存儲結(jié)構(gòu)

圖3任意二叉樹節(jié)點的鏈式存儲結(jié)構(gòu)示意圖

鏈式結(jié)構(gòu)存儲保留了任意二叉樹的結(jié)構(gòu)，且不存在空間浪費問題，但是無法通過公式來計算二叉樹的層次，只能采用遞歸的方式遍歷二叉樹進而求得層次.由于遞歸涉及到調(diào)用時空間的開辟、現(xiàn)場的保存、參數(shù)的傳遞等問題，算法較難理解，因此需要尋找合適的算法求鏈式結(jié)構(gòu)任意二叉樹的層次.

2 算法設計

2.1 設計思路

在計算鏈式結(jié)構(gòu)存儲的任意二叉樹層次的過程中，需要遍歷整個任意二叉樹，即需要處理多個相同結(jié)構(gòu)的數(shù)據(jù)，為了便于數(shù)據(jù)的處理，減少空間的浪費，采用隊列結(jié)構(gòu)來實現(xiàn)層次算法.在使用隊列求任意二叉樹層次時，算法中僅增加了一個隊列和一個順序結(jié)構(gòu)的數(shù)組[2]，沒有增加太多的空間，但卻減少了遞歸調(diào)用時空間的開辟.

隊列是常用的一種數(shù)據(jù)結(jié)構(gòu)，其特點是“先進先出”，即刪除操作只允許在隊列的前端進行，插入操作只在隊列的后端進行，進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭，所以先進入隊列的元素總是先被刪除的.利用隊列這一特點，對采用鏈式結(jié)構(gòu)存儲的任意二叉樹按照層次關(guān)系將其節(jié)點進行入隊和出隊操作，將其從邏輯關(guān)系上轉(zhuǎn)變?yōu)榫€性結(jié)構(gòu)，在轉(zhuǎn)變的過程中，利用輔助數(shù)組記錄任意二叉樹的層次.當轉(zhuǎn)變完成時，任意二叉樹的層次也就得以保存.

在用隊列實現(xiàn)二叉樹的層次問題時，讓根節(jié)點首先入隊，繼續(xù)進行操作的時候，節(jié)點出隊的同時如果它的左孩子或右孩子不為空，循環(huán)操作將其入隊.這樣，每一層的節(jié)點將按照先左后右的順序入隊.由于節(jié)點的地址之間沒有固定的線性關(guān)系，因此利用一個輔助數(shù)組來記住每一層的最左節(jié)點在隊列中的位置，在隊列不為空的時候?qū)㈥狀^元素出隊，同時重復前面的入隊操作.由于節(jié)點在不斷地入隊和出隊，所以記錄節(jié)點位置的輔助數(shù)組的長度要不小于二叉樹的最大寬度.

2.2 設計程序

在算法設計過程中，隊列采用結(jié)構(gòu)體來表示，結(jié)構(gòu)為：

struct queue /* 隊列*/

{

struct bitree *elem[MAXSIZE]; /* bitree為鏈式存儲的任意二叉樹的節(jié)點類型*/

int front,rear; /*頭指針和尾指針*/

}

為了節(jié)省空間，減少系統(tǒng)的空間開銷，隊列中只保存了指向鏈式存儲的任意二叉樹的節(jié)點的指針，而沒有保存其數(shù)據(jù).

對圖1所示任意二叉樹進行遍歷的過程如下：

根節(jié)點B1首先入隊.此時隊列中的數(shù)據(jù)如圖4所示.

0節(jié)點B11

圖4根節(jié)點B1入隊后隊列示意圖

此時，輔助數(shù)組fuzhu[ ]中保存元素全部初始化為0，輔助數(shù)組下標j初始化為0，樹的層次數(shù)k標記為0.為了標記是否是最左節(jié)點入隊，初始化flag為0.

隨后，在隊列不為空的情況下進入隊列的循環(huán)操作.

(1)隊首元素B1出隊，保存到變量P中.執(zhí)行出隊操作后，圖4中數(shù)據(jù)變化見圖5所示.

1節(jié)點B11

圖5根節(jié)點B1出隊后隊列示意圖

(2)判斷p是否有左孩子或右孩子，且其左、右孩子是否為下一層的最左節(jié)點，如果是最左節(jié)點，則j增加1，k增加1，將下一層最左節(jié)點地址寫入fuzhu[ ].

在圖1中，節(jié)點B1有左孩子且其左孩子是下一層的最左節(jié)點，因此將j增加1，此時j的值為1，為fuzhu[j]寫入下一層最左節(jié)點的值，此值即為圖4中最右邊的數(shù)據(jù)，即fuzhi[1].由于下一層的最左節(jié)點已經(jīng)入隊，因此更改flag值為1.

(3)判斷已經(jīng)出隊節(jié)點是否為本層的最右節(jié)點，若是，則隊列中首元素為下一層的最左節(jié)點，后續(xù)將開始下一層的出隊和下下層的入隊，因此更改flag值為0.

(4)判斷p的左孩子是否不為空，如果不為空，則左孩子入隊.

(5)判斷p的右孩子是否不為空，如果不為空，則右孩子入隊.

(6)繼續(xù)返回開始步驟進行循環(huán)，直至隊列為空.

對于圖1的任意二叉樹，其遍歷至第三層的過程中，隊列和對應輔助數(shù)組的變化過程如圖6所示.

從圖6中可以看出，隨著任意二叉樹節(jié)點的入隊和出隊，輔助數(shù)組中記錄了每一層節(jié)點的最左節(jié)點，flag值記錄了任意二叉樹的層次.當循環(huán)結(jié)束時，flag的值就是任意二叉樹的層次.

3 算法實現(xiàn)

算法中循環(huán)部分的C語言實現(xiàn)代碼如下：

int cc(struct bitree *root)

/*求任意二叉樹的最大層次數(shù)，二叉樹采用鏈式存儲結(jié)構(gòu)*/

{

int fuzhi={0},j=0,k=1,flag=0;

struct queue *q;

struct bitree *p

inistilize(q);/*隊列初始化*/

p=root;

enterque(q,p);/*根節(jié)點入隊*/

while(! isempty(q)) /*隊列非空*/

{

p=deleteque(q); /*隊首元素出隊*/

if (( p->lchild!=NULL ||p->rchild!=NULL) &&flag= =0)

/* flag 為0時，下一層還沒有節(jié)點入隊， 已經(jīng)出隊節(jié)點的孩子節(jié)點為下一層的最左節(jié)點*/

{

j++; /*輔助數(shù)組下標加1*/

flag=1;

/*將標志變?yōu)?，表示下一層已經(jīng)有節(jié)點入隊 */

fuzhi[j]=q->rear

/*下一層的最左節(jié)點的位置*/;

k++; /*層次數(shù)加1*/

}

if (q->front= =a[j])

/*已經(jīng)出隊節(jié)點為本層的最右節(jié)點*/

flag=0;

if (p->lchild!=NULL)

/*左孩子節(jié)點入隊*/

enterqueue(q,p->lchild);

if(p->rchild!=NULL)

/*右孩子節(jié)點入隊*/

enterqueue(q,p->rchild);

}

return(k); /*返回最大層次數(shù)*/

}

在此算法的具體設計中，對任意二叉樹采用了鏈式存儲結(jié)構(gòu)，隊列采用了順序結(jié)構(gòu)的循環(huán)隊列，并且規(guī)定，當隊列中只剩余一個空間時，隊列滿，即“尾指針+1”，對初始化的隊列長度求余等于“頭指針”時，隊列滿.隊列的出隊、入隊、初始化等問題和循環(huán)隊列的相同.文中不再給出樹、隊列的數(shù)據(jù)結(jié)構(gòu)源代碼和隊列的出隊、入隊、初始化等的代碼.

圖6 算法過程隊列及輔助數(shù)組變化示意圖

4 結(jié)語

本算法的源程序已經(jīng)在Visual C++6.0中通過調(diào)試，能解決求二叉樹的最大層次問題.在解決實際問題的過程中，可以根據(jù)需要將程序加以改變，從而實現(xiàn)和層次相關(guān)問題的求解，如二叉樹的樹形輸出、二叉樹的最大寬度即層上節(jié)點的最大個數(shù)等問題，均可采用此算法.

參考文獻：

[1] 嚴蔚敏，吳偉民．數(shù)據(jù)結(jié)構(gòu):C語言版[M]．北京：清華大學出版社，1997：126-127.

[2] 朱雅莉，李肯立.DNA計算機中基于順序存儲方式的二叉樹數(shù)據(jù)結(jié)構(gòu)[J].計算機應用，2008，28(6):1591-1594.