吳 志 福

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

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

1 二叉樹的存儲結構

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

M=log2(n+1).

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

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

圖1 任意二叉樹結構示意圖

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

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

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

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

圖2鏈式結構任意二叉樹存儲結點示意圖

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

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

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

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

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

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

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

2 算法設計

2.1 設計思路

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

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

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

2.2 設計程序

在算法設計過程中，隊列采用結構體來表示，結構為：

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)結束時，flag的值就是任意二叉樹的層次.

3 算法實現(xiàn)

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

int cc(struct bitree *root)

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

{

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ù)*/

}

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

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

4 結語

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

參考文獻：

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

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