利用括號表示法優(yōu)化二叉樹算法問題的研究

張加恩 吳鳳英 梁玉林 杜少波

貴州商學(xué)院計(jì)算機(jī)與信息工程學(xué)院 貴州貴陽 550014

隨著科技的提高,互聯(lián)網(wǎng)行業(yè)快速發(fā)展。無論是對于想從事編程工作的科班學(xué)生,或是從事實(shí)際開發(fā)的從業(yè)者。若想寫出較為復(fù)雜并且更加簡潔高效的代碼,都需要用到數(shù)據(jù)結(jié)構(gòu)的知識。

而樹作為數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)中的一個重要的非線性數(shù)據(jù)結(jié)構(gòu),是在實(shí)際開發(fā)中經(jīng)常用到的,其中二叉樹是樹結(jié)構(gòu)中最重要的一個基本結(jié)構(gòu)。在傳統(tǒng)的算法中,我們構(gòu)造二叉樹的時候,是一個遞歸過程,使用了分治法的思想,即根據(jù)兩種遍歷序列確定當(dāng)前樹的根節(jié)點(diǎn),左子樹的兩種遍歷序列和右子樹的兩種遍歷序列,再用相同的方法確定左子樹和右子樹的根節(jié)點(diǎn)。其他二叉樹基礎(chǔ)運(yùn)算,如查詢二叉樹的深度、某一層有多少個節(jié)點(diǎn)以及查詢有多少個葉子節(jié)點(diǎn)時候運(yùn)用的都是遞歸函數(shù)。

但是遞歸函數(shù)本身有很多局限性,比如消耗的空間資源較大,所以遞歸的層數(shù)不能太多,這就在一定程度上限制了二叉數(shù)的大小。而本文采用了括號表示法去描述一顆二叉樹的具體構(gòu)造,對字符串進(jìn)行遍歷去運(yùn)算有關(guān)二叉樹的基礎(chǔ)運(yùn)算,從而解決了遞歸算法查詢二叉樹的一些弊端。

1 二叉樹的構(gòu)造算法

1.1 傳統(tǒng)遞歸算法實(shí)現(xiàn)

二叉樹具有順序和鏈?zhǔn)絻煞N存儲結(jié)構(gòu),其中鏈?zhǔn)酱鎯Y(jié)構(gòu)一般比較常用,本文通過設(shè)置二叉樹的數(shù)據(jù)域、左鏈域和右鏈域來定義二叉樹的結(jié)點(diǎn)類型,結(jié)點(diǎn)數(shù)據(jù)類型的C語言描述如下:

typedef int ElemType;//定義ElemType為int類型

typedef struct BTNode

{

ElemType data;//數(shù)據(jù)域?yàn)槿我忸愋?/p>

struct BTNode*left,*right;//left和right分別為左鏈域和右鏈域

}*BiTree,BiNode;

//BiTree為二叉樹結(jié)點(diǎn)的指針類型,BiNode為普通類型

根據(jù)所聲明的二叉樹結(jié)點(diǎn)類型,按照先序遍歷二叉樹的執(zhí)行過程,先序序列創(chuàng)建二叉樹,具體代碼描述如下:

BiTree buildTree()

{

ElemType a;

BiTree root;

scanf(“%d”,&a);//輸入結(jié)點(diǎn)的值

if(a==’ ‘)

root=NULL;//輸入的字符為空格,返回空指針,證明該節(jié)點(diǎn)沒有字節(jié)點(diǎn)

else

{

if(!(root=(BiTree)malloc(sizeof(BTNode))))//開辟一個大小為BTNode的空間,存放新節(jié)點(diǎn)

T->data=a;//給結(jié)點(diǎn)的數(shù)據(jù)域賦值

T->left=buildTree();

//給結(jié)點(diǎn)的左鏈域賦值

T->right=buildTree();

//給結(jié)點(diǎn)的右鏈域賦值

}

returnroot;//返回創(chuàng)建好的結(jié)點(diǎn)地址

}

如圖1,如果使用常規(guī)算法構(gòu)建這樣一棵二叉樹,需要調(diào)用buildTree()函數(shù)八次,遞歸層數(shù)最大要調(diào)到四層。

圖1 二叉樹示例

雖然常規(guī)的遞歸算法具有代碼簡潔、編寫和理解容易等特點(diǎn),但在運(yùn)行時需要系統(tǒng)內(nèi)部的棧來實(shí)現(xiàn),因此執(zhí)行需要消耗大量的空間和時間,運(yùn)行效率較低。

