基于遍歷搜索二叉樹中最長路徑的算法研究

摘 要:在對二叉樹存儲結(jié)構(gòu)進行分析的基礎(chǔ)上，介紹二叉樹遍歷算法的一種應(yīng)用，即基于求解二叉樹深度算法設(shè)計實現(xiàn)的搜索二叉樹中最長路徑的算法。這里詳細介紹了搜索二叉樹中最長路徑問題的分析解決思路，在對可能的預(yù)期結(jié)果進行分析的基礎(chǔ)上，給出了算法的設(shè)計方案，同時給出了具體的C語言算法描述。

關(guān)鍵詞:二叉樹; 二叉樹遍歷; 完全二叉樹; 二叉樹的最長路徑; 二叉樹深度

中圖分類號:TP311.12文獻標(biāo)識碼:A

文章編號:1004-373X(2010)08-0054-02

Algorithm of Searching Longest Path in Binary Tree Based on Traverse

WANG Min， ZJAO Xiao-lei

(Weinan Teachers University， Weinan714000， China)

Abstract:By analyzing the storage structure of binary tree， a kind ofapplication of binary tree traversal algorithm， that is，the algorithm ofsearching the longest path in binary tree， which is realized by solving the depth of binary tree， is introduced. The solution ideas of searching the longest path in binary tree are proposed in detail. The design scheme of the algorithm is given by analysing the expected results. The algorithm description in C language is presented.

Keywords:binary tree; binary tree traverse; complete binary tree; longest path in binary tree; depth of binary tree

0 引 言

二叉樹的邏輯結(jié)構(gòu)為樹型結(jié)構(gòu)，結(jié)點間是一對多的層次關(guān)系。所謂二叉樹的遍歷是指按一定規(guī)律對二叉樹中每個結(jié)點進行訪問且僅訪問一次[1-2]。“訪問”的含義很廣，可以是對結(jié)點作各種處理，如輸出結(jié)點的信息等[2，3]。二叉樹的遍歷是二叉樹中所有其他運算的基礎(chǔ)。

本文介紹了二叉樹遍歷在搜索二叉樹中最長路徑算法中的應(yīng)用，重點分析算法的設(shè)計過程，并給出算法的C語言描述。

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

首先考慮二叉樹的存儲結(jié)構(gòu)。接近完全二叉樹形態(tài)的二叉樹采用靜態(tài)向量的存儲方式比較好，此時結(jié)點的父子關(guān)系可根據(jù)完全二叉樹的性質(zhì)5\\(對一棵有n個結(jié)點的完全二叉樹的結(jié)點按層序從1開始編號，則對任一序號大于1的結(jié)點i，其雙親結(jié)點序號為\\，若其左孩子序號小于n，則為2i，若其右孩子序號小于n，則為2i+1)定位對應(yīng)的下標(biāo)結(jié)點，其存儲結(jié)構(gòu)可用C語言定義如下\\:

#define MAX 1000

typedef struct{

DataType data[MAX];

int datanum;

} SeqTree;

其中:data成員用于存儲結(jié)點的元素值;datanum成員用于記錄樹中結(jié)點的總個數(shù)。

對于非完全二叉樹，一般采用二叉鏈表方式存儲，其存儲結(jié)構(gòu)如圖1所示。

圖1 二叉鏈表結(jié)點結(jié)構(gòu)

可用C語言定義如下\\:

typedef struct node{

DataType data;

struct node *Lchild，*Rchild;

} Node， *BTree;

其中:data成員用于存儲結(jié)點的元素值;Lchild和Rchild成員分別為指向該結(jié)點中左右孩子結(jié)點的指針。下面介紹采用二叉鏈表存儲結(jié)構(gòu)的算法。

2 搜索二叉樹中的最長路徑

所謂二叉樹中的最長路徑，一定是從根結(jié)點(位于第1層)到達樹中所在層次最大(也即樹的深度h層)的某個結(jié)點的一條路徑，于是，搜索該最長路徑的算法可以通過求解二叉樹的深度得以解決。

2.1 二叉樹的遍歷算法

對二叉樹進行遍歷的方式分前序、中序、后序和層序，前三種均是以訪問二叉樹中根結(jié)點(root)的次序作為命名的依據(jù)，第四種是從二叉樹的根開始逐層遍歷。這里主要介紹并利用后序遍歷算法，其遞歸算法設(shè)計思想如下:

(1) 若二叉樹為空，則遍歷過程結(jié)束;

(2) 否則;

① 后序遍歷根結(jié)點的左子樹;

② 后序遍歷根結(jié)點的右子樹;

③ 訪問根結(jié)點，算法結(jié)束[1，3-4，6-9]。

2.2 后序遍歷求解二叉樹的深度

求解二叉樹深度的遞歸算法思想可以描述為:

(1) 若二叉樹為空，則深度為0;

(2) 否則其深度應(yīng)為根結(jié)點中左右子樹深度的最大值加1[1，10]。

在求解二叉樹深度的過程中，要對二叉樹進行遍歷。可以利用二叉樹中后序遍歷算法的設(shè)計思想實現(xiàn)這一過程。基于二叉鏈表存儲結(jié)構(gòu)(BTree)的C語言算法描述如下:

int PostTreeDepth(BTree root)

{ int hl，hr，max;

if(root)

{hl=PostTreeDepth(root->Lchild);

hr=PostTreeDepth(root->Rchild);

max=hl>hr?hl:hr;

return (max+1); }

else

return 0;

}

2.3 搜索二叉樹中的最長路徑

搜索二叉樹中的最長路徑時，需要考慮以下因素:

首先，當(dāng)二叉樹的最深層有兩個以上結(jié)點時，其最長路徑不止一條，此時只需要給出最先找到的一條即可。

