利用括號表示法優化二叉樹算法問題的研究

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

貴州商學院計算機與信息工程學院 貴州貴陽 550014

隨著科技的提高,互聯網行業快速發展。無論是對于想從事編程工作的科班學生,或是從事實際開發的從業者。若想寫出較為復雜并且更加簡潔高效的代碼,都需要用到數據結構的知識。

而樹作為數據結構學習中的一個重要的非線性數據結構,是在實際開發中經常用到的,其中二叉樹是樹結構中最重要的一個基本結構。在傳統的算法中,我們構造二叉樹的時候,是一個遞歸過程,使用了分治法的思想,即根據兩種遍歷序列確定當前樹的根節點,左子樹的兩種遍歷序列和右子樹的兩種遍歷序列,再用相同的方法確定左子樹和右子樹的根節點。其他二叉樹基礎運算,如查詢二叉樹的深度、某一層有多少個節點以及查詢有多少個葉子節點時候運用的都是遞歸函數。

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

1 二叉樹的構造算法

1.1 傳統遞歸算法實現

二叉樹具有順序和鏈式兩種存儲結構,其中鏈式存儲結構一般比較常用,本文通過設置二叉樹的數據域、左鏈域和右鏈域來定義二叉樹的結點類型,結點數據類型的C語言描述如下:

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

typedef struct BTNode

{

ElemType data;//數據域為任意類型

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

}*BiTree,BiNode;

//BiTree為二叉樹結點的指針類型,BiNode為普通類型

根據所聲明的二叉樹結點類型,按照先序遍歷二叉樹的執行過程,先序序列創建二叉樹,具體代碼描述如下:

BiTree buildTree()

{

ElemType a;

BiTree root;

scanf(“%d”,&a);//輸入結點的值

if(a==’ ‘)

root=NULL;//輸入的字符為空格,返回空指針,證明該節點沒有字節點

else

{

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

T->data=a;//給結點的數據域賦值

T->left=buildTree();

//給結點的左鏈域賦值

T->right=buildTree();

//給結點的右鏈域賦值

}

returnroot;//返回創建好的結點地址

}

如圖1,如果使用常規算法構建這樣一棵二叉樹,需要調用buildTree()函數八次,遞歸層數最大要調到四層。

圖1 二叉樹示例

雖然常規的遞歸算法具有代碼簡潔、編寫和理解容易等特點,但在運行時需要系統內部的棧來實現,因此執行需要消耗大量的空間和時間,運行效率較低。

1.2 用括號表示法實現

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

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

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

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

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

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

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

TreeNode*buildTree(string s)

{if(s.empty())

{return NULL;}//根結點

TreeNode*root=new TreeNode(s[0]);//棧用于存儲未完成的結點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 利用括號表示法優化二叉樹算法

2.1 查找二叉樹深度

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

但是由于遞歸函數的局限性,所以本文用括號表示法去優化這個算法。因為在括號表示法中,如果出現了左括號代表該節點有子節點,深度加一。逗號的話代表該節點的兄弟結點,深度不變。如果是右括號的話,代表這一層已經結束,要返回上一層,所以深度減一。然后用一個記錄變量,一直更新為最大值,最后輸出即可。

C語言描述如下:

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

int Depth=1;//默認從根節點開始

int max;//記錄最大深度

int BinaryTreeDepth(){

for(int i=0;i

{

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

Depth++;//出現了左括號代表該節點有子節點,深度加一

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

Depth--;//是右括號的話,代表這一層已經結束,深度減一

if(Depth>max)

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

}

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

}

如果使用傳統的遞歸算法,需要調用遞歸函數八次,但是用括號表示法去優化以后只需要調用一次函數,而且不浪費額外的空間花銷,同時運算速度也得到了極大的提升。

2.2 查找二叉樹某一層節點數

有時候對于一棵比較大的二叉樹,有需求知道某一層的節點個數。如果使用傳統的遞歸算法,需要遍歷每一個分支到所需要的那一層,然后去統計該層的節點數量。

但用括號表示法優化該算法的時候,可以類比于查找二叉樹深度的函數,設定一個定位變量,如果出現了左括號代表該節點有子節點,定位變量層數加一。逗號的話代表是同一層某一節點的兄弟結點,層數不變。如果是右括號的話,代表這一層已經結束,要返回上一層,所以層數減一。確定到所求層數以后統計節點數量即可。

C語言描述如下:

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

int Layers=1;//默認從根節點開始

int Num=0;//記錄節點數

int BinaryLayersNum(int k){

//k是所求層數

for(int i=0;i

{

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

Layers++;//出現了左括號代表該節點有子節點,深度加一

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

Layers--;//是右括號的話,代表這一層已經結束,深度減一

if(Layers==k)

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

Num++;//記錄節點數

}

return Num;//返回二叉樹某一層節點數

}

2.3 查找二叉樹葉子節點數

在實際開發需求中,經常會需要查詢一棵二叉樹所有的葉子節點數。所謂葉子節點數,就是沒有子節點的節點。在傳統的算法中,都是用遞歸函數一直查詢到某一個沒有子節點的節點,然后記錄,直到把整棵二叉樹都遍歷完成。

但是這種方式不僅在空間和時間的利用率極其低下,當二叉樹比較大時,遞歸的層數無法達到那么多,所以導致無法計算。

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

C語言描述如下:

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

int Num=0;//記錄節點數

int BinaryLeafNodes(){

for(int i=0;i

{

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

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

Num++;

}

return Num;

}

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

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

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

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

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(“)”);

}

}

}

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

4 結論

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

本文對于傳統二叉樹的算法,與用優化后的括號表示法表示的二叉樹算法進行了比較,本文分別設立了八節點、二十節點與五十節點的二叉樹,在相同情況下,對兩種算法所用的時間進行了比較,比較結果如圖2所示。

圖2 算法所用時間比較

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

實驗結果表明,求二叉樹深度算法效率提高了18%。求二叉樹葉子節點算法所提高效率為57%。可以看出,通過括號表示法改進的二叉樹算法在時間上有較大的提升。同時,由于只用了一個字符串去存儲,所以也節約了大量的空間。

在二十節點的情況下,兩種算法所用的時間比較結果如圖3所示。

圖3 算法所用時間比較

從圖3可以看出,當節點數中等的情況下,傳統算法的時間復雜度較低,但是消耗的空間較大。優化算法時間稍微較長,但是消耗的空間更小。

在五十節點的情況下,傳統算法由于遞歸函數調用次數過多導致棧堆溢出無法執行程序,而優化后的算法則不受二叉樹大小影響。

基于這種思想,將原有運用遞歸算法所大量浪費的空間與時間方面進行改進,也為了進一步優化圖以及其他有關樹的算法提供了部分借鑒思想。