1.2 用括號表示法實(shí)現(xiàn)

所謂括號表示法,就是一種用字符串體現(xiàn)二叉樹各節(jié)點(diǎn)關(guān)系的一種表示方式。具體來說,如果一個節(jié)點(diǎn)還有子節(jié)點(diǎn)的話,在這個節(jié)點(diǎn)所代表的字母后面會跟著一對括號,這一對括號里面就是該節(jié)點(diǎn)子節(jié)點(diǎn)的信息。如果一個節(jié)點(diǎn)處在一個括號當(dāng)中,用逗號分隔該節(jié)點(diǎn)和該節(jié)點(diǎn)的兄弟節(jié)點(diǎn)。

如上圖1,用括號表示法表示出來的結(jié)果就為A(B(C,D(E,F)),G(H))。通過括號表示法,可以較為清楚地看見二叉樹每一個節(jié)點(diǎn)所對應(yīng)的關(guān)系以及層級,這樣二叉樹的大小就不再限制于遞歸函數(shù)層數(shù)的局限性了。

傳統(tǒng)的括號表示法還有一點(diǎn)局限,就是對于只有右子樹的情況表達(dá)不明確,如上圖的H節(jié)點(diǎn)如果為右子樹,和為左子樹的情況無法區(qū)分。而本文將括號表示法進(jìn)行了優(yōu)化,只有在一個括號里面逗號右邊的字母才表示上一個節(jié)點(diǎn)的右子數(shù),所以如果一個節(jié)點(diǎn)它沒有左子樹的話,在優(yōu)化后的括號表示法中依舊會寫一個逗號,表示這個單一節(jié)點(diǎn)為右節(jié)點(diǎn),如圖1如果H結(jié)點(diǎn)為右子數(shù),則會表示為A(B(C,D(E,F)),G(,H))。

同時,可以通過對這串字符串進(jìn)行遍歷,從而計(jì)算出想要的二叉數(shù)的數(shù)據(jù),比如它的深度、某一層有多少個節(jié)點(diǎn)、葉子節(jié)點(diǎn)的個數(shù)等。

1.3 用括號表示法生成二叉樹

用括號表示法生成二叉樹時,使用了棧來存儲未完成的結(jié)點(diǎn),每次處理一個括號中的字符,如果字符為節(jié)點(diǎn)的data,則創(chuàng)建一個新的結(jié)點(diǎn),并將其添加到父結(jié)點(diǎn)的左子樹或右子樹中,然后將其入棧。如果字符是右括號,則彈出棧頂元素,處理完畢后。最后返回根結(jié)點(diǎn)即可。

//通過括號表示法建立二叉樹

TreeNode*buildTree(string s)