其次，對于所求得的最長路徑應(yīng)該如何記錄，這取決于問題的需求:

(1) 最簡單的需求是輸出該最長路徑。此時只需要在遍歷時輸出結(jié)點的值即可。

(2) 若問題的解決需要記錄該路徑，則需考慮如何對求得的路徑進行存儲，可采用以下幾種方案:

方案一:另外申請一個順序表結(jié)點空間用于存儲該路徑。

此時順序表中結(jié)點的結(jié)構(gòu)可設(shè)計為如圖2所示。

圖2 路徑中的結(jié)點結(jié)構(gòu)

圖2中data域用于存儲結(jié)點的元素值;tag域用于標(biāo)記后繼結(jié)點是該結(jié)點的左孩子(設(shè)tag為0)，還是右孩子(設(shè)tag為1)。遍歷過程中，每確定路徑中一個結(jié)點，即將結(jié)點值填入順序表對應(yīng)的位置，并設(shè)置其前驅(qū)結(jié)點的tag域。

方案二:另外申請二叉鏈表的結(jié)點空間，構(gòu)成僅含一條單支的二叉樹。

此時路徑中結(jié)點的存儲結(jié)構(gòu)與前述二叉鏈表存儲結(jié)構(gòu)(BTree)相同。在二叉樹中，每確定路徑中一個結(jié)點后，需要進行以下步驟的操作:

① 為該結(jié)點申請新的結(jié)點空間;

② 將結(jié)點值填入新結(jié)點的data域，并設(shè)置新結(jié)點的Lchild和Rchild，指針為NULL;

③ 根據(jù)新結(jié)點是路徑中前驅(qū)結(jié)點的左孩子或右孩子，將新結(jié)點插入前驅(qū)結(jié)點中Lchild或Rchild指針的后面。

方案三:利用原二叉樹的二叉鏈表作出標(biāo)記進行記錄。

這種方案需要對原二叉樹的二叉鏈表結(jié)構(gòu)進行調(diào)整，在每個結(jié)點上增加一個tag域，用于標(biāo)記該結(jié)點是否屬于搜索到的最長路徑。例如，若結(jié)點屬于最長路徑，則將該結(jié)點的tag域置1，否則為0。

下面僅以輸出所求得的最長路徑為例，給出搜索最長路徑的算法，該算法的遞歸設(shè)計思路如下:

(1) 若二叉樹為空，輸出空序列，算法結(jié)束;

(2) 否則，輸出根結(jié)點元素值，并求根結(jié)點的左右子樹深度，繼續(xù)執(zhí)行第(3)步;

(3) 根據(jù)第(2)步求得的左右子樹深度，選擇深度大的一棵子樹，從其根結(jié)點開始求最長路徑。

假設(shè)樹中結(jié)點的元素值為字符型，即前述抽象數(shù)據(jù)類型DataType為char類型，則該遞歸算法中基于二叉鏈表存儲結(jié)構(gòu)(BTree)上的C語言描述如下:

void SearchLongestPath(BTree root)

{ int hl，hr;//分別表示根結(jié)點左右子樹的深度

if(!root)

printf(\"%c\"，′/0′);//樹空則輸出空串

else {

printf(\"%c\"，root->data);//輸出根結(jié)點元素值

hl=PostTreeDepth(root->Lchild);

hr=PostTreeDepth(root->Rchild);

//調(diào)用求樹的深度的算法求根結(jié)點左右子樹深度

root=hl>=hr?root->Lchild:root->Rchild;

SearchLongestPath(root); }

}

3 結(jié) 語

二叉樹的遍歷是搜索最長路徑算法的基礎(chǔ)。

在搜索二叉樹的最長路徑過程中，依次訪問從根結(jié)點開始到達樹的最大層次的某個結(jié)點，算法的執(zhí)行時間同樹的深度密切相關(guān)。求解二叉樹深度的過程涉及對二叉樹的后序遍歷，從而算法的遞歸調(diào)用次數(shù)同樹中結(jié)點的個數(shù)相關(guān)。

文中列出的所有算法的C語言程序均已通過上機測試。

參考文獻

[1]耿國華. 數(shù)據(jù)結(jié)構(gòu)C語言描述[M]. 西安: 西安電子科技大學(xué)出版社， 2006.

[2]嚴(yán)海洲， 閆志遠. 二叉樹的遍歷及其應(yīng)用實例[J]. 電腦知識與技術(shù)， 2003(5): 43-46.

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

[4]朱站立， 劉天時. 數(shù)據(jù)結(jié)構(gòu)使用C語言[M]. 2版. 西安: 西安交通大學(xué)出版社，1999.

[5]朱濤. 基于遍歷二叉樹的方法判斷完全二叉樹[J]. 紅河學(xué)院學(xué)報， 2005(6): 47-48.

[6]陳朋. 后序遍歷二叉樹的遞歸和非遞歸算法[J]. 安慶師范學(xué)院學(xué)報: 自然科學(xué)版， 2005， 11(2): 106-107.

[7]劉洋. 一種統(tǒng)一的二叉樹結(jié)構(gòu)遍歷算法及其實現(xiàn)[J]. 贛南師范學(xué)院學(xué)報， 2004(3): 10-13.

[8]尹德輝， 孟林， 李忠. 二叉樹后序遍歷的非遞歸化算法討論[J]. 西南民族大學(xué)學(xué)報: 自然科學(xué)版， 2003， 29(5): 537-538.

[9]徐鳳生， 李立群， 馬夕榮. 二叉樹遍歷的通用非遞歸算法[J]. 福建電腦， 2006(6): 121， 41.

[10]徐孝凱. 數(shù)據(jù)結(jié)構(gòu)簡明教程[M]. 北京: 清華大學(xué)出版社， 1995.