{if(s.empty())

{return NULL;}//根結(jié)點(diǎn)

TreeNode*root=new TreeNode(s[0]);//棧用于存儲未完成的結(jié)點(diǎn)stackst;

st.push(root);

for(int i=1;i

{TreeNode*cur=st.top();st.pop();//處理左子樹

if(s[i]!='('&& s[i]!=')')

{cur->left=new TreeNode(s[i]);

st.push(cur->left);}//處理右子樹

if(i+1

{cur->right=new TreeNode(s[i+1]);

st.push(cur->right);}}

return root;}

2 利用括號表示法優(yōu)化二叉樹算法

2.1 查找二叉樹深度

二叉樹的深度就是二叉樹有多少層,如圖1,二叉樹的深度為四。大部分情況下,傳統(tǒng)查找二叉樹深度的算法使用的是遞歸算法。算法邏輯為:一直查找某一個節(jié)點(diǎn),是否還有子節(jié)點(diǎn),直至沒有為止。然后記錄它的深度,然后把所有的節(jié)點(diǎn)全都查找完,最后輸出記錄下來的最大深度。

但是由于遞歸函數(shù)的局限性,所以本文用括號表示法去優(yōu)化這個算法。因?yàn)樵诶ㄌ柋硎痉ㄖ?如果出現(xiàn)了左括號代表該節(jié)點(diǎn)有子節(jié)點(diǎn),深度加一。逗號的話代表該節(jié)點(diǎn)的兄弟結(jié)點(diǎn),深度不變。如果是右括號的話,代表這一層已經(jīng)結(jié)束,要返回上一層,所以深度減一。然后用一個記錄變量,一直更新為最大值,最后輸出即可。

C語言描述如下:

string BinaryTree;//用括號表示法記錄二叉樹

int Depth=1;//默認(rèn)從根節(jié)點(diǎn)開始

int max;//記錄最大深度

int BinaryTreeDepth(){

for(int i=0;i

{

if(BinaryTree[i]==’(’)

Depth++;//出現(xiàn)了左括號代表該節(jié)點(diǎn)有子節(jié)點(diǎn),深度加一

if(BinaryTree[i]==’)’)

Depth--;//是右括號的話,代表這一層已經(jīng)結(jié)束,深度減一

if(Depth>max)

max=Depth;//記錄最大深度

}

return max;//返回二叉樹深度

}

如果使用傳統(tǒng)的遞歸算法,需要調(diào)用遞歸函數(shù)八次,但是用括號表示法去優(yōu)化以后只需要調(diào)用一次函數(shù),而且不浪費(fèi)額外的空間花銷,同時運(yùn)算速度也得到了極大的提升。

2.2 查找二叉樹某一層節(jié)點(diǎn)數(shù)

有時候?qū)τ谝豢帽容^大的二叉樹,有需求知道某一層的節(jié)點(diǎn)個數(shù)。如果使用傳統(tǒng)的遞歸算法,需要遍歷每一個分支到所需要的那一層,然后去統(tǒng)計(jì)該層的節(jié)點(diǎn)數(shù)量。

但用括號表示法優(yōu)化該算法的時候,可以類比于查找二叉樹深度的函數(shù),設(shè)定一個定位變量,如果出現(xiàn)了左括號代表該節(jié)點(diǎn)有子節(jié)點(diǎn),定位變量層數(shù)加一。逗號的話代表是同一層某一節(jié)點(diǎn)的兄弟結(jié)點(diǎn),層數(shù)不變。如果是右括號的話,代表這一層已經(jīng)結(jié)束,要返回上一層,所以層數(shù)減一。確定到所求層數(shù)以后統(tǒng)計(jì)節(jié)點(diǎn)數(shù)量即可。

C語言描述如下:

string BinaryTree;//用括號表示法記錄二叉樹

int Layers=1;//默認(rèn)從根節(jié)點(diǎn)開始

int Num=0;//記錄節(jié)點(diǎn)數(shù)

int BinaryLayersNum(int k){

//k是所求層數(shù)

for(int i=0;i

{

if(BinaryTree[i]==’(’)

Layers++;//出現(xiàn)了左括號代表該節(jié)點(diǎn)有子節(jié)點(diǎn),深度加一

if(BinaryTree[i]==’)’)

Layers--;//是右括號的話,代表這一層已經(jīng)結(jié)束,深度減一

if(Layers==k)

if(BinaryTree[i]>=’A’&&BinaryTree[i]<=’Z’)//只記錄節(jié)點(diǎn)數(shù)(除去括號,逗號等符號)

Num++;//記錄節(jié)點(diǎn)數(shù)

}

return Num;//返回二叉樹某一層節(jié)點(diǎn)數(shù)

}

2.3 查找二叉樹葉子節(jié)點(diǎn)數(shù)

在實(shí)際開發(fā)需求中,經(jīng)常會需要查詢一棵二叉樹所有的葉子節(jié)點(diǎn)數(shù)。所謂葉子節(jié)點(diǎn)數(shù),就是沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。在傳統(tǒng)的算法中,都是用遞歸函數(shù)一直查詢到某一個沒有子節(jié)點(diǎn)的節(jié)點(diǎn),然后記錄,直到把整棵二叉樹都遍歷完成。

但是這種方式不僅在空間和時間的利用率極其低下,當(dāng)二叉樹比較大時,遞歸的層數(shù)無法達(dá)到那么多,所以導(dǎo)致無法計(jì)算。

用括號表示法優(yōu)化該算法的時候,本文所改進(jìn)的算法可以解決上述的弊端。通過括號表示法的性質(zhì)可以得知,如果一個節(jié)點(diǎn)有子節(jié)點(diǎn),該節(jié)點(diǎn)的后面一定會跟著一個左括號。如果沒有左括號,就證明該節(jié)點(diǎn)是一個葉子節(jié)點(diǎn),在算法中設(shè)置一個記錄變量,記錄葉子節(jié)點(diǎn)的個數(shù)。

C語言描述如下:

string BinaryTree;//用括號表示法記錄二叉樹

int Num=0;//記錄節(jié)點(diǎn)數(shù)

int BinaryLeafNodes(){

for(int i=0;i

{

if(BinaryTree[i]>=’A’&&BinaryTree[i]<=’Z’)//只判斷節(jié)點(diǎn)(除去括號,逗號等符號)

if(BinaryTree[i+1]!=’(’)//如果沒有子節(jié)點(diǎn)

Num++;

}

return Num;

}

通過上述代碼可以看出,改進(jìn)后的算法只用遍歷一次字符串就可以求得所有的葉子節(jié)點(diǎn),極大地減輕了用遞歸函數(shù)所帶來的時間和空間上的消耗,并且運(yùn)算速度也比遞歸算法更快。

3 二叉樹輸出為括號表示法

通過上面的比較可以看出,經(jīng)過括號表示法優(yōu)化以后的算法運(yùn)算速度較遞歸算法更快,同時極大節(jié)省了空間上的浪費(fèi)。但對于已經(jīng)建好的二叉樹,需要輸出為括號表示法,所以本文也提出了一種將二叉樹輸出為括號表示法的算法。

其過程是對于非空二叉樹先輸出根節(jié)點(diǎn)值,當(dāng)存在左孩子節(jié)點(diǎn)或右孩子節(jié)點(diǎn)時,輸出一個“(”符號。然后遞歸處理左子樹,輸出一個“,”符號,遞歸處理柚子樹,最后輸出一個“)”符號。

C語言描述如下:

void DispBTree(BiTree*bt){

if(bt!=NULL)

{

printf(“%c”,bt->data);

if(bt->lchild!=NULL&&bt->rchild!=NULL)

{

printf(“(”);

DispBTree(bt->lchild);

if(bt->rchild!=NULL)

printf(“,”);

DispBTree(bt->rchild);

printf(“)”);

}

}

}

通過上述算法,我們就可以將一個已經(jīng)建立好的二叉樹輸出成一個用括號表示法描述的二叉樹的字符串。然后通過對這個字符串的處理,我們就可以對本文所提到的幾種關(guān)于二叉樹的算法進(jìn)行計(jì)算與使用。

4 結(jié)論

傳統(tǒng)的二叉樹算法都是用遞歸算法分析,但遞歸算法本身就著許多局限性。本文主要闡述了利用括號表示法改進(jìn)二叉樹算法的一些案例,除此之外,這種思想還可以用來改進(jìn)求二叉樹總結(jié)點(diǎn)的運(yùn)算以及其他跟二叉樹有關(guān)的運(yùn)算。

本文對于傳統(tǒng)二叉樹的算法,與用優(yōu)化后的括號表示法表示的二叉樹算法進(jìn)行了比較,本文分別設(shè)立了八節(jié)點(diǎn)、二十節(jié)點(diǎn)與五十節(jié)點(diǎn)的二叉樹,在相同情況下,對兩種算法所用的時間進(jìn)行了比較,比較結(jié)果如圖2所示。

圖2 算法所用時間比較

實(shí)驗(yàn)使用編譯環(huán)境為Dev-C++5.4.0版本,數(shù)據(jù)量是一棵比較小的八節(jié)點(diǎn)二叉樹,如前文圖1所示。通過在相同環(huán)境下,執(zhí)行同樣功能的程序。通過高精度時控函數(shù)QueryPerformanceCounter函數(shù),測量程序運(yùn)行時間精確到毫秒。

實(shí)驗(yàn)結(jié)果表明,求二叉樹深度算法效率提高了18%。求二叉樹葉子節(jié)點(diǎn)算法所提高效率為57%?？梢钥闯?通過括號表示法改進(jìn)的二叉樹算法在時間上有較大的提升。同時,由于只用了一個字符串去存儲,所以也節(jié)約了大量的空間。

在二十節(jié)點(diǎn)的情況下,兩種算法所用的時間比較結(jié)果如圖3所示。

圖3 算法所用時間比較

從圖3可以看出,當(dāng)節(jié)點(diǎn)數(shù)中等的情況下,傳統(tǒng)算法的時間復(fù)雜度較低,但是消耗的空間較大。優(yōu)化算法時間稍微較長,但是消耗的空間更小。

在五十節(jié)點(diǎn)的情況下,傳統(tǒng)算法由于遞歸函數(shù)調(diào)用次數(shù)過多導(dǎo)致棧堆溢出無法執(zhí)行程序,而優(yōu)化后的算法則不受二叉樹大小影響。

基于這種思想,將原有運(yùn)用遞歸算法所大量浪費(fèi)的空間與時間方面進(jìn)行改進(jìn),也為了進(jìn)一步優(yōu)化圖以及其他有關(guān)樹的算法提供了部分借鑒思想。